#![forbid(unsafe_code)]
use crate::core::adjacency::{AdjacencyIndex, AdjacencyIndexBuildError};
use crate::core::algorithms::flips::{
DelaunayRepairError, DelaunayRepairStats, FlipError, apply_bistellar_flip_k1_inverse,
repair_delaunay_local_single_pass, repair_delaunay_with_flips_k2_k3,
};
use crate::core::algorithms::incremental_insertion::InsertionError;
use crate::core::builder::DelaunayTriangulationBuilder;
use crate::core::cell::Cell;
use crate::core::collections::spatial_hash_grid::HashGridIndex;
use crate::core::collections::{CellKeyBuffer, FastHashMap, FastHasher, SmallBuffer};
use crate::core::edge::EdgeKey;
use crate::core::facet::{AllFacetsIter, BoundaryFacetsIter};
use crate::core::operations::{
DelaunayInsertionState, InsertionOutcome, InsertionStatistics, RepairDecision,
TopologicalOperation,
};
use crate::core::traits::data_type::DataType;
use crate::core::triangulation::{
TopologyGuarantee, Triangulation, TriangulationConstructionError, TriangulationValidationError,
ValidationPolicy, insertion_error_to_invariant_error, record_duplicate_detection_metrics,
};
use crate::core::triangulation_data_structure::{
CellKey, InvariantError, InvariantKind, InvariantViolation, Tds, TdsConstructionError,
TdsError, TriangulationValidationReport, VertexKey,
};
use crate::core::util::{
coords_equal_exact, coords_within_epsilon, hilbert_indices_prequantized, hilbert_quantize,
stable_hash_u64_slice,
};
use crate::core::vertex::Vertex;
use crate::geometry::kernel::{AdaptiveKernel, ExactPredicates, Kernel, RobustKernel};
use crate::geometry::traits::coordinate::{CoordinateScalar, ScalarAccumulative};
use crate::topology::manifold::validate_ridge_links_for_cells;
use crate::topology::traits::topological_space::{GlobalTopology, TopologyKind};
use core::cmp::Ordering;
use num_traits::{NumCast, ToPrimitive, Zero};
use rand::SeedableRng;
use rand::rngs::StdRng;
use rand::seq::SliceRandom;
use serde::{Deserialize, Deserializer, Serialize, Serializer};
use std::hash::{Hash, Hasher};
use std::num::NonZeroUsize;
use std::time::Instant;
use thiserror::Error;
use uuid::Uuid;
#[cfg(any(test, debug_assertions))]
const DELAUNAY_SHUFFLE_ATTEMPTS: usize = 6;
const DELAUNAY_SHUFFLE_SEED_SALT: u64 = 0x9E37_79B9_7F4A_7C15;
#[cfg(any(test, debug_assertions))]
const HEURISTIC_REBUILD_ATTEMPTS: usize = 6;
#[cfg(not(any(test, debug_assertions)))]
const HEURISTIC_REBUILD_ATTEMPTS: usize = 2;
thread_local! {
static HEURISTIC_REBUILD_DEPTH: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
#[cfg(test)]
thread_local! {
static FORCE_HEURISTIC_REBUILD: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
static FORCE_REPAIR_NONCONVERGENT: std::cell::Cell<bool> = const { std::cell::Cell::new(false) };
}
struct HeuristicRebuildRecursionGuard {
prior_depth: usize,
}
impl HeuristicRebuildRecursionGuard {
fn enter() -> Self {
let prior_depth = HEURISTIC_REBUILD_DEPTH.with(|depth| {
let prior = depth.get();
depth.set(prior.saturating_add(1));
prior
});
Self { prior_depth }
}
}
impl Drop for HeuristicRebuildRecursionGuard {
fn drop(&mut self) {
HEURISTIC_REBUILD_DEPTH.with(|depth| depth.set(self.prior_depth));
}
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum DelaunayTriangulationConstructionError {
#[error(transparent)]
Triangulation(#[from] TriangulationConstructionError),
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum DelaunayTriangulationValidationError {
#[error(transparent)]
Tds(#[from] TdsError),
#[error(transparent)]
Triangulation(#[from] TriangulationValidationError),
#[error("Delaunay verification failed: {message}")]
VerificationFailed {
message: String,
},
#[error("Delaunay repair failed: {message}")]
RepairFailed {
message: String,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum InsertionOrderStrategy {
Input,
#[default]
Hilbert,
}
#[derive(Debug, Clone, Copy, PartialEq, Default)]
#[non_exhaustive]
pub enum DedupPolicy {
#[default]
Off,
Exact,
Epsilon {
tolerance: f64,
},
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub enum InitialSimplexStrategy {
#[default]
First,
Balanced,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum RetryPolicy {
Disabled,
Shuffled {
attempts: NonZeroUsize,
base_seed: Option<u64>,
},
DebugOnlyShuffled {
attempts: NonZeroUsize,
base_seed: Option<u64>,
},
}
#[cfg(any(test, debug_assertions))]
impl Default for RetryPolicy {
fn default() -> Self {
Self::DebugOnlyShuffled {
attempts: NonZeroUsize::new(DELAUNAY_SHUFFLE_ATTEMPTS)
.expect("DELAUNAY_SHUFFLE_ATTEMPTS must be non-zero"),
base_seed: None,
}
}
}
#[cfg(not(any(test, debug_assertions)))]
impl Default for RetryPolicy {
fn default() -> Self {
Self::Disabled
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub struct ConstructionOptions {
insertion_order: InsertionOrderStrategy,
dedup_policy: DedupPolicy,
initial_simplex: InitialSimplexStrategy,
retry_policy: RetryPolicy,
pub(crate) use_global_repair_fallback: bool,
}
impl Default for ConstructionOptions {
fn default() -> Self {
Self {
insertion_order: InsertionOrderStrategy::default(),
dedup_policy: DedupPolicy::default(),
initial_simplex: InitialSimplexStrategy::default(),
retry_policy: RetryPolicy::default(),
use_global_repair_fallback: true,
}
}
}
impl ConstructionOptions {
#[must_use]
pub const fn insertion_order(&self) -> InsertionOrderStrategy {
self.insertion_order
}
#[must_use]
pub const fn dedup_policy(&self) -> DedupPolicy {
self.dedup_policy
}
#[must_use]
pub const fn initial_simplex_strategy(&self) -> InitialSimplexStrategy {
self.initial_simplex
}
#[must_use]
pub const fn retry_policy(&self) -> RetryPolicy {
self.retry_policy
}
#[must_use]
pub const fn with_insertion_order(mut self, insertion_order: InsertionOrderStrategy) -> Self {
self.insertion_order = insertion_order;
self
}
#[must_use]
pub const fn with_dedup_policy(mut self, dedup_policy: DedupPolicy) -> Self {
self.dedup_policy = dedup_policy;
self
}
#[must_use]
pub const fn with_initial_simplex_strategy(
mut self,
initial_simplex: InitialSimplexStrategy,
) -> Self {
self.initial_simplex = initial_simplex;
self
}
#[must_use]
pub const fn with_retry_policy(mut self, retry_policy: RetryPolicy) -> Self {
self.retry_policy = retry_policy;
self
}
#[must_use]
pub(crate) const fn without_global_repair_fallback(mut self) -> Self {
self.use_global_repair_fallback = false;
self
}
}
#[derive(Debug, Default, Clone)]
#[non_exhaustive]
pub struct ConstructionStatistics {
pub inserted: usize,
pub skipped_duplicate: usize,
pub skipped_degeneracy: usize,
pub total_attempts: usize,
pub max_attempts: usize,
pub attempts_histogram: Vec<usize>,
pub used_perturbation: usize,
pub cells_removed_total: usize,
pub cells_removed_max: usize,
pub skip_samples: Vec<ConstructionSkipSample>,
}
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct ConstructionSkipSample {
pub index: usize,
pub uuid: Uuid,
pub coords: Vec<f64>,
pub attempts: usize,
pub error: String,
}
#[derive(Debug, Clone, thiserror::Error)]
#[error("{error}")]
#[non_exhaustive]
pub struct DelaunayTriangulationConstructionErrorWithStatistics {
#[source]
pub error: DelaunayTriangulationConstructionError,
pub statistics: ConstructionStatistics,
}
impl ConstructionStatistics {
#[inline]
fn record_common(&mut self, stats: &InsertionStatistics) {
self.total_attempts = self.total_attempts.saturating_add(stats.attempts);
self.max_attempts = self.max_attempts.max(stats.attempts);
if self.attempts_histogram.len() <= stats.attempts {
self.attempts_histogram.resize(stats.attempts + 1, 0);
}
self.attempts_histogram[stats.attempts] =
self.attempts_histogram[stats.attempts].saturating_add(1);
if stats.used_perturbation() {
self.used_perturbation = self.used_perturbation.saturating_add(1);
}
self.cells_removed_total = self
.cells_removed_total
.saturating_add(stats.cells_removed_during_repair);
self.cells_removed_max = self
.cells_removed_max
.max(stats.cells_removed_during_repair);
}
const MAX_SKIP_SAMPLES: usize = 8;
pub fn record_insertion(&mut self, stats: &InsertionStatistics) {
if stats.skipped_duplicate() {
self.skipped_duplicate = self.skipped_duplicate.saturating_add(1);
} else if stats.skipped() {
self.skipped_degeneracy = self.skipped_degeneracy.saturating_add(1);
} else {
self.inserted = self.inserted.saturating_add(1);
}
self.record_common(stats);
}
pub fn record_skip_sample(&mut self, sample: ConstructionSkipSample) {
if self.skip_samples.len() < Self::MAX_SKIP_SAMPLES {
self.skip_samples.push(sample);
}
}
#[must_use]
pub const fn total_skipped(&self) -> usize {
self.skipped_duplicate + self.skipped_degeneracy
}
}
type VertexBuffer<T, U, const D: usize> = Vec<Vertex<T, U, D>>;
struct PreprocessVertices<T, U, const D: usize>
where
T: CoordinateScalar,
U: DataType,
{
primary: Option<VertexBuffer<T, U, D>>,
fallback: Option<VertexBuffer<T, U, D>>,
grid_cell_size: Option<T>,
}
impl<T, U, const D: usize> PreprocessVertices<T, U, D>
where
T: CoordinateScalar,
U: DataType,
{
fn primary_slice<'a>(&'a self, input: &'a [Vertex<T, U, D>]) -> &'a [Vertex<T, U, D>] {
self.primary.as_deref().unwrap_or(input)
}
fn fallback_slice(&self) -> Option<&[Vertex<T, U, D>]> {
self.fallback.as_deref()
}
const fn grid_cell_size(&self) -> Option<T>
where
T: Copy,
{
self.grid_cell_size
}
}
type PreprocessVerticesResult<T, U, const D: usize> =
Result<PreprocessVertices<T, U, D>, DelaunayTriangulationConstructionError>;
fn vertex_coordinate_hash<T, U, const D: usize>(vertex: &Vertex<T, U, D>) -> u64
where
T: CoordinateScalar,
U: DataType,
{
let mut hasher = FastHasher::default();
vertex.hash(&mut hasher);
hasher.finish()
}
fn order_vertices_lexicographic<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
let mut keyed: Vec<(Vertex<T, U, D>, u64, usize)> = vertices
.into_iter()
.enumerate()
.map(|(input_index, vertex)| {
let hash = vertex_coordinate_hash(&vertex);
(vertex, hash, input_index)
})
.collect();
keyed.sort_by(|(a, a_hash, a_idx), (b, b_hash, b_idx)| {
a.partial_cmp(b)
.unwrap_or(Ordering::Equal)
.then_with(|| a_hash.cmp(b_hash))
.then_with(|| a_idx.cmp(b_idx))
});
keyed.into_iter().map(|(v, _, _)| v).collect()
}
const BATCH_DEDUP_BUCKET_INLINE_CAPACITY: usize = 8;
const BATCH_DEDUP_MAX_DIMENSION: usize = 5;
fn order_vertices_by_strategy<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
insertion_order: InsertionOrderStrategy,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
match insertion_order {
InsertionOrderStrategy::Input => vertices,
InsertionOrderStrategy::Hilbert => order_vertices_hilbert(vertices, true),
}
}
fn default_duplicate_tolerance<T: CoordinateScalar>() -> T {
<T as NumCast>::from(1e-10_f64).unwrap_or_else(T::default_tolerance)
}
fn hash_grid_usable_for_vertices<T, U, const D: usize>(
grid: &HashGridIndex<T, D, usize>,
vertices: &[Vertex<T, U, D>],
) -> bool
where
T: CoordinateScalar,
U: DataType,
{
if !grid.is_usable() {
return false;
}
vertices
.iter()
.all(|v| grid.can_key_coords(v.point().coords()))
}
fn dedup_vertices_exact_sorted<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
let ordered = order_vertices_lexicographic(vertices);
let mut unique: Vec<Vertex<T, U, D>> = Vec::with_capacity(ordered.len());
for v in ordered {
if let Some(last) = unique.last()
&& coords_equal_exact(v.point().coords(), last.point().coords())
{
record_duplicate_detection_metrics(false, 0, true);
continue;
}
record_duplicate_detection_metrics(false, 0, true);
unique.push(v);
}
unique
}
fn dedup_vertices_exact_hash_grid<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
grid: &mut HashGridIndex<T, D, usize>,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
if !hash_grid_usable_for_vertices(grid, &vertices) {
return dedup_vertices_exact_sorted(vertices);
}
grid.clear();
let mut unique: Vec<Vertex<T, U, D>> = Vec::with_capacity(vertices.len());
for v in vertices {
let coords = v.point().coords();
let mut duplicate = false;
let mut candidate_count = 0usize;
let used_index = grid.for_each_candidate_vertex_key(coords, |idx| {
candidate_count = candidate_count.saturating_add(1);
let existing_coords = unique[idx].point().coords();
if coords_equal_exact(coords, existing_coords) {
duplicate = true;
return false;
}
true
});
record_duplicate_detection_metrics(used_index, candidate_count, !used_index);
if !duplicate {
let idx = unique.len();
unique.push(v);
grid.insert_vertex(idx, coords);
}
}
unique
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
struct QuantizedKey<const D: usize>([i64; D]);
fn quantize_coords<T: CoordinateScalar, const D: usize>(
coords: &[T; D],
inv_cell: f64,
) -> Option<[i64; D]> {
let mut key = [0_i64; D];
for (axis, coord) in coords.iter().enumerate() {
let c = coord.to_f64()?;
if !c.is_finite() {
return None;
}
let scaled = c * inv_cell;
if !scaled.is_finite() {
return None;
}
let quantized = scaled.floor();
let q = quantized.to_i64()?;
key[axis] = q;
}
Some(key)
}
fn visit_quantized_neighbors<const D: usize, F>(
axis: usize,
base: &[i64; D],
current: &mut [i64; D],
f: &mut F,
) -> bool
where
F: FnMut([i64; D]) -> bool,
{
if axis == D {
return f(*current);
}
let offsets = [-1_i64, 0, 1];
for offset in offsets {
if let Some(value) = base[axis].checked_add(offset) {
current[axis] = value;
if !visit_quantized_neighbors(axis + 1, base, current, f) {
return false;
}
}
}
true
}
fn dedup_vertices_epsilon_n2<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
epsilon: T,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
let mut unique: Vec<Vertex<T, U, D>> = Vec::with_capacity(vertices.len());
for v in vertices {
let mut duplicate = false;
for u in &unique {
if coords_within_epsilon(v.point().coords(), u.point().coords(), epsilon) {
duplicate = true;
break;
}
}
record_duplicate_detection_metrics(false, 0, true);
if !duplicate {
unique.push(v);
}
}
unique
}
fn dedup_vertices_epsilon_quantized<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
epsilon: T,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
if D > BATCH_DEDUP_MAX_DIMENSION {
return dedup_vertices_epsilon_n2(vertices, epsilon);
}
let Some(eps_f64) = epsilon.to_f64() else {
return dedup_vertices_epsilon_n2(vertices, epsilon);
};
if !eps_f64.is_finite() || eps_f64 <= 0.0 {
return dedup_vertices_epsilon_n2(vertices, epsilon);
}
let inv_cell = 1.0 / eps_f64;
let mut buckets: FastHashMap<
QuantizedKey<D>,
SmallBuffer<usize, BATCH_DEDUP_BUCKET_INLINE_CAPACITY>,
> = FastHashMap::default();
let mut unique: Vec<Vertex<T, U, D>> = Vec::with_capacity(vertices.len());
let mut iter = vertices.into_iter();
while let Some(v) = iter.next() {
let coords = v.point().coords();
let Some(base_key) = quantize_coords(coords, inv_cell) else {
return dedup_vertices_epsilon_n2(
unique
.into_iter()
.chain(std::iter::once(v))
.chain(iter)
.collect(),
epsilon,
);
};
let mut duplicate = false;
let mut candidate_count = 0usize;
let mut current = base_key;
visit_quantized_neighbors(0, &base_key, &mut current, &mut |neighbor| {
if let Some(bucket) = buckets.get(&QuantizedKey(neighbor)) {
for &idx in bucket {
candidate_count = candidate_count.saturating_add(1);
let existing_coords = unique[idx].point().coords();
if coords_within_epsilon(coords, existing_coords, epsilon) {
duplicate = true;
return false;
}
}
}
true
});
record_duplicate_detection_metrics(false, 0, true);
if !duplicate {
let idx = unique.len();
unique.push(v);
buckets.entry(QuantizedKey(base_key)).or_default().push(idx);
}
}
unique
}
fn dedup_vertices_epsilon_hash_grid<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
epsilon: T,
grid: &mut HashGridIndex<T, D, usize>,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
if !hash_grid_usable_for_vertices(grid, &vertices) {
return dedup_vertices_epsilon_quantized(vertices, epsilon);
}
grid.clear();
let mut unique: Vec<Vertex<T, U, D>> = Vec::with_capacity(vertices.len());
let epsilon_sq = epsilon * epsilon;
for v in vertices {
let coords = v.point().coords();
let mut duplicate = false;
let mut candidate_count = 0usize;
let used_index = grid.for_each_candidate_vertex_key(coords, |idx| {
candidate_count = candidate_count.saturating_add(1);
let existing_coords = unique[idx].point().coords();
let mut dist_sq = T::zero();
for i in 0..D {
let diff = coords[i] - existing_coords[i];
dist_sq = dist_sq + diff * diff;
}
if dist_sq < epsilon_sq {
duplicate = true;
return false;
}
true
});
record_duplicate_detection_metrics(used_index, candidate_count, !used_index);
if !duplicate {
let idx = unique.len();
unique.push(v);
grid.insert_vertex(idx, coords);
}
}
unique
}
fn select_balanced_simplex_indices<T, U, const D: usize>(
vertices: &[Vertex<T, U, D>],
) -> Option<Vec<usize>>
where
T: CoordinateScalar,
U: DataType,
{
if vertices.len() < D + 1 {
return None;
}
let mut coords_f64: Vec<[f64; D]> = Vec::with_capacity(vertices.len());
for v in vertices {
let mut coords = [0.0_f64; D];
for (axis, coord) in v.point().coords().iter().enumerate() {
let c = coord.to_f64()?;
if !c.is_finite() {
return None;
}
coords[axis] = c;
}
coords_f64.push(coords);
}
let dist_sq = |a: &[f64; D], b: &[f64; D]| {
a.iter()
.zip(b.iter())
.map(|(lhs, rhs)| {
let diff = lhs - rhs;
diff * diff
})
.sum::<f64>()
};
let mut seed_idx = 0usize;
for i in 1..coords_f64.len() {
if coords_f64[i].partial_cmp(&coords_f64[seed_idx]) == Some(Ordering::Less) {
seed_idx = i;
}
}
let mut selected = Vec::with_capacity(D + 1);
let mut selected_mask = vec![false; coords_f64.len()];
selected.push(seed_idx);
selected_mask[seed_idx] = true;
let mut min_dist_sq = vec![f64::INFINITY; coords_f64.len()];
for i in 0..coords_f64.len() {
min_dist_sq[i] = dist_sq(&coords_f64[i], &coords_f64[seed_idx]);
}
min_dist_sq[seed_idx] = 0.0;
while selected.len() < D + 1 {
let mut best_idx: Option<usize> = None;
let mut best_dist = -1.0_f64;
for i in 0..coords_f64.len() {
if selected_mask[i] {
continue;
}
let dist = min_dist_sq[i];
if !dist.is_finite() {
continue;
}
let replace = best_idx.is_none_or(|best_idx_val| match dist.partial_cmp(&best_dist) {
Some(Ordering::Greater) => true,
Some(Ordering::Equal) => {
coords_f64[i].partial_cmp(&coords_f64[best_idx_val]) == Some(Ordering::Less)
}
_ => false,
});
if replace {
best_idx = Some(i);
best_dist = dist;
}
}
let Some(best_idx) = best_idx else {
break;
};
selected.push(best_idx);
selected_mask[best_idx] = true;
for i in 0..coords_f64.len() {
if selected_mask[i] {
continue;
}
let dist_sq = dist_sq(&coords_f64[i], &coords_f64[best_idx]);
if dist_sq < min_dist_sq[i] {
min_dist_sq[i] = dist_sq;
}
}
}
if selected.len() == D + 1 {
Some(selected)
} else {
None
}
}
fn reorder_vertices_for_simplex<T, U, const D: usize>(
vertices: &[Vertex<T, U, D>],
simplex_indices: &[usize],
) -> Option<Vec<Vertex<T, U, D>>>
where
T: CoordinateScalar,
U: DataType,
{
if simplex_indices.len() != D + 1 {
return None;
}
let mut seen = vec![false; vertices.len()];
let mut reordered = Vec::with_capacity(vertices.len());
for &idx in simplex_indices {
if idx >= vertices.len() || seen[idx] {
return None;
}
seen[idx] = true;
reordered.push(vertices[idx]);
}
for (idx, vertex) in vertices.iter().enumerate() {
if !seen[idx] {
reordered.push(*vertex);
}
}
Some(reordered)
}
fn hilbert_bits_per_coord<const D: usize>() -> Option<u32> {
if D == 0 {
return None;
}
let Ok(d_u32) = u32::try_from(D) else {
return None;
};
let bits_per_coord = (128_u32 / d_u32).min(31);
if bits_per_coord == 0 {
return None;
}
Some(bits_per_coord)
}
type HilbertSortKey<T, U, const D: usize> = (u128, [u32; D], Vertex<T, U, D>, usize);
fn order_vertices_hilbert<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
dedup_quantized: bool,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
U: DataType,
{
if vertices.is_empty() || D == 0 {
return vertices;
}
let Some(bits_per_coord) = hilbert_bits_per_coord::<D>() else {
return order_vertices_lexicographic(vertices);
};
let mut min = f64::INFINITY;
let mut max = f64::NEG_INFINITY;
for v in &vertices {
for &coord in v.point().coords() {
let Some(c) = coord.to_f64() else {
return order_vertices_lexicographic(vertices);
};
if !c.is_finite() {
return order_vertices_lexicographic(vertices);
}
min = min.min(c);
max = max.max(c);
}
}
let (Some(min_t), Some(max_t)) = (NumCast::from(min), NumCast::from(max)) else {
return order_vertices_lexicographic(vertices);
};
let bounds = (min_t, max_t);
let quantized: Result<Vec<[u32; D]>, ()> = vertices
.iter()
.map(|vertex| {
hilbert_quantize(vertex.point().coords(), bounds, bits_per_coord).map_err(|_| ())
})
.collect();
let Ok(quantized) = quantized else {
return order_vertices_lexicographic(vertices);
};
let Ok(indices) = hilbert_indices_prequantized(&quantized, bits_per_coord) else {
return order_vertices_lexicographic(vertices);
};
let mut keyed: Vec<HilbertSortKey<T, U, D>> = vertices
.into_iter()
.enumerate()
.map(|(input_index, vertex)| {
let idx = indices
.get(input_index)
.copied()
.unwrap_or(input_index as u128);
let q = quantized[input_index];
(idx, q, vertex, input_index)
})
.collect();
keyed.sort_by(
|(a_idx, a_q, a_vertex, a_in), (b_idx, b_q, b_vertex, b_in)| {
a_idx
.cmp(b_idx)
.then_with(|| a_q.cmp(b_q))
.then_with(|| a_vertex.partial_cmp(b_vertex).unwrap_or(Ordering::Equal))
.then_with(|| a_in.cmp(b_in))
},
);
if dedup_quantized {
let input_len = keyed.len();
let mut prev_q: Option<[u32; D]> = None;
let deduped: Vec<Vertex<T, U, D>> = keyed
.into_iter()
.filter_map(|(_, q, v, _)| {
if prev_q == Some(q) {
return None;
}
prev_q = Some(q);
Some(v)
})
.collect();
let removed = input_len - deduped.len();
if removed > 0 {
tracing::debug!(
"Hilbert-sort dedup removed {removed} vertices (quantized at {bits_per_coord} bits/coord)"
);
}
deduped
} else {
keyed.into_iter().map(|(_, _, v, _)| v).collect()
}
}
#[derive(Clone, Debug)]
pub struct DelaunayTriangulation<K, U, V, const D: usize>
where
K: Kernel<D>,
U: DataType,
V: DataType,
{
pub(crate) tri: Triangulation<K, U, V, D>,
insertion_state: DelaunayInsertionState,
spatial_index: Option<HashGridIndex<K::Scalar, D>>,
}
impl<const D: usize> DelaunayTriangulation<AdaptiveKernel<f64>, (), (), D> {
pub fn new(
vertices: &[Vertex<f64, (), D>],
) -> Result<Self, DelaunayTriangulationConstructionError> {
Self::with_kernel(&AdaptiveKernel::<f64>::new(), vertices)
}
#[expect(
clippy::result_large_err,
reason = "Public API intentionally returns by-value construction statistics for compatibility"
)]
pub fn new_with_construction_statistics(
vertices: &[Vertex<f64, (), D>],
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
let kernel = AdaptiveKernel::<f64>::new();
Self::with_topology_guarantee_and_options_with_construction_statistics(
&kernel,
vertices,
TopologyGuarantee::DEFAULT,
ConstructionOptions::default(),
)
}
#[expect(
clippy::result_large_err,
reason = "Public API intentionally returns by-value construction statistics for compatibility"
)]
pub fn new_with_options_and_construction_statistics(
vertices: &[Vertex<f64, (), D>],
options: ConstructionOptions,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
let kernel = AdaptiveKernel::<f64>::new();
Self::with_topology_guarantee_and_options_with_construction_statistics(
&kernel,
vertices,
TopologyGuarantee::DEFAULT,
options,
)
}
pub fn new_with_options(
vertices: &[Vertex<f64, (), D>],
options: ConstructionOptions,
) -> Result<Self, DelaunayTriangulationConstructionError> {
let kernel = AdaptiveKernel::<f64>::new();
Self::with_topology_guarantee_and_options(
&kernel,
vertices,
TopologyGuarantee::DEFAULT,
options,
)
}
pub fn new_with_topology_guarantee(
vertices: &[Vertex<f64, (), D>],
topology_guarantee: TopologyGuarantee,
) -> Result<Self, DelaunayTriangulationConstructionError> {
let kernel = AdaptiveKernel::<f64>::new();
Self::with_topology_guarantee(&kernel, vertices, topology_guarantee)
}
#[must_use]
pub fn empty() -> Self {
Self::with_empty_kernel(AdaptiveKernel::<f64>::new())
}
#[must_use]
pub fn empty_with_topology_guarantee(topology_guarantee: TopologyGuarantee) -> Self {
Self::with_empty_kernel_and_topology_guarantee(
AdaptiveKernel::<f64>::new(),
topology_guarantee,
)
}
#[must_use]
pub fn builder(
vertices: &[Vertex<f64, (), D>],
) -> DelaunayTriangulationBuilder<'_, f64, (), D> {
DelaunayTriangulationBuilder::new(vertices)
}
}
impl<K, U, V, const D: usize> DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
K::Scalar: ScalarAccumulative + NumCast,
U: DataType,
V: DataType,
{
#[must_use]
pub fn with_empty_kernel(kernel: K) -> Self {
let duplicate_tolerance = default_duplicate_tolerance::<K::Scalar>();
Self {
tri: Triangulation::new_empty(kernel),
insertion_state: DelaunayInsertionState::new(),
spatial_index: Some(HashGridIndex::new(duplicate_tolerance)),
}
}
#[must_use]
pub fn with_empty_kernel_and_topology_guarantee(
kernel: K,
topology_guarantee: TopologyGuarantee,
) -> Self {
let duplicate_tolerance = default_duplicate_tolerance::<K::Scalar>();
let mut tri = Triangulation::new_empty(kernel);
tri.set_topology_guarantee(topology_guarantee);
Self {
tri,
insertion_state: DelaunayInsertionState::new(),
spatial_index: Some(HashGridIndex::new(duplicate_tolerance)),
}
}
pub fn with_kernel(
kernel: &K,
vertices: &[Vertex<K::Scalar, U, D>],
) -> Result<Self, DelaunayTriangulationConstructionError> {
Self::with_topology_guarantee(kernel, vertices, TopologyGuarantee::DEFAULT)
}
pub fn with_topology_guarantee(
kernel: &K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
) -> Result<Self, DelaunayTriangulationConstructionError> {
Self::with_topology_guarantee_and_options(
kernel,
vertices,
topology_guarantee,
ConstructionOptions::default(),
)
}
pub fn with_topology_guarantee_and_options(
kernel: &K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
options: ConstructionOptions,
) -> Result<Self, DelaunayTriangulationConstructionError> {
let ConstructionOptions {
insertion_order,
dedup_policy,
initial_simplex,
retry_policy,
use_global_repair_fallback,
} = options;
let preprocessed = Self::preprocess_vertices_for_construction(
vertices,
dedup_policy,
insertion_order,
initial_simplex,
)?;
let grid_cell_size = preprocessed.grid_cell_size();
let primary_vertices: &[Vertex<K::Scalar, U, D>] = preprocessed.primary_slice(vertices);
let fallback_vertices = preprocessed.fallback_slice();
let build_with_vertices = |vertices: &[Vertex<K::Scalar, U, D>]| {
match retry_policy {
RetryPolicy::Disabled => {}
RetryPolicy::Shuffled {
attempts,
base_seed,
} => {
if Self::should_retry_construction(vertices) {
return Self::build_with_shuffled_retries(
kernel,
vertices,
topology_guarantee,
attempts,
base_seed,
grid_cell_size,
use_global_repair_fallback,
);
}
}
RetryPolicy::DebugOnlyShuffled {
attempts,
base_seed,
} => {
if cfg!(any(test, debug_assertions))
&& Self::should_retry_construction(vertices)
{
return Self::build_with_shuffled_retries(
kernel,
vertices,
topology_guarantee,
attempts,
base_seed,
grid_cell_size,
use_global_repair_fallback,
);
}
}
}
Self::build_with_kernel_inner(
<K as Clone>::clone(kernel),
vertices,
topology_guarantee,
grid_cell_size,
use_global_repair_fallback,
)
};
let result = build_with_vertices(primary_vertices);
if result.is_err()
&& let Some(fallback) = fallback_vertices
{
return build_with_vertices(fallback);
}
result
}
#[expect(
clippy::result_large_err,
reason = "Public API intentionally returns by-value construction statistics for compatibility"
)]
pub fn with_topology_guarantee_and_options_with_construction_statistics(
kernel: &K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
options: ConstructionOptions,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
let ConstructionOptions {
insertion_order,
dedup_policy,
initial_simplex,
retry_policy,
use_global_repair_fallback,
} = options;
let preprocessed = Self::preprocess_vertices_for_construction(
vertices,
dedup_policy,
insertion_order,
initial_simplex,
)
.map_err(
|error| DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: ConstructionStatistics::default(),
},
)?;
let grid_cell_size = preprocessed.grid_cell_size();
let primary_vertices: &[Vertex<K::Scalar, U, D>] = preprocessed.primary_slice(vertices);
let fallback_vertices = preprocessed.fallback_slice();
let build_with_vertices = |vertices: &[Vertex<K::Scalar, U, D>]| {
match retry_policy {
RetryPolicy::Disabled => {}
RetryPolicy::Shuffled {
attempts,
base_seed,
} => {
if Self::should_retry_construction(vertices) {
return Self::build_with_shuffled_retries_with_construction_statistics(
kernel,
vertices,
topology_guarantee,
attempts,
base_seed,
grid_cell_size,
use_global_repair_fallback,
);
}
}
RetryPolicy::DebugOnlyShuffled {
attempts,
base_seed,
} => {
if cfg!(any(test, debug_assertions))
&& Self::should_retry_construction(vertices)
{
return Self::build_with_shuffled_retries_with_construction_statistics(
kernel,
vertices,
topology_guarantee,
attempts,
base_seed,
grid_cell_size,
use_global_repair_fallback,
);
}
}
}
Self::build_with_kernel_inner_with_construction_statistics(
<K as Clone>::clone(kernel),
vertices,
topology_guarantee,
grid_cell_size,
use_global_repair_fallback,
)
};
let result = build_with_vertices(primary_vertices);
if result.is_err()
&& let Some(fallback) = fallback_vertices
{
return build_with_vertices(fallback);
}
result
}
fn preprocess_vertices_for_construction(
vertices: &[Vertex<K::Scalar, U, D>],
dedup_policy: DedupPolicy,
insertion_order: InsertionOrderStrategy,
initial_simplex: InitialSimplexStrategy,
) -> PreprocessVerticesResult<K::Scalar, U, D> {
let default_tolerance = default_duplicate_tolerance::<K::Scalar>();
let mut epsilon: Option<K::Scalar> = None;
if let DedupPolicy::Epsilon { tolerance } = dedup_policy {
if !tolerance.is_finite() || tolerance < 0.0 {
return Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Invalid DedupPolicy::Epsilon tolerance {tolerance:?} (must be finite and non-negative)"
),
}
.into());
}
let Some(epsilon_value) = <K::Scalar as NumCast>::from(tolerance) else {
return Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Failed to convert DedupPolicy::Epsilon tolerance {tolerance:?} into scalar type"
),
}
.into());
};
epsilon = Some(epsilon_value);
}
let grid_cell_size_value =
if let (DedupPolicy::Epsilon { .. }, Some(eps)) = (dedup_policy, epsilon) {
if eps > K::Scalar::zero() {
eps
} else {
default_tolerance
}
} else {
default_tolerance
};
let mut grid: HashGridIndex<K::Scalar, D, usize> = HashGridIndex::new(grid_cell_size_value);
let mut owned_vertices: Option<Vec<Vertex<K::Scalar, U, D>>> = match dedup_policy {
DedupPolicy::Off => None,
DedupPolicy::Exact => {
let vertices = vertices.to_vec();
if hash_grid_usable_for_vertices(&grid, &vertices) {
Some(dedup_vertices_exact_hash_grid(vertices, &mut grid))
} else {
Some(dedup_vertices_exact_sorted(vertices))
}
}
DedupPolicy::Epsilon { .. } => {
let epsilon = epsilon.expect("epsilon validated above");
let vertices = vertices.to_vec();
if hash_grid_usable_for_vertices(&grid, &vertices) {
Some(dedup_vertices_epsilon_hash_grid(
vertices, epsilon, &mut grid,
))
} else {
Some(dedup_vertices_epsilon_quantized(vertices, epsilon))
}
}
};
owned_vertices = match insertion_order {
InsertionOrderStrategy::Input => owned_vertices,
_ => Some(order_vertices_by_strategy(
owned_vertices.unwrap_or_else(|| vertices.to_vec()),
insertion_order,
)),
};
let (primary, fallback) = match initial_simplex {
InitialSimplexStrategy::First => (owned_vertices, None),
InitialSimplexStrategy::Balanced => {
let base = owned_vertices.unwrap_or_else(|| vertices.to_vec());
if let Some(indices) = select_balanced_simplex_indices(&base) {
if let Some(reordered) = reorder_vertices_for_simplex(&base, &indices) {
(Some(reordered), Some(base))
} else {
(Some(base), None)
}
} else {
(Some(base), None)
}
}
};
let final_slice = primary.as_deref().unwrap_or(vertices);
let grid_cell_size = if hash_grid_usable_for_vertices(&grid, final_slice) {
Some(grid.cell_size())
} else {
None
};
Ok(PreprocessVertices {
primary,
fallback,
grid_cell_size,
})
}
const fn is_non_retryable_construction_error(
err: &DelaunayTriangulationConstructionError,
) -> bool {
matches!(
err,
DelaunayTriangulationConstructionError::Triangulation(
TriangulationConstructionError::Tds(TdsConstructionError::DuplicateUuid { .. })
| TriangulationConstructionError::InternalInconsistency { .. }
)
)
}
#[allow(clippy::too_many_lines)]
fn build_with_shuffled_retries(
kernel: &K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
attempts: NonZeroUsize,
base_seed: Option<u64>,
grid_cell_size: Option<K::Scalar>,
use_global_repair_fallback: bool,
) -> Result<Self, DelaunayTriangulationConstructionError> {
let base_seed = base_seed.unwrap_or_else(|| Self::construction_shuffle_seed(vertices));
#[cfg(debug_assertions)]
let log_shuffle = std::env::var_os("DELAUNAY_DEBUG_SHUFFLE").is_some();
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
base_seed,
attempts = attempts.get(),
vertex_count = vertices.len(),
"build_with_shuffled_retries: starting"
);
}
let mut last_error: String = match Self::build_with_kernel_inner_seeded(
<K as Clone>::clone(kernel),
vertices,
topology_guarantee,
0_u64,
true,
grid_cell_size,
use_global_repair_fallback,
) {
Ok(candidate) => match crate::core::util::is_delaunay_property_only(&candidate.tri.tds)
{
Ok(()) => return Ok(candidate),
Err(err) => format!("Delaunay property violated after construction: {err}"),
},
Err(err) => {
if Self::is_non_retryable_construction_error(&err) {
return Err(err);
}
err.to_string()
}
};
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
attempt = 0,
perturbation_seed = 0_u64,
last_error = %last_error,
"build_with_shuffled_retries: initial attempt failed: {last_error}"
);
}
for attempt in 1..=attempts.get() {
let mut shuffled = vertices.to_vec();
let mut attempt_seed =
base_seed.wrapping_add((attempt as u64).wrapping_mul(DELAUNAY_SHUFFLE_SEED_SALT));
if attempt_seed == 0 {
attempt_seed = 1;
}
Self::shuffle_vertices(&mut shuffled, attempt_seed);
let perturbation_seed = attempt_seed ^ 0xD1B5_4A32_D192_ED03;
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
attempt,
attempt_seed,
perturbation_seed,
"build_with_shuffled_retries: shuffled attempt starting"
);
}
match Self::build_with_kernel_inner_seeded(
<K as Clone>::clone(kernel),
&shuffled,
topology_guarantee,
perturbation_seed,
true,
grid_cell_size,
use_global_repair_fallback,
) {
Ok(candidate) => {
match crate::core::util::is_delaunay_property_only(&candidate.tri.tds) {
Ok(()) => return Ok(candidate),
Err(err) => {
last_error =
format!("Delaunay property violated after construction: {err}");
}
}
}
Err(err) => {
if Self::is_non_retryable_construction_error(&err) {
return Err(err);
}
last_error = err.to_string();
}
}
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
attempt,
attempt_seed,
perturbation_seed,
last_error = %last_error,
"build_with_shuffled_retries: attempt failed: {last_error}"
);
}
}
Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Delaunay construction failed after shuffled reconstruction attempts: {last_error}"
),
}
.into())
}
#[allow(clippy::too_many_lines)]
#[expect(
clippy::result_large_err,
reason = "Internal helper propagates public by-value construction-statistics error type"
)]
fn build_with_shuffled_retries_with_construction_statistics(
kernel: &K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
attempts: NonZeroUsize,
base_seed: Option<u64>,
grid_cell_size: Option<K::Scalar>,
use_global_repair_fallback: bool,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
let base_seed = base_seed.unwrap_or_else(|| Self::construction_shuffle_seed(vertices));
#[cfg(debug_assertions)]
let log_shuffle = std::env::var_os("DELAUNAY_DEBUG_SHUFFLE").is_some();
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
base_seed,
attempts = attempts.get(),
vertex_count = vertices.len(),
"build_with_shuffled_retries_with_construction_statistics: starting"
);
}
let mut last_stats: Option<ConstructionStatistics> = None;
let mut last_error: String =
match Self::build_with_kernel_inner_seeded_with_construction_statistics(
<K as Clone>::clone(kernel),
vertices,
topology_guarantee,
0_u64,
true,
grid_cell_size,
use_global_repair_fallback,
) {
Ok((candidate, stats)) => {
match crate::core::util::is_delaunay_property_only(&candidate.tri.tds) {
Ok(()) => return Ok((candidate, stats)),
Err(err) => {
last_stats.replace(stats);
format!("Delaunay property violated after construction: {err}")
}
}
}
Err(err) => {
let DelaunayTriangulationConstructionErrorWithStatistics { error, statistics } =
err;
if Self::is_non_retryable_construction_error(&error) {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics,
});
}
last_stats.replace(statistics);
error.to_string()
}
};
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
attempt = 0,
perturbation_seed = 0_u64,
last_error = %last_error,
"build_with_shuffled_retries_with_construction_statistics: initial attempt failed: {last_error}"
);
}
for attempt in 1..=attempts.get() {
let mut shuffled = vertices.to_vec();
let mut attempt_seed =
base_seed.wrapping_add((attempt as u64).wrapping_mul(DELAUNAY_SHUFFLE_SEED_SALT));
if attempt_seed == 0 {
attempt_seed = 1;
}
Self::shuffle_vertices(&mut shuffled, attempt_seed);
let perturbation_seed = attempt_seed ^ 0xD1B5_4A32_D192_ED03;
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
attempt,
attempt_seed,
perturbation_seed,
"build_with_shuffled_retries_with_construction_statistics: shuffled attempt starting"
);
}
match Self::build_with_kernel_inner_seeded_with_construction_statistics(
<K as Clone>::clone(kernel),
&shuffled,
topology_guarantee,
perturbation_seed,
true,
grid_cell_size,
use_global_repair_fallback,
) {
Ok((candidate, stats)) => {
match crate::core::util::is_delaunay_property_only(&candidate.tri.tds) {
Ok(()) => return Ok((candidate, stats)),
Err(err) => {
last_stats.replace(stats);
last_error =
format!("Delaunay property violated after construction: {err}");
}
}
}
Err(err) => {
let DelaunayTriangulationConstructionErrorWithStatistics { error, statistics } =
err;
if Self::is_non_retryable_construction_error(&error) {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics,
});
}
last_stats.replace(statistics);
last_error = error.to_string();
}
}
#[cfg(debug_assertions)]
if log_shuffle {
tracing::debug!(
attempt,
attempt_seed,
perturbation_seed,
last_error = %last_error,
"build_with_shuffled_retries_with_construction_statistics: attempt failed: {last_error}"
);
}
}
let statistics = last_stats.unwrap_or_default();
Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Delaunay construction failed after shuffled reconstruction attempts: {last_error}"
),
}
.into(),
statistics,
})
}
const fn should_retry_construction(vertices: &[Vertex<K::Scalar, U, D>]) -> bool {
D >= 2 && vertices.len() > D + 1
}
fn construction_shuffle_seed(vertices: &[Vertex<K::Scalar, U, D>]) -> u64 {
let mut vertex_hashes = Vec::with_capacity(vertices.len());
for vertex in vertices {
let mut hasher = FastHasher::default();
vertex.hash(&mut hasher);
vertex_hashes.push(hasher.finish());
}
vertex_hashes.sort_unstable();
stable_hash_u64_slice(&vertex_hashes)
}
fn shuffle_vertices(vertices: &mut [Vertex<K::Scalar, U, D>], seed: u64) {
let mut rng = StdRng::seed_from_u64(seed);
vertices.shuffle(&mut rng);
}
fn build_with_kernel_inner(
kernel: K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
grid_cell_size: Option<K::Scalar>,
use_global_repair_fallback: bool,
) -> Result<Self, DelaunayTriangulationConstructionError> {
let dt = Self::build_with_kernel_inner_seeded(
kernel,
vertices,
topology_guarantee,
0,
true,
grid_cell_size,
use_global_repair_fallback,
)?;
if dt
.tri
.topology_guarantee
.requires_vertex_links_at_completion()
{
tracing::debug!("post-construction: starting topology validation (build)");
let validation_started = Instant::now();
let validation_result = dt.tri.validate();
tracing::debug!(
elapsed = ?validation_started.elapsed(),
success = validation_result.is_ok(),
"post-construction: topology validation (build) completed"
);
if let Err(err) = validation_result {
return Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!("PL-manifold validation failed after construction: {err}"),
}
.into());
}
}
tracing::debug!("post-construction: starting Delaunay validation (build)");
let delaunay_started = Instant::now();
let delaunay_result = dt.is_valid();
tracing::debug!(
elapsed = ?delaunay_started.elapsed(),
success = delaunay_result.is_ok(),
"post-construction: Delaunay validation (build) completed"
);
delaunay_result.map_err(|err| TriangulationConstructionError::GeometricDegeneracy {
message: format!("Delaunay property violated after construction: {err}"),
})?;
Ok(dt)
}
#[expect(
clippy::result_large_err,
reason = "Internal helper propagates public by-value construction-statistics error type"
)]
fn build_with_kernel_inner_with_construction_statistics(
kernel: K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
grid_cell_size: Option<K::Scalar>,
use_global_repair_fallback: bool,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
let (dt, stats) = Self::build_with_kernel_inner_seeded_with_construction_statistics(
kernel,
vertices,
topology_guarantee,
0,
true,
grid_cell_size,
use_global_repair_fallback,
)?;
if dt
.tri
.topology_guarantee
.requires_vertex_links_at_completion()
{
tracing::debug!("post-construction: starting topology validation (build stats)");
let validation_started = Instant::now();
let validation_result = dt.tri.validate();
tracing::debug!(
elapsed = ?validation_started.elapsed(),
success = validation_result.is_ok(),
"post-construction: topology validation (build stats) completed"
);
if let Err(err) = validation_result {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: TriangulationConstructionError::GeometricDegeneracy {
message: format!("PL-manifold validation failed after construction: {err}"),
}
.into(),
statistics: stats,
});
}
}
tracing::debug!("post-construction: starting Delaunay validation (build stats)");
let delaunay_started = Instant::now();
let delaunay_result = dt.is_valid();
tracing::debug!(
elapsed = ?delaunay_started.elapsed(),
success = delaunay_result.is_ok(),
"post-construction: Delaunay validation (build stats) completed"
);
if let Err(err) = delaunay_result {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: TriangulationConstructionError::GeometricDegeneracy {
message: format!("Delaunay property violated after construction: {err}"),
}
.into(),
statistics: stats,
});
}
Ok((dt, stats))
}
#[expect(
clippy::result_large_err,
reason = "Internal helper propagates public by-value construction-statistics error type"
)]
fn build_with_kernel_inner_seeded_with_construction_statistics(
kernel: K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
perturbation_seed: u64,
run_final_repair: bool,
grid_cell_size: Option<K::Scalar>,
use_global_repair_fallback: bool,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
if vertices.len() < D + 1 {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: TriangulationConstructionError::InsufficientVertices {
dimension: D,
source: crate::core::cell::CellValidationError::InsufficientVertices {
actual: vertices.len(),
expected: D + 1,
dimension: D,
},
}
.into(),
statistics: ConstructionStatistics::default(),
});
}
let initial_vertices = &vertices[..=D];
let tds = Triangulation::<K, U, V, D>::build_initial_simplex(initial_vertices).map_err(
|error| DelaunayTriangulationConstructionErrorWithStatistics {
error: error.into(),
statistics: ConstructionStatistics::default(),
},
)?;
let mut dt = Self {
tri: Triangulation {
kernel,
tds,
global_topology: GlobalTopology::DEFAULT,
validation_policy: ValidationPolicy::default(),
topology_guarantee,
},
insertion_state: DelaunayInsertionState::new(),
spatial_index: None,
};
let original_validation_policy = dt.tri.validation_policy;
dt.tri.validation_policy = if dt
.tri
.topology_guarantee
.requires_vertex_links_during_insertion()
{
ValidationPolicy::Always
} else if dt.tri.topology_guarantee.requires_ridge_links() {
ValidationPolicy::OnSuspicion
} else {
ValidationPolicy::DebugOnly
};
let original_repair_policy = dt.insertion_state.delaunay_repair_policy;
dt.insertion_state.delaunay_repair_policy = DelaunayRepairPolicy::Never;
dt.insertion_state.use_global_repair_fallback = use_global_repair_fallback;
let mut stats = ConstructionStatistics::default();
let simplex_stats = InsertionStatistics {
attempts: 1,
..InsertionStatistics::default()
};
for _ in 0..=D {
stats.record_insertion(&simplex_stats);
}
let mut soft_fail_seeds: Vec<CellKey> = Vec::new();
if let Err(error) = dt.insert_remaining_vertices_seeded(
vertices,
perturbation_seed,
grid_cell_size,
Some(&mut stats),
&mut soft_fail_seeds,
) {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: stats,
});
}
if let Err(error) = dt.finalize_bulk_construction(
original_validation_policy,
original_repair_policy,
run_final_repair,
&soft_fail_seeds,
) {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: stats,
});
}
Ok((dt, stats))
}
fn build_with_kernel_inner_seeded(
kernel: K,
vertices: &[Vertex<K::Scalar, U, D>],
topology_guarantee: TopologyGuarantee,
perturbation_seed: u64,
run_final_repair: bool,
grid_cell_size: Option<K::Scalar>,
use_global_repair_fallback: bool,
) -> Result<Self, DelaunayTriangulationConstructionError> {
if vertices.len() < D + 1 {
return Err(TriangulationConstructionError::InsufficientVertices {
dimension: D,
source: crate::core::cell::CellValidationError::InsufficientVertices {
actual: vertices.len(),
expected: D + 1,
dimension: D,
},
}
.into());
}
let initial_vertices = &vertices[..=D];
let tds = Triangulation::<K, U, V, D>::build_initial_simplex(initial_vertices)?;
let mut dt = Self {
tri: Triangulation {
kernel,
tds,
global_topology: GlobalTopology::DEFAULT,
validation_policy: ValidationPolicy::default(),
topology_guarantee,
},
insertion_state: DelaunayInsertionState::new(),
spatial_index: None,
};
let original_validation_policy = dt.tri.validation_policy;
dt.tri.validation_policy = if dt
.tri
.topology_guarantee
.requires_vertex_links_during_insertion()
{
ValidationPolicy::Always
} else if dt.tri.topology_guarantee.requires_ridge_links() {
ValidationPolicy::OnSuspicion
} else {
ValidationPolicy::DebugOnly
};
let original_repair_policy = dt.insertion_state.delaunay_repair_policy;
dt.insertion_state.delaunay_repair_policy = DelaunayRepairPolicy::Never;
dt.insertion_state.use_global_repair_fallback = use_global_repair_fallback;
let mut soft_fail_seeds: Vec<CellKey> = Vec::new();
dt.insert_remaining_vertices_seeded(
vertices,
perturbation_seed,
grid_cell_size,
None,
&mut soft_fail_seeds,
)?;
dt.finalize_bulk_construction(
original_validation_policy,
original_repair_policy,
run_final_repair,
&soft_fail_seeds,
)?;
Ok(dt)
}
fn try_d_lt4_global_repair_fallback(
tds: &mut Tds<K::Scalar, U, V, D>,
kernel: &K,
topology: TopologyGuarantee,
use_global_repair_fallback: bool,
index: usize,
repair_err: &DelaunayRepairError,
) -> Result<(), DelaunayTriangulationConstructionError> {
if use_global_repair_fallback {
tracing::debug!(
error = %repair_err,
idx = index,
"bulk D<4: local repair cycling; falling back to global repair"
);
let global_result = repair_delaunay_with_flips_k2_k3(tds, kernel, None, topology, None);
if let Err(global_err) = global_result {
tracing::debug!(
error = %global_err,
idx = index,
"bulk D<4: global repair also failed; aborting this vertex ordering"
);
return Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"per-insertion Delaunay repair failed at index {index}: local error: {repair_err}; global fallback: {global_err}"
),
}
.into());
}
return Ok(());
}
tracing::debug!(
error = %repair_err,
idx = index,
"bulk D<4: local repair cycling (global fallback disabled); aborting"
);
Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!("per-insertion Delaunay repair failed at index {index}: {repair_err}"),
}
.into())
}
#[allow(clippy::too_many_lines)]
fn insert_remaining_vertices_seeded(
&mut self,
vertices: &[Vertex<K::Scalar, U, D>],
perturbation_seed: u64,
grid_cell_size: Option<K::Scalar>,
construction_stats: Option<&mut ConstructionStatistics>,
soft_fail_seeds: &mut Vec<CellKey>,
) -> Result<(), DelaunayTriangulationConstructionError> {
let mut grid_index = grid_cell_size.map(HashGridIndex::new);
if let Some(grid) = grid_index.as_mut()
&& !grid.is_usable()
{
grid_index = None;
}
if let Some(grid_index) = grid_index.as_mut() {
for (vkey, vertex) in self.tri.tds.vertices() {
grid_index.insert_vertex(vkey, vertex.point().coords());
}
}
let trace_insertion = std::env::var_os("DELAUNAY_INSERT_TRACE").is_some();
match construction_stats {
None => {
for (offset, vertex) in vertices.iter().skip(D + 1).enumerate() {
let index = (D + 1).saturating_add(offset);
let uuid = vertex.uuid();
let coords = trace_insertion.then(|| {
vertex
.point()
.coords()
.iter()
.map(|c| c.to_f64().unwrap_or(f64::NAN))
.collect::<Vec<f64>>()
});
if trace_insertion && let Some(coords) = coords.as_ref() {
eprintln!("[bulk] start idx={index} uuid={uuid} coords={coords:?}");
}
let started = trace_insertion.then(std::time::Instant::now);
let mut insert = || {
self.tri.insert_with_statistics_seeded_indexed(
*vertex,
None,
self.insertion_state.last_inserted_cell,
perturbation_seed,
grid_index.as_mut(),
)
};
let insert_result = if trace_insertion {
let span = tracing::warn_span!(
"bulk_insert",
index,
uuid = %uuid,
coords = ?coords
);
span.in_scope(insert)
} else {
insert()
};
let elapsed = started.map(|started| started.elapsed());
match insert_result {
Ok((
InsertionOutcome::Inserted {
vertex_key: v_key,
hint,
},
_stats,
)) => {
if trace_insertion && let Some(elapsed) = elapsed {
eprintln!(
"[bulk] inserted idx={index} uuid={uuid} elapsed={elapsed:?}"
);
}
self.insertion_state.last_inserted_cell = hint;
self.insertion_state.delaunay_repair_insertion_count = self
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
let topology = self.tri.topology_guarantee();
if D >= 2
&& TopologicalOperation::FacetFlip.is_admissible_under(topology)
&& self.tri.tds.number_of_cells() > 0
{
let seed_cells: Vec<CellKey> =
self.tri.adjacent_cells(v_key).collect();
if !seed_cells.is_empty() {
let max_flips = if D >= 4 {
(seed_cells.len() * (D + 1) * 2).max(8)
} else {
(seed_cells.len() * (D + 1) * 4).max(16)
};
let repair_result = {
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_local_single_pass(
tds,
kernel,
&seed_cells,
max_flips,
)
};
if let Err(repair_err) = repair_result {
if D < 4 {
Self::try_d_lt4_global_repair_fallback(
&mut self.tri.tds,
&self.tri.kernel,
topology,
self.insertion_state.use_global_repair_fallback,
index,
&repair_err,
)?;
continue;
}
tracing::debug!(
error = %repair_err,
idx = index,
"bulk D≥4: per-insertion repair non-convergent; \
continuing (both_positive_artifact handled)"
);
soft_fail_seeds.extend(seed_cells.iter().copied());
}
}
}
}
Ok((InsertionOutcome::Skipped { error }, stats)) => {
if trace_insertion && let Some(elapsed) = elapsed {
eprintln!(
"[bulk] skipped idx={index} uuid={uuid} attempts={} elapsed={elapsed:?} err={error}",
stats.attempts
);
}
#[cfg(debug_assertions)]
tracing::debug!(
attempts = stats.attempts,
error = %error,
"SKIPPED: vertex insertion during construction"
);
#[cfg(not(debug_assertions))]
{
let _ = (error, stats);
}
}
Err(e) => {
if trace_insertion && let Some(elapsed) = elapsed {
eprintln!(
"[bulk] failed idx={index} uuid={uuid} elapsed={elapsed:?} err={e}"
);
}
return Err(Self::map_insertion_error(e).into());
}
}
}
}
Some(construction_stats) => {
for (offset, vertex) in vertices.iter().skip(D + 1).enumerate() {
let index = (D + 1).saturating_add(offset);
let uuid = vertex.uuid();
let coords = trace_insertion.then(|| {
vertex
.point()
.coords()
.iter()
.map(|c| c.to_f64().unwrap_or(f64::NAN))
.collect::<Vec<f64>>()
});
if trace_insertion && let Some(coords) = coords.as_ref() {
eprintln!("[bulk] start idx={index} uuid={uuid} coords={coords:?}");
}
let started = trace_insertion.then(std::time::Instant::now);
let mut insert = || {
self.tri.insert_with_statistics_seeded_indexed(
*vertex,
None,
self.insertion_state.last_inserted_cell,
perturbation_seed,
grid_index.as_mut(),
)
};
let insert_result = if trace_insertion {
let span = tracing::warn_span!(
"bulk_insert",
index,
uuid = %uuid,
coords = ?coords
);
span.in_scope(insert)
} else {
insert()
};
let elapsed = started.map(|started| started.elapsed());
match insert_result {
Ok((
InsertionOutcome::Inserted {
vertex_key: v_key,
hint,
},
stats,
)) => {
if trace_insertion && let Some(elapsed) = elapsed {
eprintln!(
"[bulk] inserted idx={index} uuid={uuid} attempts={} elapsed={elapsed:?}",
stats.attempts
);
}
construction_stats.record_insertion(&stats);
self.insertion_state.last_inserted_cell = hint;
self.insertion_state.delaunay_repair_insertion_count = self
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
let topology = self.tri.topology_guarantee();
if D >= 2
&& TopologicalOperation::FacetFlip.is_admissible_under(topology)
&& self.tri.tds.number_of_cells() > 0
{
let seed_cells: Vec<CellKey> =
self.tri.adjacent_cells(v_key).collect();
if !seed_cells.is_empty() {
let max_flips = if D >= 4 {
(seed_cells.len() * (D + 1) * 2).max(8)
} else {
(seed_cells.len() * (D + 1) * 4).max(16)
};
let repair_result = {
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_local_single_pass(
tds,
kernel,
&seed_cells,
max_flips,
)
};
if let Err(repair_err) = repair_result {
if D < 4 {
Self::try_d_lt4_global_repair_fallback(
&mut self.tri.tds,
&self.tri.kernel,
topology,
self.insertion_state.use_global_repair_fallback,
index,
&repair_err,
)?;
continue;
}
tracing::debug!(
error = %repair_err,
idx = index,
"bulk D≥4: per-insertion repair non-convergent; \
continuing (both_positive_artifact handled)"
);
soft_fail_seeds.extend(seed_cells.iter().copied());
}
}
}
}
Ok((InsertionOutcome::Skipped { error }, stats)) => {
if trace_insertion && let Some(elapsed) = elapsed {
eprintln!(
"[bulk] skipped idx={index} uuid={uuid} attempts={} elapsed={elapsed:?} err={error}",
stats.attempts
);
}
construction_stats.record_insertion(&stats);
let coords: Vec<f64> = vertex
.point()
.coords()
.iter()
.map(|c| c.to_f64().unwrap_or(f64::NAN))
.collect();
construction_stats.record_skip_sample(ConstructionSkipSample {
index,
uuid: vertex.uuid(),
coords,
attempts: stats.attempts,
error: error.to_string(),
});
#[cfg(debug_assertions)]
tracing::debug!(
attempts = stats.attempts,
error = %error,
"SKIPPED: vertex insertion during construction"
);
#[cfg(not(debug_assertions))]
{
let _ = (error, stats);
}
}
Err(e) => {
if trace_insertion && let Some(elapsed) = elapsed {
eprintln!(
"[bulk] failed idx={index} uuid={uuid} elapsed={elapsed:?} err={e}"
);
}
return Err(Self::map_insertion_error(e).into());
}
}
}
}
}
self.spatial_index = grid_index;
Ok(())
}
fn finalize_bulk_construction(
&mut self,
original_validation_policy: ValidationPolicy,
original_repair_policy: DelaunayRepairPolicy,
run_final_repair: bool,
soft_fail_seeds: &[CellKey],
) -> Result<(), DelaunayTriangulationConstructionError> {
self.tri.validation_policy = original_validation_policy;
self.insertion_state.delaunay_repair_policy = original_repair_policy;
let topology = self.tri.topology_guarantee();
if run_final_repair && self.should_run_delaunay_repair_for(topology, 0) {
if D >= 4 {
let cell_count = self.tri.tds.number_of_cells();
if cell_count > 0 {
let all_cells: Vec<CellKey> = self.tri.tds.cell_keys().collect();
tracing::debug!(
cell_count,
"post-construction: starting global D≥4 finalize repair"
);
let repair_started = Instant::now();
let repair_result = {
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_local_single_pass(tds, kernel, &all_cells, 512).map(|_| ())
};
tracing::debug!(
elapsed = ?repair_started.elapsed(),
success = repair_result.is_ok(),
"post-construction: D≥4 finalize repair completed (soft-fail)"
);
}
} else if !soft_fail_seeds.is_empty() {
tracing::debug!(
seed_count = soft_fail_seeds.len(),
"post-construction: starting seeded D<4 finalize repair"
);
let repair_started = Instant::now();
let max_flips = (soft_fail_seeds.len() * (D + 1) * 16).max(512);
let repair_result = {
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_local_single_pass(tds, kernel, soft_fail_seeds, max_flips)
.map(|_| ())
};
let repair_outcome: Result<(), DelaunayTriangulationConstructionError> =
match repair_result {
Ok(()) => Ok(()),
Err(e) => Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!("Delaunay repair failed after construction: {e}"),
}
.into()),
};
tracing::debug!(
elapsed = ?repair_started.elapsed(),
success = repair_outcome.is_ok(),
"post-construction: D<4 finalize repair completed"
);
repair_outcome?;
}
}
self.tri
.normalize_and_promote_positive_orientation()
.map_err(Self::map_orientation_canonicalization_error)?;
if topology.requires_vertex_links_at_completion() {
tracing::debug!("post-construction: starting topology validation (finalize)");
let validation_started = Instant::now();
let validation_result = self.tri.validate();
tracing::debug!(
elapsed = ?validation_started.elapsed(),
success = validation_result.is_ok(),
"post-construction: topology validation (finalize) completed"
);
if let Err(err) = validation_result {
return Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!("PL-manifold validation failed after construction: {err}"),
}
.into());
}
}
Ok(())
}
fn map_orientation_canonicalization_error(
error: InsertionError,
) -> TriangulationConstructionError {
match error {
InsertionError::Construction(source) => source,
InsertionError::TopologyValidation(error @ TdsError::Geometric(_)) => {
TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Failed to canonicalize orientation after post-construction repair: {error}"
),
}
}
error @ (InsertionError::TopologyValidation(_)
| InsertionError::TopologyValidationFailed { .. }
| InsertionError::CavityFilling { .. }
| InsertionError::NeighborWiring { .. }
| InsertionError::DuplicateUuid { .. }) => {
TriangulationConstructionError::InternalInconsistency {
message: format!(
"Failed to canonicalize orientation after post-construction repair: {error}"
),
}
}
error @ (InsertionError::ConflictRegion(_)
| InsertionError::Location(_)
| InsertionError::NonManifoldTopology { .. }
| InsertionError::HullExtension { .. }
| InsertionError::DelaunayValidationFailed { .. }
| InsertionError::DelaunayRepairFailed { .. }
| InsertionError::DuplicateCoordinates { .. }) => {
TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Failed to canonicalize orientation after post-construction repair: {error}"
),
}
}
}
}
fn map_insertion_error(error: InsertionError) -> TriangulationConstructionError {
match error {
InsertionError::Construction(source) => source,
InsertionError::CavityFilling { message } => {
TriangulationConstructionError::FailedToCreateCell { message }
}
InsertionError::NeighborWiring { message } => {
TriangulationConstructionError::InternalInconsistency {
message: format!("Neighbor wiring failed: {message}"),
}
}
InsertionError::TopologyValidation(source) => {
TriangulationConstructionError::from(TdsConstructionError::ValidationError(source))
}
InsertionError::DuplicateUuid { entity, uuid } => {
TriangulationConstructionError::from(TdsConstructionError::DuplicateUuid {
entity,
uuid,
})
}
InsertionError::DuplicateCoordinates { coordinates } => {
TriangulationConstructionError::DuplicateCoordinates { coordinates }
}
insertion_error @ (InsertionError::ConflictRegion(_)
| InsertionError::Location(_)
| InsertionError::NonManifoldTopology { .. }
| InsertionError::HullExtension { .. }
| InsertionError::DelaunayValidationFailed { .. }
| InsertionError::DelaunayRepairFailed { .. }
| InsertionError::TopologyValidationFailed { .. }) => {
TriangulationConstructionError::GeometricDegeneracy {
message: insertion_error.to_string(),
}
}
}
}
#[must_use]
pub fn number_of_vertices(&self) -> usize {
self.tri.number_of_vertices()
}
#[must_use]
pub fn number_of_cells(&self) -> usize {
self.tri.number_of_cells()
}
#[must_use]
pub fn dim(&self) -> i32 {
self.tri.dim()
}
pub fn cells(&self) -> impl Iterator<Item = (CellKey, &Cell<K::Scalar, U, V, D>)> {
self.tri.tds.cells()
}
pub fn vertices(&self) -> impl Iterator<Item = (VertexKey, &Vertex<K::Scalar, U, D>)> {
self.tri.vertices()
}
#[inline]
pub fn set_vertex_data(&mut self, key: VertexKey, data: Option<U>) -> Option<Option<U>> {
self.tri.tds.set_vertex_data(key, data)
}
#[inline]
pub fn set_cell_data(&mut self, key: CellKey, data: Option<V>) -> Option<Option<V>> {
self.tri.tds.set_cell_data(key, data)
}
#[must_use]
pub const fn tds(&self) -> &Tds<K::Scalar, U, V, D> {
&self.tri.tds
}
#[cfg(test)]
pub(crate) fn tds_mut(&mut self) -> &mut Tds<K::Scalar, U, V, D> {
self.insertion_state.last_inserted_cell = None;
self.spatial_index = None;
&mut self.tri.tds
}
#[must_use]
pub const fn as_triangulation(&self) -> &Triangulation<K, U, V, D> {
&self.tri
}
#[must_use]
pub fn as_triangulation_mut(&mut self) -> &mut Triangulation<K, U, V, D> {
self.insertion_state.last_inserted_cell = None;
self.spatial_index = None;
&mut self.tri
}
#[inline]
#[must_use]
pub const fn validation_policy(&self) -> ValidationPolicy {
self.tri.validation_policy
}
#[inline]
pub fn set_validation_policy(&mut self, policy: ValidationPolicy) {
self.tri.set_validation_policy(policy);
}
#[inline]
#[must_use]
pub const fn delaunay_repair_policy(&self) -> DelaunayRepairPolicy {
self.insertion_state.delaunay_repair_policy
}
#[inline]
pub const fn set_delaunay_repair_policy(&mut self, policy: DelaunayRepairPolicy) {
self.insertion_state.delaunay_repair_policy = policy;
}
#[inline]
#[must_use]
pub const fn delaunay_check_policy(&self) -> DelaunayCheckPolicy {
self.insertion_state.delaunay_check_policy
}
#[inline]
pub const fn set_delaunay_check_policy(&mut self, policy: DelaunayCheckPolicy) {
self.insertion_state.delaunay_check_policy = policy;
}
pub fn repair_delaunay_with_flips(&mut self) -> Result<DelaunayRepairStats, DelaunayRepairError>
where
K: ExactPredicates,
{
self.repair_delaunay_with_flips_capped(None)
}
fn repair_delaunay_with_flips_capped(
&mut self,
max_flips: Option<usize>,
) -> Result<DelaunayRepairStats, DelaunayRepairError>
where
K: ExactPredicates,
{
#[cfg(test)]
if tests::force_repair_nonconvergent_enabled() {
return Err(tests::synthetic_nonconvergent_error());
}
let operation = TopologicalOperation::FacetFlip;
let topology = self.tri.topology_guarantee();
if !operation.is_admissible_under(topology) {
return Err(DelaunayRepairError::InvalidTopology {
required: operation.required_topology(),
found: topology,
message: "Bistellar flips require a PL-manifold (vertex-link validation)",
});
}
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
let stats = repair_delaunay_with_flips_k2_k3(tds, kernel, None, topology, max_flips)?;
self.ensure_positive_orientation()?;
Ok(stats)
}
fn ensure_positive_orientation(&mut self) -> Result<(), DelaunayRepairError> {
self.tri
.normalize_and_promote_positive_orientation()
.map_err(|e| DelaunayRepairError::PostconditionFailed {
message: format!("Orientation canonicalization failed after repair: {e}"),
})
}
fn repair_delaunay_with_flips_robust(
&mut self,
seed_cells: Option<&[CellKey]>,
max_flips: Option<usize>,
) -> Result<DelaunayRepairStats, DelaunayRepairError> {
let topology = self.tri.topology_guarantee();
let kernel = RobustKernel::<K::Scalar>::new();
let (tds, kernel) = (&mut self.tri.tds, &kernel);
repair_delaunay_with_flips_k2_k3(tds, kernel, seed_cells, topology, max_flips)
}
fn should_run_delaunay_repair_for(
&self,
topology: TopologyGuarantee,
insertion_count: usize,
) -> bool {
if D < 2 {
return false;
}
if self.tri.tds.number_of_cells() == 0 {
return false;
}
let policy = self.insertion_state.delaunay_repair_policy;
if policy == DelaunayRepairPolicy::Never {
return false;
}
matches!(
policy.decide(insertion_count, topology, TopologicalOperation::FacetFlip),
RepairDecision::Proceed
)
}
#[allow(clippy::missing_const_for_fn)]
fn force_heuristic_rebuild_enabled() -> bool {
#[cfg(test)]
{
FORCE_HEURISTIC_REBUILD.with(std::cell::Cell::get)
}
#[cfg(not(test))]
{
false
}
}
pub fn repair_delaunay_with_flips_advanced(
&mut self,
config: DelaunayRepairHeuristicConfig,
) -> Result<DelaunayRepairOutcome, DelaunayRepairError>
where
K: ExactPredicates,
{
if Self::force_heuristic_rebuild_enabled() {
let base_seed = self.heuristic_rebuild_base_seed();
let seeds = config.resolve_seeds(base_seed);
let (candidate, stats, used_seeds) =
self.rebuild_with_heuristic(seeds, config.max_flips)?;
*self = candidate;
return Ok(DelaunayRepairOutcome {
stats,
heuristic: Some(used_seeds),
});
}
let max_flips = config.max_flips;
match self.repair_delaunay_with_flips_capped(max_flips) {
Ok(stats) => Ok(DelaunayRepairOutcome {
stats,
heuristic: None,
}),
Err(
primary_err @ (DelaunayRepairError::NonConvergent { .. }
| DelaunayRepairError::PostconditionFailed { .. }),
) => {
match self.repair_delaunay_with_flips_robust(None, max_flips) {
Ok(stats) => {
self.ensure_positive_orientation()?;
Ok(DelaunayRepairOutcome {
stats,
heuristic: None,
})
}
Err(robust_err) => {
let base_seed = self.heuristic_rebuild_base_seed();
let seeds = config.resolve_seeds(base_seed);
let (candidate, stats, used_seeds) = self
.rebuild_with_heuristic(seeds, max_flips)
.map_err(|heuristic_err| {
let heuristic_message = match heuristic_err {
DelaunayRepairError::HeuristicRebuildFailed { message } => {
message
}
other => other.to_string(),
};
DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"primary repair failed ({primary_err}); robust fallback failed ({robust_err}); {heuristic_message}"
),
}
})?;
*self = candidate;
Ok(DelaunayRepairOutcome {
stats,
heuristic: Some(used_seeds),
})
}
}
}
Err(err) => Err(err),
}
}
#[allow(clippy::too_many_lines)]
fn rebuild_with_heuristic(
&self,
base_seeds: DelaunayRepairHeuristicSeeds,
max_flips_override: Option<usize>,
) -> Result<(Self, DelaunayRepairStats, DelaunayRepairHeuristicSeeds), DelaunayRepairError>
where
K: ExactPredicates,
{
use rand::{SeedableRng, seq::SliceRandom};
let base_vertices = self.collect_vertices_for_rebuild();
let mut last_error: Option<String> = None;
for attempt in 0..HEURISTIC_REBUILD_ATTEMPTS {
let seeds = if attempt == 0 {
base_seeds
} else {
const SHUFFLE_SALT: u64 = 0x9E37_79B9_7F4A_7C15;
const PERTURB_SALT: u64 = 0xD1B5_4A32_D192_ED03;
let attempt_u64 = attempt as u64;
let mut shuffle_seed = base_seeds
.shuffle_seed
.wrapping_add(attempt_u64.wrapping_mul(SHUFFLE_SALT));
if shuffle_seed == 0 {
shuffle_seed = 1;
}
let mut perturbation_seed =
base_seeds.perturbation_seed ^ attempt_u64.wrapping_mul(PERTURB_SALT);
if perturbation_seed == 0 {
perturbation_seed = 1;
}
DelaunayRepairHeuristicSeeds {
shuffle_seed,
perturbation_seed,
}
};
let rebuild_attempt = (|| {
let _guard = HeuristicRebuildRecursionGuard::enter();
let mut vertices = base_vertices.clone();
let mut rng = rand::rngs::StdRng::seed_from_u64(seeds.shuffle_seed);
vertices.shuffle(&mut rng);
let topology = self.tri.topology_guarantee();
let mut candidate = Self::with_empty_kernel_and_topology_guarantee(
self.tri.kernel.clone(),
topology,
);
let rebuild_repair_policy = candidate.insertion_state.delaunay_repair_policy;
let rebuild_check_policy = candidate.insertion_state.delaunay_check_policy;
candidate.insertion_state.delaunay_repair_policy =
DelaunayRepairPolicy::EveryInsertion;
candidate.insertion_state.delaunay_check_policy = DelaunayCheckPolicy::EndOnly;
for (idx, vertex) in vertices.into_iter().enumerate() {
let uuid = vertex.uuid();
let coords = *vertex.point().coords();
let hint = candidate.insertion_state.last_inserted_cell;
let (outcome, _stats) = {
let (tri, spatial_index) =
(&mut candidate.tri, &mut candidate.spatial_index);
tri.insert_with_statistics_seeded_indexed(
vertex,
None,
hint,
seeds.perturbation_seed,
spatial_index.as_mut(),
)
.map_err(|e| DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"heuristic rebuild insertion failed at idx={idx} uuid={uuid} coords={coords:?}: {e}"
),
})?
};
match outcome {
InsertionOutcome::Inserted { vertex_key, hint } => {
candidate.insertion_state.last_inserted_cell = hint;
candidate.insertion_state.delaunay_repair_insertion_count = candidate
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
candidate
.maybe_repair_after_insertion_capped(
vertex_key,
hint,
max_flips_override,
)
.map_err(|e| DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"heuristic rebuild repair failed at idx={idx} uuid={uuid} coords={coords:?}: {e}"
),
})?;
candidate
.maybe_check_after_insertion()
.map_err(|e| DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"heuristic rebuild Delaunay check failed at idx={idx} uuid={uuid} coords={coords:?}: {e}"
),
})?;
}
InsertionOutcome::Skipped { error } => {
return Err(DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"heuristic rebuild skipped vertex at idx={idx} uuid={uuid} coords={coords:?}: {error}"
),
});
}
}
}
candidate.tri.validation_policy = self.tri.validation_policy;
candidate.insertion_state.delaunay_repair_policy =
self.insertion_state.delaunay_repair_policy;
candidate.insertion_state.delaunay_check_policy =
self.insertion_state.delaunay_check_policy;
candidate.insertion_state.delaunay_repair_insertion_count =
self.insertion_state.delaunay_repair_insertion_count;
candidate.insertion_state.last_inserted_cell = None;
let _ = (rebuild_repair_policy, rebuild_check_policy);
let topology = candidate.tri.topology_guarantee();
let (tds, kernel) = (&mut candidate.tri.tds, &candidate.tri.kernel);
let stats = repair_delaunay_with_flips_k2_k3(
tds,
kernel,
None,
topology,
max_flips_override,
)?;
candidate.ensure_positive_orientation()?;
Ok::<_, DelaunayRepairError>((candidate, stats))
})();
match rebuild_attempt {
Ok((candidate, stats)) => return Ok((candidate, stats, seeds)),
Err(err) => {
last_error = Some(format!(
"attempt {}/{} (shuffle_seed={} perturbation_seed={}): {err}",
attempt + 1,
HEURISTIC_REBUILD_ATTEMPTS,
seeds.shuffle_seed,
seeds.perturbation_seed,
));
}
}
}
Err(DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"heuristic rebuild failed after {HEURISTIC_REBUILD_ATTEMPTS} attempts: {}",
last_error.unwrap_or_else(|| "unknown error".to_string())
),
})
}
fn collect_vertices_for_rebuild(&self) -> Vec<Vertex<K::Scalar, U, D>> {
self.tri
.tds
.vertices()
.map(|(_, vertex)| Vertex::new_with_uuid(*vertex.point(), vertex.uuid(), vertex.data))
.collect()
}
fn heuristic_rebuild_base_seed(&self) -> u64 {
let mut vertex_hashes = Vec::with_capacity(self.tri.tds.number_of_vertices());
for (_, vertex) in self.tri.tds.vertices() {
let mut hasher = FastHasher::default();
vertex.hash(&mut hasher);
vertex_hashes.push(hasher.finish());
}
vertex_hashes.sort_unstable();
stable_hash_u64_slice(&vertex_hashes)
}
#[inline]
#[must_use]
pub const fn topology_guarantee(&self) -> TopologyGuarantee {
self.tri.topology_guarantee()
}
#[inline]
#[must_use]
pub const fn global_topology(&self) -> GlobalTopology<D> {
self.tri.global_topology()
}
#[inline]
#[must_use]
pub const fn topology_kind(&self) -> TopologyKind {
self.tri.topology_kind()
}
#[inline]
pub const fn set_global_topology(&mut self, global_topology: GlobalTopology<D>) {
self.tri.set_global_topology(global_topology);
}
#[inline]
pub fn set_topology_guarantee(&mut self, guarantee: TopologyGuarantee) {
self.tri.set_topology_guarantee(guarantee);
}
pub fn facets(&self) -> AllFacetsIter<'_, K::Scalar, U, V, D> {
self.tri.facets()
}
pub fn boundary_facets(&self) -> BoundaryFacetsIter<'_, K::Scalar, U, V, D> {
self.tri.boundary_facets()
}
#[inline]
pub fn build_adjacency_index(&self) -> Result<AdjacencyIndex, AdjacencyIndexBuildError> {
self.as_triangulation().build_adjacency_index()
}
pub fn edges(&self) -> impl Iterator<Item = EdgeKey> + '_ {
self.as_triangulation().edges()
}
pub fn edges_with_index<'a>(
&self,
index: &'a AdjacencyIndex,
) -> impl Iterator<Item = EdgeKey> + 'a {
self.as_triangulation().edges_with_index(index)
}
pub fn incident_edges(&self, v: VertexKey) -> impl Iterator<Item = EdgeKey> + '_ {
self.as_triangulation().incident_edges(v)
}
pub fn incident_edges_with_index<'a>(
&self,
index: &'a AdjacencyIndex,
v: VertexKey,
) -> impl Iterator<Item = EdgeKey> + 'a {
self.as_triangulation().incident_edges_with_index(index, v)
}
pub fn cell_neighbors(&self, c: CellKey) -> impl Iterator<Item = CellKey> + '_ {
self.as_triangulation().cell_neighbors(c)
}
pub fn cell_neighbors_with_index<'a>(
&self,
index: &'a AdjacencyIndex,
c: CellKey,
) -> impl Iterator<Item = CellKey> + 'a {
self.as_triangulation().cell_neighbors_with_index(index, c)
}
#[must_use]
pub fn cell_vertices(&self, c: CellKey) -> Option<&[VertexKey]> {
self.as_triangulation().cell_vertices(c)
}
#[must_use]
pub fn vertex_coords(&self, v: VertexKey) -> Option<&[K::Scalar]> {
self.as_triangulation().vertex_coords(v)
}
fn ensure_spatial_index_seeded(&mut self) {
if self.spatial_index.is_some() {
return;
}
let duplicate_tolerance: K::Scalar =
<K::Scalar as NumCast>::from(1e-10_f64).unwrap_or_else(K::Scalar::default_tolerance);
let mut index: HashGridIndex<K::Scalar, D> = HashGridIndex::new(duplicate_tolerance);
for (vkey, vertex) in self.tri.tds.vertices() {
index.insert_vertex(vkey, vertex.point().coords());
}
self.spatial_index = Some(index);
}
pub fn insert(&mut self, vertex: Vertex<K::Scalar, U, D>) -> Result<VertexKey, InsertionError> {
self.ensure_spatial_index_seeded();
let next_insertion_count = self
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
let could_have_cells_after_insertion = self.tri.tds.number_of_cells() > 0
|| self.tri.tds.number_of_vertices().saturating_add(1) > D;
let snapshot_needed = could_have_cells_after_insertion
&& (self.insertion_state.delaunay_repair_policy != DelaunayRepairPolicy::Never
|| self
.insertion_state
.delaunay_check_policy
.should_check(next_insertion_count));
let snapshot = snapshot_needed.then(|| {
(
self.tri.tds.clone(),
self.insertion_state,
self.spatial_index.clone(),
)
});
let insertion_result = (|| {
let hint = self.insertion_state.last_inserted_cell;
let (outcome, _stats) = {
let (tri, spatial_index) = (&mut self.tri, &mut self.spatial_index);
tri.insert_with_statistics_seeded_indexed(
vertex,
None,
hint,
0,
spatial_index.as_mut(),
)?
};
match outcome {
InsertionOutcome::Inserted {
vertex_key: v_key,
hint,
} => {
self.insertion_state.last_inserted_cell = hint;
self.insertion_state.delaunay_repair_insertion_count = self
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
self.maybe_repair_after_insertion(v_key, hint)?;
self.maybe_check_after_insertion()?;
Ok(v_key)
}
InsertionOutcome::Skipped { error } => Err(error),
}
})();
match insertion_result {
Ok(v_key) => Ok(v_key),
Err(err) => {
if let Some((tds, insertion_state, spatial_index)) = snapshot {
self.tri.tds = tds;
self.insertion_state = insertion_state;
self.spatial_index = spatial_index;
}
Err(err)
}
}
}
pub fn insert_with_statistics(
&mut self,
vertex: Vertex<K::Scalar, U, D>,
) -> Result<(InsertionOutcome, InsertionStatistics), InsertionError> {
self.ensure_spatial_index_seeded();
let next_insertion_count = self
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
let could_have_cells_after_insertion = self.tri.tds.number_of_cells() > 0
|| self.tri.tds.number_of_vertices().saturating_add(1) > D;
let snapshot_needed = could_have_cells_after_insertion
&& (self.insertion_state.delaunay_repair_policy != DelaunayRepairPolicy::Never
|| self
.insertion_state
.delaunay_check_policy
.should_check(next_insertion_count));
let snapshot = snapshot_needed.then(|| {
(
self.tri.tds.clone(),
self.insertion_state,
self.spatial_index.clone(),
)
});
let insertion_result = (|| {
let hint = self.insertion_state.last_inserted_cell;
let (outcome, stats) = {
let (tri, spatial_index) = (&mut self.tri, &mut self.spatial_index);
tri.insert_with_statistics_seeded_indexed(
vertex,
None,
hint,
0,
spatial_index.as_mut(),
)?
};
let outcome = match outcome {
InsertionOutcome::Inserted { vertex_key, hint } => {
self.insertion_state.last_inserted_cell = hint;
self.insertion_state.delaunay_repair_insertion_count = self
.insertion_state
.delaunay_repair_insertion_count
.saturating_add(1);
self.maybe_repair_after_insertion(vertex_key, hint)?;
self.maybe_check_after_insertion()?;
InsertionOutcome::Inserted { vertex_key, hint }
}
other @ InsertionOutcome::Skipped { .. } => other,
};
Ok((outcome, stats))
})();
match insertion_result {
Ok((outcome, stats)) => Ok((outcome, stats)),
Err(err) => {
if let Some((tds, insertion_state, spatial_index)) = snapshot {
self.tri.tds = tds;
self.insertion_state = insertion_state;
self.spatial_index = spatial_index;
}
Err(err)
}
}
}
fn maybe_repair_after_insertion(
&mut self,
vertex_key: VertexKey,
hint: Option<CellKey>,
) -> Result<(), InsertionError> {
self.maybe_repair_after_insertion_capped(vertex_key, hint, None)
}
fn maybe_repair_after_insertion_capped(
&mut self,
vertex_key: VertexKey,
hint: Option<CellKey>,
max_flips: Option<usize>,
) -> Result<(), InsertionError> {
let topology = self.tri.topology_guarantee();
if !self.should_run_delaunay_repair_for(
topology,
self.insertion_state.delaunay_repair_insertion_count,
) {
return Ok(());
}
let seed_cells: Vec<CellKey> = self.tri.adjacent_cells(vertex_key).collect();
let hint_seed = hint.and_then(|ck| {
if !self.tri.tds.contains_cell(ck) {
if std::env::var_os("DELAUNAY_REPAIR_TRACE").is_some() {
tracing::debug!(
"[repair] insertion seed hint missing (cell={ck:?}, vertex={vertex_key:?})"
);
}
return None;
}
let contains_vertex = self
.tri
.tds
.get_cell(ck)
.is_some_and(|cell| cell.contains_vertex(vertex_key));
if !contains_vertex && std::env::var_os("DELAUNAY_REPAIR_TRACE").is_some() {
tracing::debug!(
"[repair] insertion seed hint does not contain vertex (cell={ck:?}, vertex={vertex_key:?})"
);
}
contains_vertex.then_some(ck)
});
let seed_ref = if seed_cells.is_empty() {
hint_seed.as_ref().map(std::slice::from_ref)
} else {
Some(seed_cells.as_slice())
};
let repair_result = {
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_with_flips_k2_k3(tds, kernel, seed_ref, topology, max_flips).map(|_| ())
};
#[cfg(test)]
let repair_result = if tests::force_repair_nonconvergent_enabled() {
Err(tests::synthetic_nonconvergent_error())
} else {
repair_result
};
match repair_result {
Ok(()) => {}
Err(
e @ (DelaunayRepairError::NonConvergent { .. }
| DelaunayRepairError::PostconditionFailed { .. }),
) => {
self.repair_delaunay_with_flips_robust(seed_ref, max_flips)
.map_err(|robust_err| InsertionError::DelaunayRepairFailed {
source: Box::new(robust_err),
context: format!("local repair failed ({e}); robust fallback also failed"),
})?;
}
Err(e) => {
return Err(InsertionError::DelaunayRepairFailed {
source: Box::new(e),
context: "Delaunay repair failed (non-recoverable)".to_string(),
});
}
}
if topology.requires_ridge_links() {
let local_cells: Vec<CellKey> = self.tri.adjacent_cells(vertex_key).collect();
if !local_cells.is_empty()
&& let Err(err) = validate_ridge_links_for_cells(&self.tri.tds, &local_cells)
{
return Err(InsertionError::TopologyValidationFailed {
message: "Topology invalid after Delaunay repair".to_string(),
source: Box::new(TriangulationValidationError::from(err)),
});
}
}
self.tri.normalize_and_promote_positive_orientation()?;
self.tri
.validate_geometric_cell_orientation()
.map_err(InsertionError::TopologyValidation)?;
Ok(())
}
fn maybe_check_after_insertion(&self) -> Result<(), InsertionError> {
if self.tri.tds.number_of_cells() == 0 {
return Ok(());
}
let policy = self.insertion_state.delaunay_check_policy;
let insertion_count = self.insertion_state.delaunay_repair_insertion_count;
if !policy.should_check(insertion_count) {
return Ok(());
}
self.is_valid()
.map_err(|e| InsertionError::DelaunayValidationFailed {
source: Box::new(e),
})
}
pub fn remove_vertex(
&mut self,
vertex: &Vertex<K::Scalar, U, D>,
) -> Result<usize, InvariantError> {
let Some(vertex_key) = self.tri.tds.vertex_key_from_uuid(&vertex.uuid()) else {
return Ok(0);
};
let mut seed_cells: Option<CellKeyBuffer> = None;
let cells_removed = match apply_bistellar_flip_k1_inverse(&mut self.tri.tds, vertex_key) {
Ok(info) => {
seed_cells = Some(info.new_cells);
info.removed_cells.len()
}
Err(FlipError::NeighborWiring { message }) => {
return Err(TdsError::InvalidNeighbors {
message: format!("inverse k=1 flip failed during remove_vertex: {message}"),
}
.into());
}
Err(_) => self.tri.remove_vertex(vertex)?,
};
let topology = self.tri.topology_guarantee();
if self.should_run_delaunay_repair_for(topology, 0) {
let seed_ref = seed_cells.as_deref();
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_with_flips_k2_k3(tds, kernel, seed_ref, topology, None).map_err(
|e| {
InvariantError::Delaunay(DelaunayTriangulationValidationError::RepairFailed {
message: format!("Delaunay repair failed after vertex removal: {e}"),
})
},
)?;
self.tri
.normalize_and_promote_positive_orientation()
.map_err(|e| {
insertion_error_to_invariant_error(
e,
"Orientation canonicalization failed after vertex removal",
)
})?;
}
Ok(cells_removed)
}
pub fn is_valid(&self) -> Result<(), DelaunayTriangulationValidationError> {
self.is_delaunay_via_flips().map_err(|err| {
DelaunayTriangulationValidationError::VerificationFailed {
message: err.to_string(),
}
})
}
pub fn is_delaunay_via_flips(&self) -> Result<(), DelaunayRepairError> {
crate::core::algorithms::flips::verify_delaunay_via_flip_predicates(
&self.tri.tds,
&self.tri.kernel,
)
}
pub fn validate(&self) -> Result<(), DelaunayTriangulationValidationError> {
self.tri.validate().map_err(|e| match e {
InvariantError::Tds(tds_err) => DelaunayTriangulationValidationError::Tds(tds_err),
InvariantError::Triangulation(tri_err) => {
DelaunayTriangulationValidationError::Triangulation(tri_err)
}
InvariantError::Delaunay(dt_err) => dt_err,
})?;
self.is_valid()
}
#[must_use]
pub const fn from_tds(tds: Tds<K::Scalar, U, V, D>, kernel: K) -> Self {
Self {
tri: Triangulation {
kernel,
tds,
global_topology: GlobalTopology::DEFAULT,
validation_policy: ValidationPolicy::OnSuspicion,
topology_guarantee: TopologyGuarantee::DEFAULT,
},
insertion_state: DelaunayInsertionState::new(),
spatial_index: None,
}
}
#[must_use]
pub const fn from_tds_with_topology_guarantee(
tds: Tds<K::Scalar, U, V, D>,
kernel: K,
topology_guarantee: TopologyGuarantee,
) -> Self {
Self {
tri: Triangulation {
kernel,
tds,
global_topology: GlobalTopology::DEFAULT,
validation_policy: ValidationPolicy::OnSuspicion,
topology_guarantee,
},
insertion_state: DelaunayInsertionState::new(),
spatial_index: None,
}
}
pub fn validation_report(&self) -> Result<(), TriangulationValidationReport> {
match self.tri.validation_report() {
Ok(()) => {
if let Err(e) = self.is_valid() {
return Err(TriangulationValidationReport {
violations: vec![InvariantViolation {
kind: InvariantKind::DelaunayProperty,
error: e.into(),
}],
});
}
Ok(())
}
Err(mut report) => {
if report.violations.iter().any(|v| {
matches!(
v.kind,
InvariantKind::VertexMappings | InvariantKind::CellMappings
)
}) {
return Err(report);
}
if let Err(e) = self.is_valid() {
report.violations.push(InvariantViolation {
kind: InvariantKind::DelaunayProperty,
error: e.into(),
});
}
if report.violations.is_empty() {
Ok(())
} else {
Err(report)
}
}
}
}
}
impl<K, U, V, const D: usize> Serialize for DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
U: DataType,
V: DataType,
{
fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
where
S: Serializer,
{
self.tri.tds.serialize(serializer)
}
}
impl<'de, const D: usize> Deserialize<'de> for DelaunayTriangulation<RobustKernel<f64>, (), (), D>
where
Tds<f64, (), (), D>: Deserialize<'de>,
{
fn deserialize<De>(deserializer: De) -> Result<Self, De::Error>
where
De: Deserializer<'de>,
{
let tds = Tds::deserialize(deserializer)?;
Ok(Self::from_tds(tds, RobustKernel::new()))
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum DelaunayRepairPolicy {
Never,
EveryInsertion,
EveryN(NonZeroUsize),
}
impl Default for DelaunayRepairPolicy {
#[inline]
fn default() -> Self {
Self::EveryInsertion
}
}
impl DelaunayRepairPolicy {
#[inline]
#[must_use]
pub const fn should_repair(self, insertion_count: usize) -> bool {
match self {
Self::Never => false,
Self::EveryInsertion => true,
Self::EveryN(n) => insertion_count.is_multiple_of(n.get()),
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
#[non_exhaustive]
pub struct DelaunayRepairHeuristicConfig {
pub shuffle_seed: Option<u64>,
pub perturbation_seed: Option<u64>,
pub max_flips: Option<usize>,
}
impl DelaunayRepairHeuristicConfig {
fn resolve_seeds(self, base_seed: u64) -> DelaunayRepairHeuristicSeeds {
const SHUFFLE_SALT: u64 = 0x9E37_79B9_7F4A_7C15;
const PERTURB_SALT: u64 = 0xD1B5_4A32_D192_ED03;
let mut shuffle_seed = self
.shuffle_seed
.unwrap_or_else(|| base_seed.wrapping_add(SHUFFLE_SALT));
if self.shuffle_seed.is_none() && shuffle_seed == 0 {
shuffle_seed = 1;
}
let mut perturbation_seed = self
.perturbation_seed
.unwrap_or_else(|| base_seed.rotate_left(17) ^ PERTURB_SALT);
if self.perturbation_seed.is_none() && perturbation_seed == 0 {
perturbation_seed = 1;
}
DelaunayRepairHeuristicSeeds {
shuffle_seed,
perturbation_seed,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct DelaunayRepairHeuristicSeeds {
pub shuffle_seed: u64,
pub perturbation_seed: u64,
}
#[derive(Debug, Clone)]
pub struct DelaunayRepairOutcome {
pub stats: DelaunayRepairStats,
pub heuristic: Option<DelaunayRepairHeuristicSeeds>,
}
impl DelaunayRepairOutcome {
#[must_use]
pub const fn used_heuristic(&self) -> bool {
self.heuristic.is_some()
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum DelaunayCheckPolicy {
#[default]
EndOnly,
EveryN(NonZeroUsize),
}
impl DelaunayCheckPolicy {
#[inline]
#[must_use]
pub const fn should_check(self, insertion_count: usize) -> bool {
match self {
Self::EndOnly => false,
Self::EveryN(n) => insertion_count.is_multiple_of(n.get()),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::core::algorithms::flips::{
DelaunayRepairDiagnostics, DelaunayRepairError, FlipError, RepairQueueOrder,
verify_delaunay_via_flip_predicates,
};
use crate::core::algorithms::incremental_insertion::repair_neighbor_pointers;
use crate::core::triangulation_data_structure::{EntityKind, GeometricError};
use crate::geometry::kernel::{AdaptiveKernel, FastKernel, RobustKernel};
use crate::geometry::traits::coordinate::Coordinate;
use crate::topology::characteristics::euler::TopologyClassification;
use crate::triangulation::flips::BistellarFlips;
use crate::vertex;
pub(super) fn force_repair_nonconvergent_enabled() -> bool {
FORCE_REPAIR_NONCONVERGENT.with(std::cell::Cell::get)
}
pub(super) fn synthetic_nonconvergent_error() -> DelaunayRepairError {
DelaunayRepairError::NonConvergent {
max_flips: 0,
diagnostics: DelaunayRepairDiagnostics {
facets_checked: 0,
flips_performed: 0,
max_queue_len: 0,
ambiguous_predicates: 0,
ambiguous_predicate_samples: Vec::new(),
predicate_failures: 0,
cycle_detections: 0,
cycle_signature_samples: Vec::new(),
attempt: 0,
queue_order: RepairQueueOrder::Fifo,
},
}
}
use rand::{RngExt, SeedableRng};
fn init_tracing() {
static INIT: std::sync::Once = std::sync::Once::new();
INIT.call_once(|| {
let filter = tracing_subscriber::EnvFilter::try_from_default_env()
.unwrap_or_else(|_| tracing_subscriber::EnvFilter::new("warn"));
let _ = tracing_subscriber::fmt()
.with_env_filter(filter)
.with_test_writer()
.try_init();
});
}
struct ForceHeuristicRebuildGuard {
prior: bool,
}
impl ForceHeuristicRebuildGuard {
fn enable() -> Self {
let prior = FORCE_HEURISTIC_REBUILD.with(|flag| {
let prior = flag.get();
flag.set(true);
prior
});
Self { prior }
}
}
impl Drop for ForceHeuristicRebuildGuard {
fn drop(&mut self) {
FORCE_HEURISTIC_REBUILD.with(|flag| flag.set(self.prior));
}
}
struct ForceRepairNonconvergentGuard {
prior: bool,
}
impl ForceRepairNonconvergentGuard {
fn enable() -> Self {
let prior = FORCE_REPAIR_NONCONVERGENT.with(|flag| {
let prior = flag.get();
flag.set(true);
prior
});
Self { prior }
}
}
impl Drop for ForceRepairNonconvergentGuard {
fn drop(&mut self) {
FORCE_REPAIR_NONCONVERGENT.with(|flag| flag.set(self.prior));
}
}
#[test]
fn test_construction_options_builder_roundtrip() {
init_tracing();
let opts = ConstructionOptions::default()
.with_insertion_order(InsertionOrderStrategy::Input)
.with_dedup_policy(DedupPolicy::Exact)
.with_retry_policy(RetryPolicy::Disabled);
assert_eq!(opts.insertion_order(), InsertionOrderStrategy::Input);
assert_eq!(opts.dedup_policy(), DedupPolicy::Exact);
assert_eq!(opts.retry_policy(), RetryPolicy::Disabled);
}
#[test]
fn test_construction_options_global_repair_fallback_toggle() {
init_tracing();
let default_opts = ConstructionOptions::default();
assert!(
default_opts.use_global_repair_fallback,
"default should enable global repair fallback"
);
let disabled_opts = default_opts.without_global_repair_fallback();
assert!(
!disabled_opts.use_global_repair_fallback,
"without_global_repair_fallback should disable the flag"
);
let chained_opts = ConstructionOptions::default()
.with_insertion_order(InsertionOrderStrategy::Input)
.without_global_repair_fallback()
.with_retry_policy(RetryPolicy::Disabled);
assert!(!chained_opts.use_global_repair_fallback);
assert_eq!(
chained_opts.insertion_order(),
InsertionOrderStrategy::Input
);
assert_eq!(chained_opts.retry_policy(), RetryPolicy::Disabled);
}
#[test]
fn test_new_with_options_smoke_3d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let opts = ConstructionOptions::default().with_retry_policy(RetryPolicy::Disabled);
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new_with_options(&vertices, opts).unwrap();
assert_eq!(dt.number_of_vertices(), 4);
assert_eq!(dt.number_of_cells(), 1);
assert!(dt.validate().is_ok());
}
#[test]
fn test_new_with_construction_statistics_counts_initial_simplex_3d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let (dt, stats) =
DelaunayTriangulation::new_with_construction_statistics(&vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 4);
assert_eq!(stats.inserted, 4);
assert_eq!(stats.total_skipped(), 0);
assert_eq!(stats.total_attempts, 4);
assert_eq!(stats.max_attempts, 1);
assert_eq!(stats.attempts_histogram.get(1).copied().unwrap_or(0), 4);
}
#[test]
fn test_new_with_options_and_construction_statistics_skips_duplicate_3d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.0, 0.0, 0.0]),
];
let duplicate_uuid = vertices[4].uuid();
let opts = ConstructionOptions::default()
.with_insertion_order(InsertionOrderStrategy::Input)
.with_retry_policy(RetryPolicy::Disabled);
let (dt, stats) =
DelaunayTriangulation::new_with_options_and_construction_statistics(&vertices, opts)
.unwrap();
assert_eq!(dt.number_of_vertices(), 4);
assert_eq!(stats.inserted, 4);
assert_eq!(stats.skipped_duplicate, 1);
assert_eq!(stats.skipped_degeneracy, 0);
assert_eq!(stats.total_skipped(), 1);
assert_eq!(stats.total_attempts, 5);
assert_eq!(stats.attempts_histogram.get(1).copied().unwrap_or(0), 5);
assert_eq!(stats.skip_samples.len(), 1);
let sample = &stats.skip_samples[0];
assert_eq!(sample.index, 4);
assert_eq!(sample.uuid, duplicate_uuid);
assert_eq!(sample.coords, vec![0.0, 0.0, 0.0]);
assert_eq!(sample.attempts, 1);
assert!(sample.error.contains("Duplicate coordinates"));
}
#[test]
fn test_construction_statistics_record_insertion_tracks_inserted_common_fields() {
init_tracing();
let mut summary = ConstructionStatistics::default();
let stats = InsertionStatistics {
attempts: 3,
cells_removed_during_repair: 4,
result: crate::core::operations::InsertionResult::Inserted,
};
summary.record_insertion(&stats);
assert_eq!(summary.inserted, 1);
assert_eq!(summary.skipped_duplicate, 0);
assert_eq!(summary.skipped_degeneracy, 0);
assert_eq!(summary.total_attempts, 3);
assert_eq!(summary.max_attempts, 3);
assert_eq!(summary.attempts_histogram.get(3).copied().unwrap_or(0), 1);
assert_eq!(summary.used_perturbation, 1);
assert_eq!(summary.cells_removed_total, 4);
assert_eq!(summary.cells_removed_max, 4);
assert_eq!(stats.attempts, 3);
assert!(matches!(
stats.result,
crate::core::operations::InsertionResult::Inserted
));
}
#[test]
fn test_construction_statistics_record_insertion_tracks_skipped_variants() {
init_tracing();
let mut summary = ConstructionStatistics::default();
let skipped_duplicate = InsertionStatistics {
attempts: 1,
cells_removed_during_repair: 0,
result: crate::core::operations::InsertionResult::SkippedDuplicate,
};
let skipped_degeneracy = InsertionStatistics {
attempts: 2,
cells_removed_during_repair: 5,
result: crate::core::operations::InsertionResult::SkippedDegeneracy,
};
summary.record_insertion(&skipped_duplicate);
summary.record_insertion(&skipped_degeneracy);
assert_eq!(summary.inserted, 0);
assert_eq!(summary.skipped_duplicate, 1);
assert_eq!(summary.skipped_degeneracy, 1);
assert_eq!(summary.total_skipped(), 2);
assert_eq!(summary.total_attempts, 3);
assert_eq!(summary.max_attempts, 2);
assert_eq!(summary.attempts_histogram.get(1).copied().unwrap_or(0), 1);
assert_eq!(summary.attempts_histogram.get(2).copied().unwrap_or(0), 1);
assert_eq!(summary.used_perturbation, 1);
assert_eq!(summary.cells_removed_total, 5);
assert_eq!(summary.cells_removed_max, 5);
}
#[test]
fn test_construction_statistics_record_skip_sample_caps_at_eight_samples() {
init_tracing();
let mut summary = ConstructionStatistics::default();
for index in 0..10 {
let sample_index_u32 = u32::try_from(index).unwrap();
let coordinate_base = <f64 as std::convert::From<u32>>::from(sample_index_u32);
summary.record_skip_sample(ConstructionSkipSample {
index,
uuid: Uuid::from_u128(
<u128 as std::convert::From<u32>>::from(sample_index_u32) + 1,
),
coords: vec![
coordinate_base,
coordinate_base + 0.5,
coordinate_base + 1.0,
],
attempts: index + 1,
error: format!("skip sample #{index}"),
});
}
assert_eq!(summary.skip_samples.len(), 8);
assert_eq!(summary.skip_samples.first().map(|s| s.index), Some(0));
assert_eq!(summary.skip_samples.last().map(|s| s.index), Some(7));
assert_eq!(
summary.skip_samples.last().map(|s| s.uuid),
Some(Uuid::from_u128(8))
);
}
#[test]
fn test_select_balanced_simplex_indices_insufficient_vertices() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
];
let result = select_balanced_simplex_indices(&vertices);
assert!(result.is_none());
}
#[test]
fn test_select_balanced_simplex_indices_rejects_non_finite_coords() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
Vertex::new_with_uuid(
crate::geometry::point::Point::new([f64::NAN, 0.0, 0.0]),
Uuid::new_v4(),
None,
),
];
let result = select_balanced_simplex_indices(&vertices);
assert!(result.is_none());
}
#[test]
fn test_reorder_vertices_for_simplex_valid_and_invalid() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([2.0, 2.0, 2.0]),
];
let indices = [2_usize, 0, 3, 1];
let reordered =
reorder_vertices_for_simplex(&vertices, &indices).expect("expected valid reorder");
let expected_first: Vec<[f64; 3]> =
indices.iter().map(|&i| (&vertices[i]).into()).collect();
let actual_first: Vec<[f64; 3]> = reordered.iter().take(4).map(Into::into).collect();
assert_eq!(actual_first, expected_first);
let remaining_expected: Vec<[f64; 3]> = vertices
.iter()
.enumerate()
.filter(|(idx, _)| !indices.contains(idx))
.map(|(_, v)| (*v).into())
.collect();
let remaining_actual: Vec<[f64; 3]> = reordered.iter().skip(4).map(Into::into).collect();
assert_eq!(remaining_actual, remaining_expected);
assert!(reorder_vertices_for_simplex(&vertices, &[0, 1, 2]).is_none());
assert!(reorder_vertices_for_simplex(&vertices, &[0, 1, 1, 2]).is_none());
assert!(reorder_vertices_for_simplex(&vertices, &[0, 1, 2, 99]).is_none());
}
#[test]
fn test_preprocess_vertices_for_construction_balanced_sets_fallback() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([2.0, 2.0, 2.0]),
];
let preprocess = DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::preprocess_vertices_for_construction(
&vertices,
DedupPolicy::Off,
InsertionOrderStrategy::Input,
InitialSimplexStrategy::Balanced,
)
.expect("preprocess failed");
assert!(preprocess.fallback_slice().is_some());
assert_eq!(preprocess.primary_slice(&vertices).len(), vertices.len());
assert_eq!(preprocess.fallback_slice().unwrap().len(), vertices.len());
assert!(preprocess.grid_cell_size().is_some());
}
#[test]
fn test_preprocess_vertices_rejects_invalid_epsilon_tolerance() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let result = DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::preprocess_vertices_for_construction(
&vertices,
DedupPolicy::Epsilon { tolerance: -1.0 },
InsertionOrderStrategy::Input,
InitialSimplexStrategy::First,
);
assert!(matches!(
result,
Err(DelaunayTriangulationConstructionError::Triangulation(
TriangulationConstructionError::GeometricDegeneracy { .. }
))
));
}
fn vertices_from_coords_permutation_3d(
coords: &[[f64; 3]],
permutation: &[usize],
) -> Vec<Vertex<f64, (), 3>> {
permutation.iter().map(|&i| vertex!(coords[i])).collect()
}
#[test]
fn test_bulk_construction_skips_near_duplicate_coordinates_3d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.25, 0.25, 0.25]),
vertex!([0.25 + 5e-11, 0.25, 0.25]),
];
let opts = ConstructionOptions::default()
.with_dedup_policy(DedupPolicy::Epsilon { tolerance: 1e-10 })
.with_retry_policy(RetryPolicy::Disabled);
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new_with_options(&vertices, opts).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
assert!(dt.validate().is_ok());
}
fn coord_sequence_3d(vertices: &[Vertex<f64, (), 3>]) -> Vec<[f64; 3]> {
vertices.iter().map(Into::into).collect()
}
#[test]
fn test_insertion_order_hilbert_is_deterministic_across_permutations_3d() {
init_tracing();
let coords: [[f64; 3]; 8] = [
[0.0, 0.0, 0.0],
[1.0, 0.0, 0.0],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0],
[1.0, 1.0, 1.0],
[2.0, 0.0, 1.0],
[-1.0, 5.0, 0.0],
[3.0, 2.0, 1.0],
];
let permutations: [&[usize]; 4] = [
&[0, 1, 2, 3, 4, 5, 6, 7],
&[7, 6, 5, 4, 3, 2, 1, 0],
&[2, 3, 4, 5, 6, 7, 0, 1],
&[1, 3, 5, 7, 0, 2, 4, 6],
];
let expected_no_dedup = vertices_from_coords_permutation_3d(&coords, permutations[0]);
let expected_no_dedup =
coord_sequence_3d(&order_vertices_hilbert(expected_no_dedup, false));
let expected_dedup = vertices_from_coords_permutation_3d(&coords, permutations[0]);
let expected_dedup = coord_sequence_3d(&order_vertices_hilbert(expected_dedup, true));
for perm in &permutations[1..] {
let vertices = vertices_from_coords_permutation_3d(&coords, perm);
let got = coord_sequence_3d(&order_vertices_hilbert(vertices, false));
assert_eq!(got, expected_no_dedup);
let vertices = vertices_from_coords_permutation_3d(&coords, perm);
let got = coord_sequence_3d(&order_vertices_hilbert(vertices, true));
assert_eq!(got, expected_dedup);
}
}
fn simplex_vertices<const D: usize>() -> Vec<Vertex<f64, (), D>> {
let mut verts = Vec::with_capacity(D + 1);
verts.push(vertex!([0.0; D]));
for i in 0..D {
let mut coords = [0.0; D];
coords[i] = 1.0;
verts.push(vertex!(coords));
}
verts
}
fn simplex_with_duplicates<const D: usize>() -> (Vec<Vertex<f64, (), D>>, usize) {
let mut verts = simplex_vertices::<D>();
let distinct = verts.len();
verts.push(vertex!([0.0; D]));
let mut unit = [0.0; D];
unit[0] = 1.0;
verts.push(vertex!(unit));
(verts, distinct)
}
#[expect(
clippy::cast_precision_loss,
reason = "D ≤ 5 in practice; no precision loss"
)]
fn simplex_with_interior<const D: usize>() -> Vec<Vertex<f64, (), D>> {
let mut verts = simplex_vertices::<D>();
let interior = [0.1_f64 / (D as f64); D];
verts.push(vertex!(interior));
verts
}
macro_rules! gen_hilbert_dedup_tests {
($dim:literal) => {
pastey::paste! {
#[test]
fn [<test_hilbert_sort_dedup_removes_exact_duplicates_ $dim d>]() {
init_tracing();
let (vertices, distinct) = simplex_with_duplicates::<$dim>();
assert!(vertices.len() > distinct);
let result = order_vertices_hilbert(vertices, true);
assert_eq!(
result.len(),
distinct,
"{}D: exact duplicates should be removed",
$dim
);
}
#[test]
fn [<test_hilbert_sort_dedup_preserves_distinct_points_ $dim d>]() {
init_tracing();
let vertices = simplex_with_interior::<$dim>();
let expected = vertices.len();
let result = order_vertices_hilbert(vertices, true);
assert_eq!(
result.len(),
expected,
"{}D: distinct points should all be preserved",
$dim
);
}
#[test]
fn [<test_hilbert_sort_dedup_all_identical_ $dim d>]() {
init_tracing();
let vertices: Vec<Vertex<f64, (), $dim>> = vec![
vertex!([0.5; $dim]),
vertex!([0.5; $dim]),
vertex!([0.5; $dim]),
];
let result = order_vertices_hilbert(vertices, true);
assert_eq!(
result.len(),
1,
"{}D: all-identical inputs should collapse to 1",
$dim
);
}
}
};
}
gen_hilbert_dedup_tests!(2);
gen_hilbert_dedup_tests!(3);
gen_hilbert_dedup_tests!(4);
gen_hilbert_dedup_tests!(5);
#[test]
fn test_hilbert_dedup_empty_input() {
let vertices: Vec<Vertex<f64, (), 3>> = vec![];
let result = order_vertices_hilbert(vertices, true);
assert!(result.is_empty(), "empty input must produce empty output");
}
#[test]
fn test_hilbert_dedup_single_vertex() {
let vertices: Vec<Vertex<f64, (), 3>> = vec![vertex!([1.0, 2.0, 3.0])];
let result = order_vertices_hilbert(vertices, true);
assert_eq!(result.len(), 1, "single vertex must be preserved");
}
#[test]
fn test_hilbert_dedup_already_unique() {
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let n = vertices.len();
let result = order_vertices_hilbert(vertices, true);
assert_eq!(result.len(), n, "already-unique input must be unchanged");
}
#[test]
fn test_new_with_options_hilbert_smoke_3d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.25, 0.25, 0.25]),
];
let opts = ConstructionOptions::default()
.with_insertion_order(InsertionOrderStrategy::Hilbert)
.with_retry_policy(RetryPolicy::Disabled);
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new_with_options(&vertices, opts).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
assert!(dt.validate().is_ok());
}
#[test]
fn test_new_with_options_shuffled_retry_policy_smoke_3d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.25, 0.25, 0.25]),
];
let opts = ConstructionOptions::default()
.with_insertion_order(InsertionOrderStrategy::Input)
.with_retry_policy(RetryPolicy::Shuffled {
attempts: NonZeroUsize::new(2).unwrap(),
base_seed: Some(123),
});
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new_with_options(&vertices, opts).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
assert!(dt.validate().is_ok());
}
#[test]
fn test_delaunay_constructors_default_to_pl_manifold_mode() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt_new: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt_new.topology_guarantee(), TopologyGuarantee::PLManifold);
let dt_empty: DelaunayTriangulation<_, (), (), 2> = DelaunayTriangulation::empty();
assert_eq!(dt_empty.topology_guarantee(), TopologyGuarantee::PLManifold);
let dt_with_kernel: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::with_kernel(&AdaptiveKernel::new(), &vertices).unwrap();
assert_eq!(
dt_with_kernel.topology_guarantee(),
TopologyGuarantee::PLManifold
);
let dt_from_tds: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::from_tds(dt_new.tds().clone(), FastKernel::new());
assert_eq!(
dt_from_tds.topology_guarantee(),
TopologyGuarantee::PLManifold
);
}
#[test]
fn test_set_topology_guarantee_updates_underlying_triangulation() {
init_tracing();
let mut dt: DelaunayTriangulation<_, (), (), 2> = DelaunayTriangulation::empty();
assert_eq!(dt.topology_guarantee(), TopologyGuarantee::PLManifold);
assert_eq!(dt.tri.topology_guarantee, TopologyGuarantee::PLManifold);
dt.set_topology_guarantee(TopologyGuarantee::Pseudomanifold);
assert_eq!(dt.topology_guarantee(), TopologyGuarantee::Pseudomanifold);
assert_eq!(dt.tri.topology_guarantee, TopologyGuarantee::Pseudomanifold);
}
#[test]
fn test_new_with_topology_guarantee_sets_pl() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new_with_topology_guarantee(
&vertices,
TopologyGuarantee::PLManifold,
)
.unwrap();
assert_eq!(dt.topology_guarantee(), TopologyGuarantee::PLManifold);
}
#[test]
fn test_delaunay_check_policy_should_check() {
init_tracing();
assert!(!DelaunayCheckPolicy::EndOnly.should_check(1));
let every_2 = DelaunayCheckPolicy::EveryN(NonZeroUsize::new(2).unwrap());
assert!(!every_2.should_check(1));
assert!(every_2.should_check(2));
assert!(!every_2.should_check(3));
assert!(every_2.should_check(4));
}
#[test]
fn test_set_delaunay_check_policy_updates_state() {
init_tracing();
let mut dt: DelaunayTriangulation<_, (), (), 2> = DelaunayTriangulation::empty();
assert_eq!(dt.delaunay_check_policy(), DelaunayCheckPolicy::EndOnly);
let policy = DelaunayCheckPolicy::EveryN(NonZeroUsize::new(3).unwrap());
dt.set_delaunay_check_policy(policy);
assert_eq!(dt.delaunay_check_policy(), policy);
}
#[test]
fn test_should_run_delaunay_repair_for_skips_for_dimension_lt_2() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 1>> = vec![vertex!([0.0]), vertex!([1.0])];
let dt: DelaunayTriangulation<_, (), (), 1> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_cells(), 1);
assert_eq!(
dt.delaunay_repair_policy(),
DelaunayRepairPolicy::EveryInsertion
);
assert!(!dt.should_run_delaunay_repair_for(dt.topology_guarantee(), 1));
}
#[test]
fn test_should_run_delaunay_repair_for_skips_when_no_cells() {
init_tracing();
let dt: DelaunayTriangulation<_, (), (), 2> = DelaunayTriangulation::empty();
assert_eq!(dt.number_of_cells(), 0);
assert_eq!(
dt.delaunay_repair_policy(),
DelaunayRepairPolicy::EveryInsertion
);
assert!(!dt.should_run_delaunay_repair_for(dt.topology_guarantee(), 1));
}
#[test]
fn test_should_run_delaunay_repair_for_skips_when_policy_never() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_cells(), 1);
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::Never);
assert!(!dt.should_run_delaunay_repair_for(dt.topology_guarantee(), 1));
}
#[test]
fn test_should_run_delaunay_repair_for_respects_every_n_schedule() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::EveryN(NonZeroUsize::new(2).unwrap()));
let topology = dt.topology_guarantee();
assert!(!dt.should_run_delaunay_repair_for(topology, 1));
assert!(dt.should_run_delaunay_repair_for(topology, 2));
}
#[test]
fn test_vertex_key_valid_after_explicit_heuristic_rebuild() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let inserted = vertex!([0.25, 0.25]);
let inserted_uuid = inserted.uuid();
let (outcome, _stats) = dt.insert_with_statistics(inserted).unwrap();
let InsertionOutcome::Inserted { vertex_key, .. } = outcome else {
panic!("Expected successful insertion outcome");
};
let _guard = ForceHeuristicRebuildGuard::enable();
let outcome = dt
.repair_delaunay_with_flips_advanced(DelaunayRepairHeuristicConfig::default())
.unwrap();
assert!(
outcome.used_heuristic(),
"Expected heuristic rebuild to be used"
);
let remapped = dt
.tri
.tds
.vertex_key_from_uuid(&inserted_uuid)
.expect("Inserted vertex UUID missing after heuristic rebuild");
assert!(dt.tri.tds.get_vertex_by_key(remapped).is_some());
assert!(dt.validate().is_ok());
let _ = vertex_key;
}
#[test]
#[ignore = "manual search helper; run explicitly to discover natural repro cases"]
fn find_stale_vertex_key_after_heuristic_rebuild_repro_case() {
const DIM: usize = 4;
const INITIAL_COUNT: usize = 12;
const CASES: usize = 2_000;
init_tracing();
let mut rng = rand::rngs::StdRng::seed_from_u64(0xD3_1A_7A_1C_0A_17_u64);
for case in 0..CASES {
let mut vertices: Vec<Vertex<f64, (), DIM>> = Vec::with_capacity(INITIAL_COUNT);
for _ in 0..INITIAL_COUNT {
let mut coords = [0.0_f64; DIM];
for c in &mut coords {
let base: i32 = rng.random_range(-3..=3);
let noise: f64 = rng.random_range(-1.0e-6..=1.0e-6);
*c = <f64 as std::convert::From<i32>>::from(base) + noise;
}
vertices.push(vertex!(coords));
}
let Ok(mut dt) =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), DIM>::new(&vertices)
else {
continue;
};
let mut inserted_coords = [0.0_f64; DIM];
for c in &mut inserted_coords {
let base: i32 = rng.random_range(-3..=3);
let noise: f64 = rng.random_range(-1.0e-6..=1.0e-6);
*c = <f64 as std::convert::From<i32>>::from(base) + noise;
}
let inserted = vertex!(inserted_coords);
let inserted_uuid = inserted.uuid();
let Ok(vertex_key) = dt.insert(inserted) else {
continue;
};
let found = dt
.tri
.tds
.get_vertex_by_key(vertex_key)
.is_some_and(|v| v.uuid() == inserted_uuid);
if !found {
tracing::debug!(case, "FOUND stale key after insertion");
tracing::debug!(vertex_key = ?vertex_key, inserted_uuid = %inserted_uuid);
tracing::debug!("initial vertices:");
for v in &vertices {
tracing::debug!(coords = ?v.point().coords(), " vertex");
}
tracing::debug!("inserted vertex coords: {inserted_coords:?}");
panic!("stale VertexKey returned from insert() after heuristic rebuild");
}
}
panic!("no stale-key case found after {CASES} attempts");
}
#[test]
fn test_remove_vertex_fast_path_inverse_k1() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.set_topology_guarantee(TopologyGuarantee::PLManifold);
let original_vertex_count = dt.number_of_vertices();
let original_cell_count = dt.number_of_cells();
let cell_key = dt.cells().next().unwrap().0;
let inserted_vertex = vertex!([0.2, 0.2, 0.2]);
let inserted_uuid = inserted_vertex.uuid();
dt.flip_k1_insert(cell_key, inserted_vertex).unwrap();
assert_eq!(dt.number_of_vertices(), original_vertex_count + 1);
assert_eq!(dt.number_of_cells(), original_cell_count + 3);
let vertex_to_remove = dt
.vertices()
.find(|(_, v)| v.uuid() == inserted_uuid)
.map(|(_, v)| *v)
.expect("Inserted vertex not found");
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::Never);
let removed_cells = dt.remove_vertex(&vertex_to_remove).unwrap();
assert_eq!(removed_cells, 4);
assert_eq!(dt.number_of_vertices(), original_vertex_count);
assert_eq!(dt.number_of_cells(), original_cell_count);
assert!(dt.as_triangulation().validate().is_ok());
assert!(dt.vertices().all(|(_, v)| v.uuid() != inserted_uuid));
}
#[test]
fn test_repair_delaunay_with_flips_allows_pl_manifold() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.set_topology_guarantee(TopologyGuarantee::PLManifold);
let result = dt.repair_delaunay_with_flips();
assert!(
!matches!(result, Err(DelaunayRepairError::InvalidTopology { .. })),
"Flip-based repair should be admissible under PLManifold topology"
);
}
#[test]
fn test_repair_delaunay_with_flips_advanced_robust_fallback_succeeds() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let _guard = ForceRepairNonconvergentGuard::enable();
let outcome = dt
.repair_delaunay_with_flips_advanced(DelaunayRepairHeuristicConfig::default())
.unwrap();
assert!(
!outcome.used_heuristic(),
"Robust fallback should succeed without needing heuristic rebuild"
);
}
#[test]
fn test_maybe_repair_after_insertion_robust_fallback_on_forced_nonconvergent() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let _guard = ForceRepairNonconvergentGuard::enable();
let result = dt.insert(vertex!([0.5, 0.5]));
assert!(
result.is_ok(),
"Insertion should succeed via robust fallback: {result:?}"
);
assert!(dt.validate().is_ok());
}
#[test]
fn test_repair_advanced_max_flips_zero_on_valid_triangulation_succeeds() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let config = DelaunayRepairHeuristicConfig {
max_flips: Some(0),
..DelaunayRepairHeuristicConfig::default()
};
let outcome = dt.repair_delaunay_with_flips_advanced(config).unwrap();
assert_eq!(outcome.stats.flips_performed, 0);
assert!(
!outcome.used_heuristic(),
"Already-Delaunay triangulation should not trigger heuristic rebuild"
);
}
#[test]
fn test_repair_advanced_max_flips_zero_forced_nonconvergent_hits_robust_fallback() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let _guard = ForceRepairNonconvergentGuard::enable();
let config = DelaunayRepairHeuristicConfig {
max_flips: Some(0),
..DelaunayRepairHeuristicConfig::default()
};
let outcome = dt.repair_delaunay_with_flips_advanced(config).unwrap();
assert_eq!(
outcome.stats.flips_performed, 0,
"max_flips=0 should prevent any flips even on the robust fallback path"
);
assert!(
!outcome.used_heuristic(),
"Robust fallback should succeed without heuristic rebuild"
);
}
#[test]
fn test_repair_advanced_max_flips_on_non_delaunay_triangulation() {
init_tracing();
let d_candidates = [[0.0, 1.2], [0.1, 1.1], [0.2, 0.9], [-0.1, 1.3]];
let kernel = AdaptiveKernel::<f64>::new();
let mut raw_tds = None;
for d_coords in d_candidates {
let mut candidate: Tds<f64, (), (), 2> = Tds::empty();
let a = candidate
.insert_vertex_with_mapping(vertex!([0.0, 0.0]))
.unwrap();
let b = candidate
.insert_vertex_with_mapping(vertex!([1.0, 1.0]))
.unwrap();
let c = candidate
.insert_vertex_with_mapping(vertex!([1.0, 0.0]))
.unwrap();
let d = candidate
.insert_vertex_with_mapping(vertex!(d_coords))
.unwrap();
let _ = candidate
.insert_cell_with_mapping(Cell::new(vec![a, b, c], None).unwrap())
.unwrap();
let _ = candidate
.insert_cell_with_mapping(Cell::new(vec![a, b, d], None).unwrap())
.unwrap();
repair_neighbor_pointers(&mut candidate).unwrap();
if verify_delaunay_via_flip_predicates(&candidate, &kernel).is_err() {
raw_tds = Some(candidate);
break;
}
}
let tds = raw_tds.expect("need a non-Delaunay 2D config");
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::from_tds(tds, kernel);
dt.set_topology_guarantee(TopologyGuarantee::PLManifold);
let config_zero = DelaunayRepairHeuristicConfig {
max_flips: Some(0),
..DelaunayRepairHeuristicConfig::default()
};
let outcome_zero = dt.repair_delaunay_with_flips_advanced(config_zero);
if let Ok(ref outcome) = outcome_zero {
assert!(
outcome.used_heuristic() || outcome.stats.flips_performed > 0,
"max_flips=0 on non-Delaunay input must not silently succeed with 0 flips and no heuristic"
);
}
let config_generous = DelaunayRepairHeuristicConfig {
max_flips: Some(100),
..DelaunayRepairHeuristicConfig::default()
};
let kernel2 = AdaptiveKernel::<f64>::new();
let mut raw_tds2 = None;
for d_coords in d_candidates {
let mut candidate: Tds<f64, (), (), 2> = Tds::empty();
let a = candidate
.insert_vertex_with_mapping(vertex!([0.0, 0.0]))
.unwrap();
let b = candidate
.insert_vertex_with_mapping(vertex!([1.0, 1.0]))
.unwrap();
let c = candidate
.insert_vertex_with_mapping(vertex!([1.0, 0.0]))
.unwrap();
let d = candidate
.insert_vertex_with_mapping(vertex!(d_coords))
.unwrap();
let _ = candidate
.insert_cell_with_mapping(Cell::new(vec![a, b, c], None).unwrap())
.unwrap();
let _ = candidate
.insert_cell_with_mapping(Cell::new(vec![a, b, d], None).unwrap())
.unwrap();
repair_neighbor_pointers(&mut candidate).unwrap();
if verify_delaunay_via_flip_predicates(&candidate, &kernel2).is_err() {
raw_tds2 = Some(candidate);
break;
}
}
let tds2 = raw_tds2.unwrap();
let mut dt2: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::from_tds(tds2, AdaptiveKernel::new());
dt2.set_topology_guarantee(TopologyGuarantee::PLManifold);
let outcome_generous = dt2
.repair_delaunay_with_flips_advanced(config_generous)
.unwrap();
assert!(
outcome_generous.stats.flips_performed > 0,
"Generous budget should allow flips to repair the non-Delaunay triangulation"
);
}
#[test]
fn test_repair_delaunay_with_flips_returns_flip_error_for_1d() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 1>> = vec![vertex!([0.0]), vertex!([1.0])];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 1> =
DelaunayTriangulation::new(&vertices).unwrap();
let result = dt.repair_delaunay_with_flips();
assert!(
matches!(
result,
Err(DelaunayRepairError::Flip(FlipError::UnsupportedDimension {
dimension: 1
}))
),
"Expected Flip(UnsupportedDimension {{ dimension: 1 }}) for D=1, got: {result:?}"
);
}
#[test]
fn test_repair_delaunay_with_flips_advanced_passes_through_non_retryable_error() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 1>> = vec![vertex!([0.0]), vertex!([1.0])];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 1> =
DelaunayTriangulation::new(&vertices).unwrap();
let result =
dt.repair_delaunay_with_flips_advanced(DelaunayRepairHeuristicConfig::default());
assert!(
matches!(
result,
Err(DelaunayRepairError::Flip(FlipError::UnsupportedDimension {
dimension: 1
}))
),
"Expected non-retryable Flip(UnsupportedDimension) pass-through for D=1, got: {result:?}"
);
}
macro_rules! test_incremental_insertion {
($dim:expr, [$($simplex_coords:expr),+ $(,)?], $interior_point:expr) => {
pastey::paste! {
#[test]
fn [<test_incremental_insertion_ $dim d>]() {
init_tracing();
let mut vertices: Vec<Vertex<f64, (), $dim>> = vec![
$(vertex!($simplex_coords)),+
];
vertices.push(vertex!($interior_point));
let expected_vertices = vertices.len();
let dt: DelaunayTriangulation<_, (), (), $dim> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_vertices(), expected_vertices,
"{}D: Expected {} vertices", $dim, expected_vertices);
assert!(dt.number_of_cells() > 1,
"{}D: Expected multiple cells, got {}", $dim, dt.number_of_cells());
}
#[test]
fn [<test_bootstrap_from_empty_ $dim d>]() {
init_tracing();
let mut dt: DelaunayTriangulation<_, (), (), $dim> = DelaunayTriangulation::empty();
assert_eq!(dt.number_of_vertices(), 0);
assert_eq!(dt.number_of_cells(), 0);
let vertices = vec![$(vertex!($simplex_coords)),+];
assert_eq!(vertices.len(), $dim + 1, "Test should provide exactly D+1 vertices");
for (i, vertex) in vertices.iter().take($dim).enumerate() {
dt.insert(*vertex).unwrap();
assert_eq!(dt.number_of_vertices(), i + 1,
"{}D: After inserting vertex {}, expected {} vertices", $dim, i, i + 1);
assert_eq!(dt.number_of_cells(), 0,
"{}D: Should have 0 cells during bootstrap (have {} vertices < D+1)",
$dim, i + 1);
}
dt.insert(*vertices.last().unwrap()).unwrap();
assert_eq!(dt.number_of_vertices(), $dim + 1);
assert_eq!(dt.number_of_cells(), 1,
"{}D: Should have exactly 1 cell after inserting D+1 vertices", $dim);
assert!(dt.is_valid().is_ok(),
"{}D: Triangulation should be valid after bootstrap", $dim);
}
#[test]
fn [<test_bootstrap_continues_with_cavity_ $dim d>]() {
init_tracing();
let mut dt: DelaunayTriangulation<_, (), (), $dim> = DelaunayTriangulation::empty();
let initial_vertices = vec![$(vertex!($simplex_coords)),+];
for vertex in &initial_vertices {
dt.insert(*vertex).unwrap();
}
assert_eq!(dt.number_of_cells(), 1);
dt.insert(vertex!($interior_point)).unwrap();
assert_eq!(dt.number_of_vertices(), $dim + 2);
assert!(dt.number_of_cells() > 1,
"{}D: Should have multiple cells after cavity-based insertion", $dim);
assert!(dt.is_valid().is_ok());
}
#[test]
fn [<test_bootstrap_equivalent_to_batch_ $dim d>]() {
init_tracing();
let vertices = vec![$(vertex!($simplex_coords)),+];
let mut dt_bootstrap: DelaunayTriangulation<_, (), (), $dim> =
DelaunayTriangulation::empty();
for vertex in &vertices {
dt_bootstrap.insert(*vertex).unwrap();
}
let dt_batch: DelaunayTriangulation<_, (), (), $dim> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt_bootstrap.number_of_vertices(), dt_batch.number_of_vertices(),
"{}D: Bootstrap and batch should have same vertex count", $dim);
assert_eq!(dt_bootstrap.number_of_cells(), dt_batch.number_of_cells(),
"{}D: Bootstrap and batch should have same cell count", $dim);
assert!(dt_bootstrap.is_valid().is_ok());
assert!(dt_batch.is_valid().is_ok());
}
}
};
}
test_incremental_insertion!(2, [[0.0, 0.0], [1.0, 0.0], [0.0, 1.0]], [0.5, 0.5]);
test_incremental_insertion!(
3,
[
[0.0, 0.0, 0.0],
[1.0, 0.0, 0.0],
[0.0, 1.0, 0.0],
[0.0, 0.0, 1.0]
],
[0.2, 0.2, 0.2]
);
test_incremental_insertion!(
4,
[
[0.0, 0.0, 0.0, 0.0],
[1.0, 0.0, 0.0, 0.0],
[0.0, 1.0, 0.0, 0.0],
[0.0, 0.0, 1.0, 0.0],
[0.0, 0.0, 0.0, 1.0]
],
[0.2, 0.2, 0.2, 0.2]
);
test_incremental_insertion!(
5,
[
[0.0, 0.0, 0.0, 0.0, 0.0],
[1.0, 0.0, 0.0, 0.0, 0.0],
[0.0, 1.0, 0.0, 0.0, 0.0],
[0.0, 0.0, 1.0, 0.0, 0.0],
[0.0, 0.0, 0.0, 1.0, 0.0],
[0.0, 0.0, 0.0, 0.0, 1.0]
],
[0.2, 0.2, 0.2, 0.2, 0.2]
);
#[test]
fn test_empty_creates_empty_triangulation() {
init_tracing();
let dt: DelaunayTriangulation<_, (), (), 3> = DelaunayTriangulation::empty();
assert_eq!(dt.number_of_vertices(), 0);
assert_eq!(dt.number_of_cells(), 0);
assert_eq!(dt.dim(), -1);
}
#[test]
fn test_empty_supports_incremental_insertion() {
init_tracing();
let mut dt: DelaunayTriangulation<_, (), (), 2> = DelaunayTriangulation::empty();
assert_eq!(dt.number_of_vertices(), 0);
dt.insert(vertex!([0.0, 0.0])).unwrap();
dt.insert(vertex!([1.0, 0.0])).unwrap();
assert_eq!(dt.number_of_cells(), 0);
dt.insert(vertex!([0.0, 1.0])).unwrap();
assert_eq!(dt.number_of_cells(), 1); }
#[test]
fn test_validation_policy_defaults_to_on_suspicion() {
init_tracing();
let dt_empty: DelaunayTriangulation<_, (), (), 2> = DelaunayTriangulation::empty();
assert_eq!(dt_empty.validation_policy(), ValidationPolicy::OnSuspicion);
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt_new: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt_new.validation_policy(), ValidationPolicy::OnSuspicion);
let dt_with_kernel: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::with_kernel(&AdaptiveKernel::new(), &vertices).unwrap();
assert_eq!(
dt_with_kernel.validation_policy(),
ValidationPolicy::OnSuspicion
);
let tds =
Triangulation::<FastKernel<f64>, (), (), 2>::build_initial_simplex(&vertices).unwrap();
let dt_from_tds: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::from_tds(tds, FastKernel::new());
assert_eq!(
dt_from_tds.validation_policy(),
ValidationPolicy::OnSuspicion
);
}
#[test]
fn test_validation_policy_setter_and_getter_roundtrip() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.validation_policy(), ValidationPolicy::OnSuspicion);
assert_eq!(dt.tri.validation_policy, ValidationPolicy::OnSuspicion);
dt.set_validation_policy(ValidationPolicy::Always);
assert_eq!(dt.validation_policy(), ValidationPolicy::Always);
assert_eq!(dt.tri.validation_policy, ValidationPolicy::Always);
dt.set_validation_policy(ValidationPolicy::Never);
assert_eq!(dt.validation_policy(), ValidationPolicy::Never);
assert_eq!(dt.tri.validation_policy, ValidationPolicy::Never);
dt.set_validation_policy(ValidationPolicy::OnSuspicion);
assert_eq!(dt.validation_policy(), ValidationPolicy::OnSuspicion);
assert_eq!(dt.tri.validation_policy, ValidationPolicy::OnSuspicion);
}
#[test]
fn test_with_kernel_fast_kernel() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt: DelaunayTriangulation<FastKernel<f64>, (), (), 2> =
DelaunayTriangulation::with_kernel(&FastKernel::new(), &vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 3);
assert_eq!(dt.number_of_cells(), 1);
}
#[test]
fn test_with_kernel_robust_kernel() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt: DelaunayTriangulation<RobustKernel<f64>, (), (), 2> =
DelaunayTriangulation::with_kernel(&RobustKernel::new(), &vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 3);
assert_eq!(dt.number_of_cells(), 1);
}
#[test]
fn test_with_kernel_insufficient_vertices_2d() {
init_tracing();
let vertices = vec![vertex!([0.0, 0.0]), vertex!([1.0, 0.0])];
let result: Result<DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2>, _> =
DelaunayTriangulation::with_kernel(&AdaptiveKernel::new(), &vertices);
assert!(result.is_err());
match result {
Err(DelaunayTriangulationConstructionError::Triangulation(
TriangulationConstructionError::InsufficientVertices { dimension, .. },
)) => {
assert_eq!(dimension, 2);
}
_ => panic!("Expected InsufficientVertices error"),
}
}
#[test]
fn test_with_kernel_insufficient_vertices_3d() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
];
let result: Result<DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 3>, _> =
DelaunayTriangulation::with_kernel(&AdaptiveKernel::new(), &vertices);
assert!(result.is_err());
match result {
Err(DelaunayTriangulationConstructionError::Triangulation(
TriangulationConstructionError::InsufficientVertices { dimension, .. },
)) => {
assert_eq!(dimension, 3);
}
_ => panic!("Expected InsufficientVertices error"),
}
}
#[test]
fn test_with_kernel_f32_coordinates() {
init_tracing();
let vertices = vec![
vertex!([0.0f32, 0.0f32]),
vertex!([1.0f32, 0.0f32]),
vertex!([0.0f32, 1.0f32]),
];
let dt: DelaunayTriangulation<AdaptiveKernel<f32>, (), (), 2> =
DelaunayTriangulation::with_kernel(&AdaptiveKernel::new(), &vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 3);
assert_eq!(dt.number_of_cells(), 1);
}
#[test]
fn test_number_of_vertices_minimal_simplex() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 4);
}
#[test]
fn test_number_of_cells_minimal_simplex() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_cells(), 1);
}
#[test]
fn test_number_of_cells_after_insertion() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_cells(), 1);
dt.insert(vertex!([0.3, 0.3])).unwrap();
assert_eq!(dt.number_of_cells(), 3);
}
#[test]
fn test_dim_returns_correct_dimension() {
init_tracing();
let vertices_2d = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt_2d: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices_2d).unwrap();
assert_eq!(dt_2d.dim(), 2);
let vertices_3d = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt_3d: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices_3d).unwrap();
assert_eq!(dt_3d.dim(), 3);
let vertices_4d = vec![
vertex!([0.0, 0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0, 0.0]),
vertex!([0.0, 0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 0.0, 1.0]),
];
let dt_4d: DelaunayTriangulation<_, (), (), 4> =
DelaunayTriangulation::new(&vertices_4d).unwrap();
assert_eq!(dt_4d.dim(), 4);
}
#[test]
fn test_insert_single_interior_point_2d() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 3);
assert_eq!(dt.number_of_cells(), 1);
let v_key = dt.insert(vertex!([0.3, 0.3])).unwrap();
assert_eq!(dt.number_of_vertices(), 4);
assert_eq!(dt.number_of_cells(), 3);
assert!(dt.tri.tds.get_vertex_by_key(v_key).is_some());
}
#[test]
fn test_insert_multiple_sequential_points_2d() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.insert(vertex!([0.3, 0.3])).unwrap();
assert_eq!(dt.number_of_vertices(), 4);
dt.insert(vertex!([0.5, 0.2])).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
dt.insert(vertex!([0.2, 0.5])).unwrap();
assert_eq!(dt.number_of_vertices(), 6);
assert!(dt.number_of_cells() > 1);
}
#[test]
fn test_insert_multiple_sequential_points_3d() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.insert(vertex!([0.1, 0.1, 0.1])).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
dt.insert(vertex!([0.15, 0.15, 0.1])).unwrap();
assert_eq!(dt.number_of_vertices(), 6);
dt.insert(vertex!([0.1, 0.15, 0.15])).unwrap();
assert_eq!(dt.number_of_vertices(), 7);
assert!(dt.number_of_cells() > 1);
}
#[test]
fn test_insert_updates_last_inserted_cell() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert!(dt.insertion_state.last_inserted_cell.is_none());
dt.insert(vertex!([0.3, 0.3])).unwrap();
assert!(dt.insertion_state.last_inserted_cell.is_some());
}
#[test]
fn test_new_with_exact_minimum_vertices() {
init_tracing();
let vertices_2d = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt_2d: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices_2d).unwrap();
assert_eq!(dt_2d.number_of_vertices(), 3);
assert_eq!(dt_2d.number_of_cells(), 1);
let vertices_3d = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt_3d: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices_3d).unwrap();
assert_eq!(dt_3d.number_of_vertices(), 4);
assert_eq!(dt_3d.number_of_cells(), 1);
}
#[test]
fn test_tds_accessor_provides_readonly_access() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let tds = dt.tds();
assert_eq!(tds.number_of_vertices(), 3);
assert_eq!(tds.number_of_cells(), 1);
assert!(tds.is_valid().is_ok());
assert!(tds.cell_keys().next().is_some());
}
#[test]
fn test_internal_tds_access() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 4);
let tds = &mut dt.tri.tds;
assert_eq!(tds.number_of_vertices(), 4);
assert_eq!(tds.number_of_cells(), 1);
let result = tds.remove_duplicate_cells();
assert!(result.is_ok());
}
#[test]
fn test_tds_accessor_reflects_insertions() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.tds().number_of_vertices(), 3);
dt.insert(vertex!([0.3, 0.3])).unwrap();
assert_eq!(dt.tds().number_of_vertices(), 4);
assert!(dt.tds().number_of_cells() > 1);
}
#[test]
fn test_tds_accessors_maintain_validation_invariants() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0, 0.0]),
vertex!([0.0, 0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 4> =
DelaunayTriangulation::new(&vertices).unwrap();
assert!(dt.tds().is_valid().is_ok());
dt.insert(vertex!([0.2, 0.2, 0.2, 0.2])).unwrap();
assert!(dt.tds().is_valid().is_ok());
assert!(dt.tds().validate().is_ok());
}
#[test]
fn test_bootstrap_with_custom_kernel() {
init_tracing();
let mut dt: DelaunayTriangulation<RobustKernel<f64>, (), (), 3> =
DelaunayTriangulation::with_empty_kernel(RobustKernel::new());
assert_eq!(dt.number_of_vertices(), 0);
dt.insert(vertex!([0.0, 0.0, 0.0])).unwrap();
dt.insert(vertex!([1.0, 0.0, 0.0])).unwrap();
dt.insert(vertex!([0.0, 1.0, 0.0])).unwrap();
assert_eq!(dt.number_of_cells(), 0);
dt.insert(vertex!([0.0, 0.0, 1.0])).unwrap();
assert_eq!(dt.number_of_cells(), 1);
assert!(dt.is_valid().is_ok());
}
#[test]
fn test_with_kernel_aborts_on_duplicate_uuid_in_insertion_loop() {
init_tracing();
let mut vertices = vec![
vertex!([0.0, 0.0]),
vertex!([2.0, 0.0]),
vertex!([0.0, 2.0]),
vertex!([0.25, 0.25]),
];
let dup_uuid = vertices[0].uuid();
vertices[3].set_uuid(dup_uuid).unwrap();
let result: Result<DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2>, _> =
DelaunayTriangulation::with_kernel(&AdaptiveKernel::new(), &vertices);
match result.unwrap_err() {
DelaunayTriangulationConstructionError::Triangulation(
TriangulationConstructionError::Tds(TdsConstructionError::DuplicateUuid {
entity: _,
uuid,
}),
) => {
assert_eq!(uuid, dup_uuid);
}
other => panic!("Expected DuplicateUuid error, got {other:?}"),
}
}
#[test]
fn test_validation_report_ok_for_valid_triangulation() {
init_tracing();
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
assert!(dt.validation_report().is_ok());
}
#[test]
fn test_validation_report_returns_mapping_failures_only() {
init_tracing();
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let uuid = dt.tri.tds.vertices().next().unwrap().1.uuid();
dt.tri.tds.uuid_to_vertex_key.remove(&uuid);
let report = dt.validation_report().unwrap_err();
assert!(!report.violations.is_empty());
assert!(report.violations.iter().all(|v| {
matches!(
v.kind,
InvariantKind::VertexMappings | InvariantKind::CellMappings
)
}));
assert!(
report
.violations
.iter()
.all(|v| v.kind != InvariantKind::DelaunayProperty)
);
}
#[test]
fn test_validation_report_includes_vertex_incidence_violation() {
init_tracing();
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let vertex_key = dt.tri.tds.vertices().next().unwrap().0;
dt.tri
.tds
.get_vertex_by_key_mut(vertex_key)
.unwrap()
.incident_cell = Some(CellKey::default());
let report = dt.validation_report().unwrap_err();
assert!(
report
.violations
.iter()
.any(|v| v.kind == InvariantKind::VertexIncidence)
);
}
#[test]
fn test_serde_roundtrip_uses_custom_deserialize_impl() {
init_tracing();
let vertices = [
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let json = serde_json::to_string(&dt).unwrap();
let tds: Tds<f64, (), (), 3> = serde_json::from_str(&json).unwrap();
let roundtrip_adaptive = DelaunayTriangulation::from_tds(tds, AdaptiveKernel::new());
assert_eq!(
roundtrip_adaptive.number_of_vertices(),
dt.number_of_vertices()
);
assert_eq!(roundtrip_adaptive.number_of_cells(), dt.number_of_cells());
assert!(
roundtrip_adaptive
.insertion_state
.last_inserted_cell
.is_none()
);
let roundtrip_robust: DelaunayTriangulation<RobustKernel<f64>, (), (), 3> =
serde_json::from_str(&json).unwrap();
assert_eq!(
roundtrip_robust.number_of_vertices(),
dt.number_of_vertices()
);
assert_eq!(roundtrip_robust.number_of_cells(), dt.number_of_cells());
assert!(
roundtrip_robust
.insertion_state
.last_inserted_cell
.is_none()
);
}
#[test]
fn test_topology_traversal_methods_are_forwarded() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let tri = dt.as_triangulation();
let edges_dt: std::collections::HashSet<_> = dt.edges().collect();
let edges_tri: std::collections::HashSet<_> = tri.edges().collect();
assert_eq!(edges_dt, edges_tri);
assert_eq!(edges_dt.len(), 6);
let index = dt.build_adjacency_index().unwrap();
let edges_dt_index: std::collections::HashSet<_> = dt.edges_with_index(&index).collect();
let edges_tri_index: std::collections::HashSet<_> = tri.edges_with_index(&index).collect();
assert_eq!(edges_dt_index, edges_tri_index);
assert_eq!(edges_dt_index, edges_dt);
let v0 = dt.vertices().next().unwrap().0;
let incident_dt: std::collections::HashSet<_> = dt.incident_edges(v0).collect();
let incident_tri: std::collections::HashSet<_> = tri.incident_edges(v0).collect();
assert_eq!(incident_dt, incident_tri);
assert_eq!(incident_dt.len(), 3);
let incident_dt_index: std::collections::HashSet<_> =
dt.incident_edges_with_index(&index, v0).collect();
let incident_tri_index: std::collections::HashSet<_> =
tri.incident_edges_with_index(&index, v0).collect();
assert_eq!(incident_dt_index, incident_tri_index);
assert_eq!(incident_dt_index, incident_dt);
let cell_key = dt.cells().next().unwrap().0;
let neighbors_dt: Vec<_> = dt.cell_neighbors(cell_key).collect();
let neighbors_tri: Vec<_> = tri.cell_neighbors(cell_key).collect();
assert_eq!(neighbors_dt, neighbors_tri);
assert!(neighbors_dt.is_empty());
let neighbors_dt_index: Vec<_> = dt.cell_neighbors_with_index(&index, cell_key).collect();
let neighbors_tri_index: Vec<_> = tri.cell_neighbors_with_index(&index, cell_key).collect();
assert_eq!(neighbors_dt_index, neighbors_tri_index);
assert_eq!(neighbors_dt_index, neighbors_dt);
let cell_vertices_dt = dt.cell_vertices(cell_key).unwrap();
let cell_vertices_tri = tri.cell_vertices(cell_key).unwrap();
assert_eq!(cell_vertices_dt, cell_vertices_tri);
assert_eq!(cell_vertices_dt.len(), 4);
let coords_dt = dt.vertex_coords(v0).unwrap();
let coords_tri = tri.vertex_coords(v0).unwrap();
assert_eq!(coords_dt, coords_tri);
assert!(dt.vertex_coords(VertexKey::default()).is_none());
assert!(dt.cell_vertices(CellKey::default()).is_none());
}
#[test]
fn test_batch_3d_construction_with_extra_vertex_triggers_incremental_repair() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.3, 0.3, 0.3]),
];
let dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
assert_eq!(dt.number_of_vertices(), 5);
assert!(dt.validate().is_ok());
}
#[test]
fn test_batch_3d_construction_statistics_with_extra_vertex_triggers_incremental_repair() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.3, 0.3, 0.3]),
];
let (dt, stats) =
DelaunayTriangulation::<_, (), (), 3>::new_with_construction_statistics(&vertices)
.unwrap();
assert_eq!(dt.number_of_vertices(), 5);
assert_eq!(stats.inserted, 5);
assert!(dt.validate().is_ok());
}
#[test]
fn test_try_d_lt4_global_repair_fallback_disabled_returns_error() {
use crate::core::algorithms::flips::{DelaunayRepairDiagnostics, RepairQueueOrder};
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let repair_err = DelaunayRepairError::NonConvergent {
max_flips: 16,
diagnostics: DelaunayRepairDiagnostics {
facets_checked: 0,
flips_performed: 0,
max_queue_len: 0,
ambiguous_predicates: 0,
ambiguous_predicate_samples: Vec::new(),
predicate_failures: 0,
cycle_detections: 0,
cycle_signature_samples: Vec::new(),
attempt: 1,
queue_order: RepairQueueOrder::Fifo,
},
};
let result =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::try_d_lt4_global_repair_fallback(
&mut dt.tri.tds,
&dt.tri.kernel,
TopologyGuarantee::PLManifold,
false, 5,
&repair_err,
);
assert!(result.is_err());
let err_msg = format!("{}", result.unwrap_err());
assert!(
err_msg.contains("per-insertion Delaunay repair failed at index 5"),
"error should mention the index: {err_msg}"
);
}
#[test]
fn test_try_d_lt4_global_repair_fallback_enabled_succeeds_on_valid_tds() {
use crate::core::algorithms::flips::{DelaunayRepairDiagnostics, RepairQueueOrder};
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
vertex!([0.3, 0.3, 0.3]),
];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let repair_err = DelaunayRepairError::NonConvergent {
max_flips: 16,
diagnostics: DelaunayRepairDiagnostics {
facets_checked: 0,
flips_performed: 0,
max_queue_len: 0,
ambiguous_predicates: 0,
ambiguous_predicate_samples: Vec::new(),
predicate_failures: 0,
cycle_detections: 0,
cycle_signature_samples: Vec::new(),
attempt: 1,
queue_order: RepairQueueOrder::Fifo,
},
};
let result =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::try_d_lt4_global_repair_fallback(
&mut dt.tri.tds,
&dt.tri.kernel,
TopologyGuarantee::PLManifold,
true, 5,
&repair_err,
);
assert!(
result.is_ok(),
"global repair on valid TDS should succeed: {:?}",
result.err()
);
}
#[test]
fn test_try_d_lt4_global_repair_fallback_error_includes_both_messages() {
init_tracing();
let vertices = vec![vertex!([0.0]), vertex!([1.0])];
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 1> =
DelaunayTriangulation::new(&vertices).unwrap();
let repair_err = DelaunayRepairError::PostconditionFailed {
message: "synthetic local error".to_string(),
};
let result =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 1>::try_d_lt4_global_repair_fallback(
&mut dt.tri.tds,
&dt.tri.kernel,
TopologyGuarantee::PLManifold,
true, 7,
&repair_err,
);
assert!(result.is_err());
let err_msg = format!("{}", result.unwrap_err());
assert!(
err_msg.contains("local error:"),
"error should contain local error detail: {err_msg}"
);
assert!(
err_msg.contains("global fallback:"),
"error should contain global fallback detail: {err_msg}"
);
assert!(
err_msg.contains("index 7"),
"error should contain the index: {err_msg}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_topology_validation_is_internal() {
let error = InsertionError::TopologyValidation(TdsError::InconsistentDataStructure {
message: "missing cell".to_string(),
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
),
"TopologyValidation should map to InternalInconsistency, got: {mapped:?}"
);
let msg = mapped.to_string();
assert!(
msg.contains("missing cell"),
"error message should preserve the original error: {msg}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_degenerate_orientation_is_degeneracy() {
let error = InsertionError::TopologyValidation(TdsError::Geometric(
GeometricError::DegenerateOrientation {
message: "det=0".to_string(),
},
));
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::GeometricDegeneracy { .. }
),
"DegenerateOrientation should map to GeometricDegeneracy, got: {mapped:?}"
);
let msg = mapped.to_string();
assert!(
msg.contains("det=0"),
"error message should preserve the original error: {msg}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_negative_orientation_is_degeneracy() {
let error = InsertionError::TopologyValidation(TdsError::Geometric(
GeometricError::NegativeOrientation {
message: "det<0 after canonicalization".to_string(),
},
));
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::GeometricDegeneracy { .. }
),
"NegativeOrientation should map to GeometricDegeneracy, got: {mapped:?}"
);
let msg = mapped.to_string();
assert!(
msg.contains("det<0"),
"error message should preserve the original error: {msg}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_isolated_vertex_is_internal() {
let error = InsertionError::TopologyValidationFailed {
message: "test".to_string(),
source: Box::new(TriangulationValidationError::IsolatedVertex {
vertex_key: VertexKey::from(slotmap::KeyData::from_ffi(1)),
vertex_uuid: Uuid::nil(),
}),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
),
"IsolatedVertex should map to InternalInconsistency, got: {mapped:?}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_construction_preserves_source() {
let error =
InsertionError::Construction(TriangulationConstructionError::FailedToCreateCell {
message: "test".to_string(),
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::FailedToCreateCell { .. }
),
"Construction should preserve the inner error, got: {mapped:?}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_topology_validation_failed_is_internal() {
let error = InsertionError::TopologyValidationFailed {
message: "post-insertion".to_string(),
source: Box::new(TriangulationValidationError::EulerCharacteristicMismatch {
computed: 3,
expected: 2,
classification: TopologyClassification::Ball(3),
}),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
),
"TopologyValidationFailed should map to InternalInconsistency, got: {mapped:?}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_cavity_filling_is_internal() {
let error = InsertionError::CavityFilling {
message: "test".to_string(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
));
}
#[test]
fn test_map_orientation_canonicalization_error_neighbor_wiring_is_internal() {
let error = InsertionError::NeighborWiring {
message: "test".to_string(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
));
}
#[test]
fn test_map_orientation_canonicalization_error_duplicate_uuid_is_internal() {
let error = InsertionError::DuplicateUuid {
entity: EntityKind::Cell,
uuid: Uuid::nil(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
));
}
#[test]
fn test_map_orientation_canonicalization_error_geometry_variants_are_degeneracy() {
use crate::core::algorithms::incremental_insertion::HullExtensionReason;
use crate::core::algorithms::locate::LocateError;
let geometry_errors: Vec<InsertionError> = vec![
InsertionError::Location(LocateError::EmptyTriangulation),
InsertionError::NonManifoldTopology {
facet_hash: 0,
cell_count: 3,
},
InsertionError::HullExtension {
reason: HullExtensionReason::NoVisibleFacets,
},
InsertionError::DelaunayValidationFailed {
source: Box::new(DelaunayTriangulationValidationError::VerificationFailed {
message: "test".to_string(),
}),
},
InsertionError::DelaunayRepairFailed {
source: Box::new(DelaunayRepairError::PostconditionFailed {
message: "test".to_string(),
}),
context: "test".to_string(),
},
InsertionError::DuplicateCoordinates {
coordinates: "[0,0,0]".to_string(),
},
];
for error in geometry_errors {
let label = format!("{error}");
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::GeometricDegeneracy { .. }
),
"{label} should map to GeometricDegeneracy, got: {mapped:?}"
);
}
}
#[test]
fn test_map_insertion_error_construction_preserves_source() {
let error =
InsertionError::Construction(TriangulationConstructionError::FailedToCreateCell {
message: "inner".to_string(),
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::FailedToCreateCell { .. }
),
"Construction should preserve inner error, got: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_cavity_filling() {
let error = InsertionError::CavityFilling {
message: "test".to_string(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::FailedToCreateCell { .. }
),
"CavityFilling should map to FailedToCreateCell, got: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_neighbor_wiring() {
let error = InsertionError::NeighborWiring {
message: "bad wiring".to_string(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
),
"NeighborWiring should map to InternalInconsistency, got: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_topology_validation() {
let error = InsertionError::TopologyValidation(TdsError::InconsistentDataStructure {
message: "broken".to_string(),
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(mapped, TriangulationConstructionError::Tds(_)),
"TopologyValidation should map to Tds(ValidationError), got: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_duplicate_uuid() {
let error = InsertionError::DuplicateUuid {
entity: EntityKind::Cell,
uuid: Uuid::nil(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(mapped, TriangulationConstructionError::Tds(_)),
"DuplicateUuid should map to Tds(DuplicateUuid), got: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_duplicate_coordinates() {
let error = InsertionError::DuplicateCoordinates {
coordinates: "[1,2,3]".to_string(),
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::DuplicateCoordinates { .. }
),
"DuplicateCoordinates should be preserved, got: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_geometry_variants_are_degeneracy() {
use crate::core::algorithms::incremental_insertion::HullExtensionReason;
use crate::core::algorithms::locate::LocateError;
let geometry_errors: Vec<InsertionError> = vec![
InsertionError::ConflictRegion(
crate::core::algorithms::locate::ConflictError::OpenBoundary {
facet_count: 2,
ridge_vertex_count: 1,
open_cell: CellKey::from(slotmap::KeyData::from_ffi(1)),
},
),
InsertionError::Location(LocateError::EmptyTriangulation),
InsertionError::NonManifoldTopology {
facet_hash: 0,
cell_count: 3,
},
InsertionError::HullExtension {
reason: HullExtensionReason::NoVisibleFacets,
},
InsertionError::DelaunayValidationFailed {
source: Box::new(DelaunayTriangulationValidationError::VerificationFailed {
message: "test".to_string(),
}),
},
InsertionError::DelaunayRepairFailed {
source: Box::new(DelaunayRepairError::PostconditionFailed {
message: "test".to_string(),
}),
context: "test".to_string(),
},
InsertionError::TopologyValidationFailed {
message: "test".to_string(),
source: Box::new(TriangulationValidationError::EulerCharacteristicMismatch {
computed: 3,
expected: 2,
classification: TopologyClassification::Ball(3),
}),
},
];
for error in geometry_errors {
let label = format!("{error}");
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::GeometricDegeneracy { .. }
),
"{label} should map to GeometricDegeneracy, got: {mapped:?}"
);
}
}
#[test]
fn test_is_retryable_degenerate_orientation_is_retryable() {
let error = InsertionError::TopologyValidation(TdsError::Geometric(
GeometricError::DegenerateOrientation {
message: "det=0".to_string(),
},
));
assert!(
error.is_retryable(),
"DegenerateOrientation should be retryable"
);
}
#[test]
fn test_is_retryable_negative_orientation_is_retryable() {
let error = InsertionError::TopologyValidation(TdsError::Geometric(
GeometricError::NegativeOrientation {
message: "det<0".to_string(),
},
));
assert!(
error.is_retryable(),
"NegativeOrientation should be retryable"
);
}
#[test]
fn test_is_retryable_isolated_vertex_is_retryable() {
let error = InsertionError::TopologyValidationFailed {
message: "test".to_string(),
source: Box::new(TriangulationValidationError::IsolatedVertex {
vertex_key: VertexKey::from(slotmap::KeyData::from_ffi(1)),
vertex_uuid: Uuid::nil(),
}),
};
assert!(
error.is_retryable(),
"IsolatedVertex should be retryable (geometry-sensitive conflict region)"
);
}
#[test]
fn test_is_retryable_inconsistent_data_structure_is_not_retryable() {
let error = InsertionError::TopologyValidation(TdsError::InconsistentDataStructure {
message: "missing cell".to_string(),
});
assert!(
!error.is_retryable(),
"InconsistentDataStructure should NOT be retryable"
);
}
#[test]
fn test_is_retryable_failed_to_create_cell_is_not_retryable() {
let error = InsertionError::TopologyValidation(TdsError::FailedToCreateCell {
message: "test".to_string(),
});
assert!(
!error.is_retryable(),
"FailedToCreateCell should NOT be retryable"
);
}
#[test]
fn test_verification_failed_display() {
let err = DelaunayTriangulationValidationError::VerificationFailed {
message: "flip predicate detected non-Delaunay facet".to_string(),
};
let msg = err.to_string();
assert!(
msg.contains("Delaunay verification failed"),
"Display should contain prefix: {msg}"
);
assert!(
msg.contains("flip predicate detected non-Delaunay facet"),
"Display should contain inner message: {msg}"
);
}
#[test]
fn test_delaunay_validation_error_tds_variant_display() {
let inner = TdsError::InconsistentDataStructure {
message: "broken link".to_string(),
};
let err = DelaunayTriangulationValidationError::from(inner);
assert!(err.to_string().contains("broken link"));
}
#[test]
fn test_delaunay_validation_error_triangulation_variant_display() {
let inner = TriangulationValidationError::IsolatedVertex {
vertex_key: VertexKey::from(slotmap::KeyData::from_ffi(1)),
vertex_uuid: Uuid::nil(),
};
let err = DelaunayTriangulationValidationError::from(inner);
assert!(err.to_string().contains("Isolated vertex"));
}
#[test]
fn test_dt_validate_maps_tds_error_to_tds_variant() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let vk = dt.tds().vertex_keys().next().unwrap();
let uuid = dt.tds().get_vertex_by_key(vk).unwrap().uuid();
dt.tds_mut().uuid_to_vertex_key.remove(&uuid);
match dt.validate() {
Err(DelaunayTriangulationValidationError::Tds(TdsError::MappingInconsistency {
..
})) => {}
other => panic!(
"Expected DelaunayTriangulationValidationError::Tds(MappingInconsistency), got {other:?}"
),
}
}
#[test]
fn test_dt_validate_maps_topology_error_to_triangulation_variant() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([0.0, 1.0, 0.0]),
vertex!([0.0, 0.0, 1.0]),
];
let mut dt: DelaunayTriangulation<_, (), (), 3> =
DelaunayTriangulation::new(&vertices).unwrap();
let _ = dt
.tds_mut()
.insert_vertex_with_mapping(vertex!([0.5, 0.5, 0.5]))
.unwrap();
match dt.validate() {
Err(DelaunayTriangulationValidationError::Triangulation(
TriangulationValidationError::IsolatedVertex { .. },
)) => {}
other => panic!(
"Expected DelaunayTriangulationValidationError::Triangulation(IsolatedVertex), got {other:?}"
),
}
}
#[test]
fn test_map_orientation_canonicalization_error_orientation_violation_is_internal_inconsistency()
{
let error = InsertionError::TopologyValidation(TdsError::OrientationViolation {
cell1_key: CellKey::from(slotmap::KeyData::from_ffi(1)),
cell1_uuid: Uuid::nil(),
cell2_key: CellKey::from(slotmap::KeyData::from_ffi(2)),
cell2_uuid: Uuid::nil(),
cell1_facet_index: 0,
cell2_facet_index: 1,
facet_vertices: vec![],
cell2_facet_vertices: vec![],
observed_odd_permutation: true,
expected_odd_permutation: false,
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { .. }
),
"OrientationViolation should map to InternalInconsistency (structural invariant breach, not geometry), got: {mapped:?}"
);
}
#[test]
fn test_map_orientation_canonicalization_error_conflict_region_is_degeneracy() {
use crate::core::algorithms::locate::ConflictError;
let error = InsertionError::ConflictRegion(ConflictError::NonManifoldFacet {
facet_hash: 0x123,
cell_count: 3,
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::GeometricDegeneracy { .. }
),
"ConflictRegion should map to GeometricDegeneracy, got: {mapped:?}"
);
}
#[test]
fn test_is_non_retryable_construction_error_duplicate_uuid() {
let err: DelaunayTriangulationConstructionError =
TriangulationConstructionError::Tds(TdsConstructionError::DuplicateUuid {
entity: EntityKind::Cell,
uuid: Uuid::nil(),
})
.into();
assert!(
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::is_non_retryable_construction_error(
&err
),
"DuplicateUuid should be non-retryable"
);
}
#[test]
fn test_is_non_retryable_construction_error_internal_inconsistency() {
let err: DelaunayTriangulationConstructionError =
TriangulationConstructionError::InternalInconsistency {
message: "test".to_string(),
}
.into();
assert!(
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::is_non_retryable_construction_error(
&err
),
"InternalInconsistency should be non-retryable"
);
}
#[test]
fn test_is_non_retryable_construction_error_false_for_geometric_degeneracy() {
let err: DelaunayTriangulationConstructionError =
TriangulationConstructionError::GeometricDegeneracy {
message: "test".to_string(),
}
.into();
assert!(
!DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::is_non_retryable_construction_error(
&err
),
"GeometricDegeneracy should NOT be non-retryable"
);
}
#[test]
fn test_advanced_repair_fallback_error_preserves_full_chain_context() {
let primary_err = DelaunayRepairError::NonConvergent {
max_flips: 1000,
diagnostics: crate::core::algorithms::flips::DelaunayRepairDiagnostics {
facets_checked: 50,
flips_performed: 1000,
max_queue_len: 42,
ambiguous_predicates: 0,
ambiguous_predicate_samples: Vec::new(),
predicate_failures: 0,
cycle_detections: 0,
cycle_signature_samples: Vec::new(),
attempt: 1,
queue_order: crate::core::algorithms::flips::RepairQueueOrder::Fifo,
},
};
let robust_err = DelaunayRepairError::PostconditionFailed {
message: "robust postcondition failure".to_string(),
};
let heuristic_inner = DelaunayRepairError::HeuristicRebuildFailed {
message: "heuristic rebuild failed after 3 attempts: attempt 3/3 (shuffle_seed=1 perturbation_seed=2): inner".to_string(),
};
let heuristic_message = match heuristic_inner {
DelaunayRepairError::HeuristicRebuildFailed { message } => message,
other => other.to_string(),
};
let combined = DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"primary repair failed ({primary_err}); robust fallback failed ({robust_err}); {heuristic_message}"
),
};
let msg = combined.to_string();
assert!(
msg.contains("primary repair failed"),
"error should mention primary failure: {msg}"
);
assert!(
msg.contains("robust fallback failed"),
"error should mention robust failure: {msg}"
);
assert!(
msg.contains("robust postcondition failure"),
"error should include robust failure details: {msg}"
);
assert!(
msg.contains("heuristic rebuild failed after 3 attempts"),
"error should include heuristic rebuild details: {msg}"
);
}
}