#![forbid(unsafe_code)]
use crate::core::adjacency::{AdjacencyIndex, AdjacencyIndexBuildError};
use crate::core::algorithms::flips::{
DelaunayRepairError, DelaunayRepairRun, DelaunayRepairStats, FlipError, LocalRepairPhaseTiming,
apply_bistellar_flip_k1_inverse, repair_delaunay_local_single_pass,
repair_delaunay_local_single_pass_timed, repair_delaunay_with_flips_k2_k3,
repair_delaunay_with_flips_k2_k3_run, verify_delaunay_for_triangulation,
};
use crate::core::algorithms::incremental_insertion::{
DelaunayRepairErrorSummary, DelaunayRepairFailureContext, InsertionError,
TdsConstructionFailure,
};
use crate::core::algorithms::locate::LocateError;
use crate::core::cell::{Cell, CellValidationError};
use crate::core::collections::spatial_hash_grid::HashGridIndex;
use crate::core::collections::{
CellKeyBuffer, FastHashSet, FastHasher, MAX_PRACTICAL_DIMENSION_SIZE, SecureHashMap,
SmallBuffer,
};
use crate::core::edge::EdgeKey;
use crate::core::facet::{AllFacetsIter, BoundaryFacetsIter};
use crate::core::operations::{
DelaunayInsertionState, InsertionOutcome, InsertionResult, InsertionStatistics,
InsertionTelemetryMode, RepairDecision, TopologicalOperation,
};
use crate::core::tds::{
CellKey, InvariantError, InvariantKind, InvariantViolation, NeighborValidationError, Tds,
TdsConstructionError, TdsError, TriangulationValidationReport, VertexKey,
};
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::util::{
coords_equal_exact, coords_within_epsilon, hilbert_indices_prequantized, hilbert_quantize,
is_delaunay_property_only, stable_hash_u64_slice,
};
use crate::core::vertex::Vertex;
use crate::geometry::kernel::{AdaptiveKernel, ExactPredicates, Kernel, RobustKernel};
use crate::geometry::point::Point;
use crate::geometry::traits::coordinate::{Coordinate, CoordinateScalar};
use crate::geometry::util::{safe_coords_to_f64, safe_usize_to_scalar, simplex_volume};
use crate::topology::manifold::{ManifoldError, validate_ridge_links_for_cells};
use crate::topology::traits::topological_space::{GlobalTopology, TopologyKind};
use crate::triangulation::builder::DelaunayTriangulationBuilder;
use crate::triangulation::diagnostics::{
BatchLocalRepairTrigger, ConstructionTelemetry, LocalRepairSample,
};
use crate::triangulation::locality::{
accumulate_live_cell_seeds, clear_cell_seed_set, retain_live_cell_seeds,
};
use core::{cmp::Ordering, fmt};
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::env;
use std::hash::{Hash, Hasher};
use std::num::NonZeroUsize;
use std::time::{Duration, Instant};
use thiserror::Error;
use uuid::Uuid;
const DELAUNAY_SHUFFLE_ATTEMPTS: usize = 6;
const DELAUNAY_SHUFFLE_SEED_SALT: u64 = 0x9E37_79B9_7F4A_7C15;
const INITIAL_SIMPLEX_MAX_VOLUME_CANDIDATE_CAP: usize = 18;
const HEURISTIC_REBUILD_ATTEMPTS: usize = 6;
pub(crate) const LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_GE_4: usize = 12;
pub(crate) const LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_GE_4: usize = 96;
pub(crate) const LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_LT_4: usize = 4;
pub(crate) const LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_LT_4: usize = 16;
const LOCAL_REPAIR_SEED_BACKLOG_FACTOR_D_GE_4: usize = 24;
const LOCAL_REPAIR_SEED_BACKLOG_FACTOR_D_LT_4: usize = 16;
const RIDGE_LINK_REPAIR_VALIDATION_MESSAGE: &str = "Topology invalid after Delaunay repair";
fn ridge_link_repair_validation_error(err: ManifoldError) -> InsertionError {
match TriangulationValidationError::try_from(err) {
Ok(source) => InsertionError::TopologyValidationFailed {
message: RIDGE_LINK_REPAIR_VALIDATION_MESSAGE.to_string(),
source,
},
Err(source) => InsertionError::TopologyValidation(source),
}
}
const fn is_geometric_repair_error(repair_err: &DelaunayRepairError) -> bool {
match repair_err {
DelaunayRepairError::NonConvergent { .. }
| DelaunayRepairError::PostconditionFailed { .. } => true,
DelaunayRepairError::VerificationFailed { source, .. } => is_geometric_flip_error(source),
DelaunayRepairError::Flip(source) => is_geometric_flip_error(source),
DelaunayRepairError::OrientationCanonicalizationFailed { .. }
| DelaunayRepairError::InvalidTopology { .. }
| DelaunayRepairError::HeuristicRebuildFailed { .. } => false,
}
}
const fn is_geometric_flip_error(error: &FlipError) -> bool {
matches!(
error,
FlipError::PredicateFailure { .. }
| FlipError::DegenerateCell
| FlipError::NegativeOrientation { .. }
| FlipError::CellCreation(
CellValidationError::DegenerateSimplex
| CellValidationError::CoordinateConversion { .. },
)
)
}
const fn local_repair_flip_budget<const D: usize>(seed_cells_len: usize) -> usize {
let (factor, floor) = if D >= 4 {
(
LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_GE_4,
LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_GE_4,
)
} else {
(
LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_LT_4,
LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_LT_4,
)
};
let raw = seed_cells_len.saturating_mul(D + 1).saturating_mul(factor);
if raw > floor { raw } else { floor }
}
const fn local_repair_seed_backlog_threshold<const D: usize>() -> usize {
let factor = if D >= 4 {
LOCAL_REPAIR_SEED_BACKLOG_FACTOR_D_GE_4
} else {
LOCAL_REPAIR_SEED_BACKLOG_FACTOR_D_LT_4
};
(D + 1).saturating_mul(factor)
}
const fn default_batch_repair_policy() -> DelaunayRepairPolicy {
DelaunayRepairPolicy::EveryInsertion
}
fn batch_local_repair_trigger<const D: usize>(
policy: DelaunayRepairPolicy,
insertion_count: usize,
topology: TopologyGuarantee,
pending_seed_cells_len: usize,
) -> Option<BatchLocalRepairTrigger> {
if policy == DelaunayRepairPolicy::Never
|| pending_seed_cells_len == 0
|| !TopologicalOperation::FacetFlip.is_admissible_under(topology)
{
return None;
}
if matches!(
policy.decide(insertion_count, topology, TopologicalOperation::FacetFlip,),
RepairDecision::Proceed
) {
return Some(BatchLocalRepairTrigger::Cadence);
}
(pending_seed_cells_len >= local_repair_seed_backlog_threshold::<D>())
.then_some(BatchLocalRepairTrigger::SeedBacklog)
}
fn batch_repair_trace_enabled() -> bool {
env::var_os("DELAUNAY_BATCH_REPAIR_TRACE").is_some()
}
thread_local! {
static HEURISTIC_REBUILD_DEPTH: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
#[cfg(test)]
mod test_hooks {
use crate::core::algorithms::flips::{
DelaunayRepairDiagnostics, DelaunayRepairError, RepairQueueOrder,
};
use std::cell::Cell;
thread_local! {
static FORCE_HEURISTIC_REBUILD: Cell<bool> = const { Cell::new(false) };
static FORCE_REPAIR_NONCONVERGENT: Cell<bool> = const { Cell::new(false) };
static BATCH_LOCAL_REPAIR_CALLS: Cell<usize> = const { Cell::new(0) };
}
pub(super) fn force_heuristic_rebuild_enabled() -> bool {
FORCE_HEURISTIC_REBUILD.with(Cell::get)
}
pub(super) fn set_force_heuristic_rebuild(enabled: bool) -> bool {
FORCE_HEURISTIC_REBUILD.with(|flag| {
let prior = flag.get();
flag.set(enabled);
prior
})
}
pub(super) fn restore_force_heuristic_rebuild(prior: bool) {
FORCE_HEURISTIC_REBUILD.with(|flag| flag.set(prior));
}
pub(super) fn force_repair_nonconvergent_enabled() -> bool {
FORCE_REPAIR_NONCONVERGENT.with(Cell::get)
}
pub(super) fn set_force_repair_nonconvergent(enabled: bool) -> bool {
FORCE_REPAIR_NONCONVERGENT.with(|flag| {
let prior = flag.get();
flag.set(enabled);
prior
})
}
pub(super) fn restore_force_repair_nonconvergent(prior: bool) {
FORCE_REPAIR_NONCONVERGENT.with(|flag| flag.set(prior));
}
pub(super) fn reset_batch_local_repair_calls() {
BATCH_LOCAL_REPAIR_CALLS.with(|calls| calls.set(0));
}
pub(super) fn batch_local_repair_calls() -> usize {
BATCH_LOCAL_REPAIR_CALLS.with(Cell::get)
}
pub(super) fn record_batch_local_repair_call() {
BATCH_LOCAL_REPAIR_CALLS.with(|calls| calls.set(calls.get().saturating_add(1)));
}
pub(super) fn synthetic_nonconvergent_error() -> DelaunayRepairError {
DelaunayRepairError::NonConvergent {
max_flips: 0,
diagnostics: Box::new(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,
}),
}
}
}
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(DelaunayConstructionFailure),
#[error(transparent)]
ExplicitConstruction(#[from] crate::triangulation::builder::ExplicitConstructionError),
}
impl From<TriangulationConstructionError> for DelaunayTriangulationConstructionError {
fn from(source: TriangulationConstructionError) -> Self {
Self::Triangulation(source.into())
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum DelaunayConstructionRepairPhase {
BatchLocal {
index: usize,
},
Completion,
}
impl fmt::Display for DelaunayConstructionRepairPhase {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::BatchLocal { index } => {
write!(f, "batch local repair at input index {index}")
}
Self::Completion => f.write_str("completion repair"),
}
}
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum DelaunayConstructionFailure {
#[error("TDS construction failed: {reason}")]
Tds {
#[source]
reason: TdsConstructionFailure,
},
#[error("failed to create cell during construction: {message}")]
FailedToCreateCell {
message: String,
},
#[error("insufficient vertices for {dimension}D triangulation: {source}")]
InsufficientVertices {
dimension: usize,
#[source]
source: CellValidationError,
},
#[error("geometric degeneracy encountered during construction: {message}")]
GeometricDegeneracy {
message: String,
},
#[error("internal inconsistency during construction: {message}")]
InternalInconsistency {
message: String,
},
#[error("Delaunay repair failed during {phase}: {source}")]
DelaunayRepair {
phase: DelaunayConstructionRepairPhase,
#[source]
source: Box<DelaunayRepairError>,
},
#[error("duplicate coordinates detected: {coordinates}")]
DuplicateCoordinates {
coordinates: String,
},
#[error("conflict region failed during insertion: {message}")]
InsertionConflictRegion {
message: String,
},
#[error("point location failed during insertion: {source}")]
InsertionLocation {
#[source]
source: LocateError,
},
#[error(
"non-manifold topology during insertion: facet {facet_hash:#x} shared by {cell_count} cells"
)]
InsertionNonManifoldTopology {
facet_hash: u64,
cell_count: usize,
},
#[error("hull extension failed during insertion: {message}")]
InsertionHullExtension {
message: String,
},
#[error("Delaunay validation failed during insertion: {message}")]
InsertionDelaunayValidation {
message: String,
},
#[error("topology validation failed during insertion: {message}")]
InsertionTopologyValidation {
message: String,
},
#[error("final topology validation failed after construction: {message}: {source}")]
FinalTopologyValidation {
message: String,
#[source]
source: crate::core::tds::InvariantErrorSummary,
},
}
impl From<TriangulationConstructionError> for DelaunayConstructionFailure {
fn from(source: TriangulationConstructionError) -> Self {
match source {
TriangulationConstructionError::Tds(source) => Self::Tds {
reason: source.into(),
},
TriangulationConstructionError::FailedToCreateCell { message } => {
Self::FailedToCreateCell { message }
}
TriangulationConstructionError::InsufficientVertices { dimension, source } => {
Self::InsufficientVertices { dimension, source }
}
TriangulationConstructionError::GeometricDegeneracy { message } => {
Self::GeometricDegeneracy { message }
}
TriangulationConstructionError::InternalInconsistency { message } => {
Self::InternalInconsistency { message }
}
TriangulationConstructionError::DuplicateCoordinates { coordinates } => {
Self::DuplicateCoordinates { coordinates }
}
TriangulationConstructionError::InsertionConflictRegion { source } => {
Self::InsertionConflictRegion {
message: source.to_string(),
}
}
TriangulationConstructionError::InsertionLocation { source } => {
Self::InsertionLocation { source }
}
TriangulationConstructionError::InsertionNonManifoldTopology {
facet_hash,
cell_count,
} => Self::InsertionNonManifoldTopology {
facet_hash,
cell_count,
},
TriangulationConstructionError::InsertionHullExtension { reason } => {
Self::InsertionHullExtension {
message: reason.to_string(),
}
}
TriangulationConstructionError::InsertionDelaunayValidation { source } => {
Self::InsertionDelaunayValidation {
message: source.to_string(),
}
}
TriangulationConstructionError::InsertionTopologyValidation { message, source } => {
Self::InsertionTopologyValidation {
message: format!("{message}: {source}"),
}
}
TriangulationConstructionError::FinalTopologyValidation { message, source } => {
Self::FinalTopologyValidation { message, source }
}
}
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
#[non_exhaustive]
pub enum DelaunayRepairOperation {
VertexRemoval,
}
impl fmt::Display for DelaunayRepairOperation {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::VertexRemoval => f.write_str("vertex removal"),
}
}
}
#[derive(Clone, Debug, Error, PartialEq, Eq)]
#[non_exhaustive]
pub enum DelaunayTriangulationValidationError {
#[error(transparent)]
Tds(Box<TdsError>),
#[error(transparent)]
Triangulation(Box<TriangulationValidationError>),
#[error("Delaunay verification failed: {message}")]
VerificationFailed {
message: String,
},
#[error("Delaunay repair failed: {message}")]
RepairFailed {
message: String,
},
#[error("Delaunay repair failed during {operation}: {source}")]
RepairOperationFailed {
operation: DelaunayRepairOperation,
#[source]
source: Box<DelaunayRepairError>,
},
}
impl From<TdsError> for DelaunayTriangulationValidationError {
fn from(source: TdsError) -> Self {
Self::Tds(Box::new(source))
}
}
impl From<TriangulationValidationError> for DelaunayTriangulationValidationError {
fn from(source: TriangulationValidationError) -> Self {
Self::Triangulation(Box::new(source))
}
}
#[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 {
First,
Balanced,
#[default]
MaxVolume,
}
#[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>,
},
}
impl Default for RetryPolicy {
fn default() -> Self {
Self::Shuffled {
attempts: NonZeroUsize::new(DELAUNAY_SHUFFLE_ATTEMPTS)
.expect("DELAUNAY_SHUFFLE_ATTEMPTS must be non-zero"),
base_seed: None,
}
}
}
#[derive(Debug, Clone, Copy, PartialEq)]
#[non_exhaustive]
pub struct ConstructionOptions {
insertion_order: InsertionOrderStrategy,
dedup_policy: DedupPolicy,
initial_simplex: InitialSimplexStrategy,
retry_policy: RetryPolicy,
batch_repair_policy: DelaunayRepairPolicy,
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(),
batch_repair_policy: default_batch_repair_policy(),
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 batch_repair_policy(&self) -> DelaunayRepairPolicy {
self.batch_repair_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 const fn with_batch_repair_policy(
mut self,
batch_repair_policy: DelaunayRepairPolicy,
) -> Self {
self.batch_repair_policy = batch_repair_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 telemetry: ConstructionTelemetry,
pub slow_insertions: Vec<ConstructionSlowInsertionSample>,
pub skip_samples: Vec<ConstructionSkipSample>,
}
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct ConstructionSkipSample {
pub index: usize,
pub uuid: Uuid,
pub coords: Vec<f64>,
pub coords_available: bool,
pub attempts: usize,
pub error: String,
}
#[derive(Debug, Clone)]
#[non_exhaustive]
pub struct ConstructionSlowInsertionSample {
pub index: usize,
pub uuid: Uuid,
pub attempts: usize,
pub result: InsertionResult,
pub elapsed_nanos: u64,
pub cells_after: usize,
pub locate_calls: usize,
pub locate_walk_steps_total: usize,
pub conflict_region_calls: usize,
pub conflict_region_cells_total: usize,
pub cavity_insertion_calls: usize,
pub global_conflict_scans: usize,
pub hull_extension_calls: usize,
pub topology_validation_calls: usize,
}
#[derive(Debug, Clone, thiserror::Error)]
#[error("{error}")]
#[non_exhaustive]
#[must_use]
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;
const MAX_SLOW_INSERTION_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);
}
}
pub fn record_slow_insertion_sample(&mut self, sample: ConstructionSlowInsertionSample) {
let insert_at = self
.slow_insertions
.iter()
.position(|existing| sample.elapsed_nanos > existing.elapsed_nanos)
.unwrap_or(self.slow_insertions.len());
if insert_at >= Self::MAX_SLOW_INSERTION_SAMPLES {
return;
}
self.slow_insertions.insert(insert_at, sample);
self.slow_insertions
.truncate(Self::MAX_SLOW_INSERTION_SAMPLES);
}
fn merge_from(&mut self, other: &Self) {
self.inserted = self.inserted.saturating_add(other.inserted);
self.skipped_duplicate = self
.skipped_duplicate
.saturating_add(other.skipped_duplicate);
self.skipped_degeneracy = self
.skipped_degeneracy
.saturating_add(other.skipped_degeneracy);
self.total_attempts = self.total_attempts.saturating_add(other.total_attempts);
self.max_attempts = self.max_attempts.max(other.max_attempts);
if self.attempts_histogram.len() < other.attempts_histogram.len() {
self.attempts_histogram
.resize(other.attempts_histogram.len(), 0);
}
for (idx, count) in other.attempts_histogram.iter().enumerate() {
self.attempts_histogram[idx] = self.attempts_histogram[idx].saturating_add(*count);
}
self.used_perturbation = self
.used_perturbation
.saturating_add(other.used_perturbation);
self.cells_removed_total = self
.cells_removed_total
.saturating_add(other.cells_removed_total);
self.cells_removed_max = self.cells_removed_max.max(other.cells_removed_max);
self.telemetry.merge_from(&other.telemetry);
for sample in &other.skip_samples {
if self.skip_samples.len() >= Self::MAX_SKIP_SAMPLES {
break;
}
self.skip_samples.push(sample.clone());
}
for sample in &other.slow_insertions {
self.record_slow_insertion_sample(sample.clone());
}
}
#[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> {
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> {
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,
{
let mut hasher = FastHasher::default();
vertex.hash(&mut hasher);
hasher.finish()
}
fn total_cmp_for_coordinate<T>(left: &T, right: &T) -> Ordering
where
T: CoordinateScalar,
{
left.ordered_partial_cmp(right)
.expect("CoordinateScalar::ordered_partial_cmp must define a total order")
}
fn compare_vertices_by_coordinates<T, U, const D: usize>(
left: &Vertex<T, U, D>,
right: &Vertex<T, U, D>,
) -> Ordering
where
T: CoordinateScalar,
{
for (left_coord, right_coord) in left.point().coords().iter().zip(right.point().coords()) {
let ordering = total_cmp_for_coordinate(left_coord, right_coord);
if ordering != Ordering::Equal {
return ordering;
}
}
Ordering::Equal
}
fn order_vertices_lexicographic<T, U, const D: usize>(
vertices: Vec<Vertex<T, U, D>>,
) -> Vec<Vertex<T, U, D>>
where
T: CoordinateScalar,
{
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)| {
compare_vertices_by_coordinates(a, b)
.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,
{
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,
{
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,
{
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,
{
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,
{
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,
{
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: SecureHashMap<
QuantizedKey<D>,
SmallBuffer<usize, BATCH_DEDUP_BUCKET_INLINE_CAPACITY>,
> = SecureHashMap::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,
{
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 += 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 vertices_coords_f64<T, U, const D: usize>(vertices: &[Vertex<T, U, D>]) -> Option<Vec<[f64; D]>>
where
T: CoordinateScalar,
{
let mut coords_f64: Vec<[f64; D]> = Vec::with_capacity(vertices.len());
for v in vertices {
let coords = safe_coords_to_f64(v.point().coords()).ok()?;
if coords.iter().any(|coord| !coord.is_finite()) {
return None;
}
coords_f64.push(coords);
}
Some(coords_f64)
}
fn squared_distance<const D: usize>(a: &[f64; D], b: &[f64; D]) -> f64 {
a.iter()
.zip(b.iter())
.map(|(lhs, rhs)| {
let diff = lhs - rhs;
diff * diff
})
.sum::<f64>()
}
fn push_unique_index(indices: &mut Vec<usize>, idx: usize) {
if !indices.contains(&idx) {
indices.push(idx);
}
}
const fn initial_simplex_candidate_cap<const D: usize>(point_count: usize) -> usize {
let minimum = D.saturating_add(1);
let bounded_cap = if INITIAL_SIMPLEX_MAX_VOLUME_CANDIDATE_CAP > minimum {
INITIAL_SIMPLEX_MAX_VOLUME_CANDIDATE_CAP
} else {
minimum
};
let requested = D.saturating_add(1).saturating_mul(2).saturating_add(4);
let target = if requested < bounded_cap {
requested
} else {
bounded_cap
};
if point_count < target {
point_count
} else {
target
}
}
fn lexicographic_min_index<const D: usize>(coords_f64: &[[f64; D]]) -> Option<usize> {
if coords_f64.is_empty() {
return None;
}
let mut lexicographic_min = 0usize;
for idx in 1..coords_f64.len() {
if coords_f64[idx].partial_cmp(&coords_f64[lexicographic_min]) == Some(Ordering::Less) {
lexicographic_min = idx;
}
}
Some(lexicographic_min)
}
fn append_axis_extrema<const D: usize>(coords_f64: &[[f64; D]], candidates: &mut Vec<usize>) {
for axis in 0..D {
let mut min_idx = 0usize;
let mut max_idx = 0usize;
for idx in 1..coords_f64.len() {
let coord = coords_f64[idx][axis];
let min_coord = coords_f64[min_idx][axis];
let max_coord = coords_f64[max_idx][axis];
match coord.partial_cmp(&min_coord) {
Some(Ordering::Less) => min_idx = idx,
Some(Ordering::Equal)
if coords_f64[idx].partial_cmp(&coords_f64[min_idx])
== Some(Ordering::Less) =>
{
min_idx = idx;
}
_ => {}
}
match coord.partial_cmp(&max_coord) {
Some(Ordering::Greater) => max_idx = idx,
Some(Ordering::Equal)
if coords_f64[idx].partial_cmp(&coords_f64[max_idx])
== Some(Ordering::Less) =>
{
max_idx = idx;
}
_ => {}
}
}
push_unique_index(candidates, min_idx);
push_unique_index(candidates, max_idx);
}
}
fn extend_candidate_pool_by_farthest_points<const D: usize>(
coords_f64: &[[f64; D]],
candidates: &mut Vec<usize>,
candidate_cap: usize,
) {
let mut selected_mask = vec![false; coords_f64.len()];
for &idx in candidates.iter() {
selected_mask[idx] = true;
}
let mut min_dist_sq = vec![f64::INFINITY; coords_f64.len()];
for idx in 0..coords_f64.len() {
if selected_mask[idx] {
min_dist_sq[idx] = 0.0;
continue;
}
for &candidate_idx in candidates.iter() {
let dist = squared_distance(&coords_f64[idx], &coords_f64[candidate_idx]);
if dist < min_dist_sq[idx] {
min_dist_sq[idx] = dist;
}
}
}
while candidates.len() < candidate_cap {
let mut best_idx: Option<usize> = None;
let mut best_dist = -1.0_f64;
for idx in 0..coords_f64.len() {
if selected_mask[idx] {
continue;
}
let dist = min_dist_sq[idx];
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[idx].partial_cmp(&coords_f64[best_idx_val]) == Some(Ordering::Less)
}
_ => false,
});
if replace {
best_idx = Some(idx);
best_dist = dist;
}
}
let Some(best_idx) = best_idx else {
break;
};
push_unique_index(candidates, best_idx);
selected_mask[best_idx] = true;
for idx in 0..coords_f64.len() {
if selected_mask[idx] {
continue;
}
let dist = squared_distance(&coords_f64[idx], &coords_f64[best_idx]);
if dist < min_dist_sq[idx] {
min_dist_sq[idx] = dist;
}
}
}
}
fn initial_simplex_candidate_pool_indices<const D: usize>(coords_f64: &[[f64; D]]) -> Vec<usize> {
let candidate_cap = initial_simplex_candidate_cap::<D>(coords_f64.len());
if candidate_cap == 0 {
return Vec::new();
}
let mut candidates = Vec::with_capacity(candidate_cap);
if let Some(lexicographic_min) = lexicographic_min_index(coords_f64) {
push_unique_index(&mut candidates, lexicographic_min);
}
append_axis_extrema(coords_f64, &mut candidates);
extend_candidate_pool_by_farthest_points(coords_f64, &mut candidates, candidate_cap);
candidates
}
fn select_balanced_simplex_indices<T, U, const D: usize>(
vertices: &[Vertex<T, U, D>],
) -> Option<Vec<usize>>
where
T: CoordinateScalar,
{
if vertices.len() < D + 1 {
return None;
}
let coords_f64 = vertices_coords_f64(vertices)?;
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] = squared_distance(&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 = squared_distance(&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 advance_combination(indices: &mut [usize], upper: usize) -> bool {
let len = indices.len();
if len > upper {
return false;
}
for pos in (0..len).rev() {
if indices[pos] < pos + upper - len {
indices[pos] += 1;
for next in pos + 1..len {
indices[next] = indices[next - 1] + 1;
}
return true;
}
}
false
}
fn simplex_volume_for_indices<const D: usize>(
coords_f64: &[[f64; D]],
simplex_indices: &[usize],
) -> Option<f64> {
if simplex_indices.len() != D + 1 {
return None;
}
let mut points: SmallBuffer<Point<f64, D>, MAX_PRACTICAL_DIMENSION_SIZE> =
SmallBuffer::with_capacity(simplex_indices.len());
for &idx in simplex_indices {
points.push(Point::new(coords_f64[idx]));
}
simplex_volume(&points)
.ok()
.filter(|volume| volume.is_finite() && *volume > 0.0)
}
fn select_max_volume_simplex_indices<T, U, const D: usize>(
vertices: &[Vertex<T, U, D>],
) -> Option<Vec<usize>>
where
T: CoordinateScalar,
{
if vertices.len() < D + 1 {
return None;
}
let coords_f64 = vertices_coords_f64(vertices)?;
let candidates = initial_simplex_candidate_pool_indices(&coords_f64);
if candidates.len() < D + 1 {
return None;
}
let simplex_len = D + 1;
let mut combination: Vec<usize> = (0..simplex_len).collect();
let mut best_volume = 0.0_f64;
let mut best_indices: Option<Vec<usize>> = None;
loop {
let simplex_indices: SmallBuffer<usize, MAX_PRACTICAL_DIMENSION_SIZE> = combination
.iter()
.map(|&candidate_idx| candidates[candidate_idx])
.collect();
if let Some(volume) = simplex_volume_for_indices(&coords_f64, &simplex_indices)
&& volume > best_volume
{
best_volume = volume;
best_indices = Some(simplex_indices.iter().copied().collect());
}
if !advance_combination(&mut combination, candidates.len()) {
break;
}
}
best_indices
}
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: Copy,
U: Copy,
{
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)
}
fn bulk_progress_every_from_env() -> Option<usize> {
[
"DELAUNAY_BULK_PROGRESS_EVERY",
"DELAUNAY_LARGE_DEBUG_PROGRESS_EVERY",
]
.into_iter()
.find_map(|name| {
env::var(name)
.ok()
.and_then(|raw| raw.trim().parse::<usize>().ok())
})
.filter(|every| *every > 0)
}
fn construction_retry_trace_enabled() -> bool {
bulk_progress_every_from_env().is_some()
|| env::var_os("DELAUNAY_DEBUG_SHUFFLE").is_some()
|| env::var_os("DELAUNAY_INSERT_TRACE").is_some()
}
fn duration_nanos_saturating(duration: Duration) -> u64 {
u64::try_from(duration.as_nanos()).unwrap_or(u64::MAX)
}
#[derive(Clone, Copy, Debug)]
struct BatchProgressSample {
processed: usize,
inserted: usize,
skipped: usize,
cell_count: usize,
perturbation_seed: u64,
}
#[derive(Clone, Copy, Debug)]
struct BatchProgressState {
total_vertices: usize,
progress_every: usize,
started: Instant,
last_progress: Instant,
last_processed: usize,
}
fn log_bulk_progress_if_due(sample: BatchProgressSample, state: &mut Option<BatchProgressState>) {
let Some(state) = state.as_mut() else {
return;
};
if sample.processed == 0 {
return;
}
let should_log = sample.processed == state.total_vertices
|| sample.processed.is_multiple_of(state.progress_every);
if !should_log {
return;
}
let elapsed = state.started.elapsed();
let chunk_elapsed = state.last_progress.elapsed();
let chunk_processed = sample.processed.saturating_sub(state.last_processed);
let overall_rate = safe_usize_to_scalar::<f64>(sample.processed)
.ok()
.map(|processed| processed / elapsed.as_secs_f64().max(1e-9));
let chunk_rate = safe_usize_to_scalar::<f64>(chunk_processed)
.ok()
.map(|processed| processed / chunk_elapsed.as_secs_f64().max(1e-9));
tracing::debug!(
target: "delaunay::bulk_progress",
perturbation_seed = format_args!("0x{:X}", sample.perturbation_seed),
processed = sample.processed,
total_vertices = state.total_vertices,
inserted = sample.inserted,
skipped = sample.skipped,
cells = sample.cell_count,
elapsed = ?elapsed,
total_rate_pts_per_s = ?overall_rate,
recent_rate_pts_per_s = ?chunk_rate,
"bulk-construction progress"
);
state.last_progress = Instant::now();
state.last_processed = sample.processed;
}
fn log_construction_retry_start(attempt: usize, attempt_seed: u64, perturbation_seed: u64) {
if !construction_retry_trace_enabled() {
return;
}
tracing::debug!(
target: "delaunay::bulk_retry",
attempt,
attempt_seed = format_args!("0x{:X}", attempt_seed),
perturbation_seed = format_args!("0x{:X}", perturbation_seed),
"shuffled retry attempt starting"
);
}
fn log_construction_retry_result(
attempt: usize,
attempt_seed: Option<u64>,
perturbation_seed: u64,
outcome: &'static str,
error: Option<&str>,
stats: Option<&ConstructionStatistics>,
) {
if !construction_retry_trace_enabled() {
return;
}
let attempt_seed_display =
attempt_seed.map_or_else(|| String::from("input-order"), |seed| format!("0x{seed:X}"));
let error_display = error.unwrap_or("-");
if let Some(stats) = stats {
tracing::debug!(
target: "delaunay::bulk_retry",
attempt,
attempt_seed = %attempt_seed_display,
perturbation_seed = format_args!("0x{:X}", perturbation_seed),
outcome,
inserted = stats.inserted,
skipped_duplicate = stats.skipped_duplicate,
skipped_degeneracy = stats.skipped_degeneracy,
total_attempts = stats.total_attempts,
max_attempts = stats.max_attempts,
cells_removed_total = stats.cells_removed_total,
cells_removed_max = stats.cells_removed_max,
error = %error_display,
"shuffled retry attempt result (with stats)"
);
} else {
tracing::debug!(
target: "delaunay::bulk_retry",
attempt,
attempt_seed = %attempt_seed_display,
perturbation_seed = format_args!("0x{:X}", perturbation_seed),
outcome,
error = %error_display,
"shuffled retry attempt result"
);
}
}
fn vertex_coords_f64<T, U, const D: usize>(vertex: &Vertex<T, U, D>) -> Option<Vec<f64>>
where
T: CoordinateScalar,
{
vertex
.point()
.coords()
.iter()
.map(|coord| coord.to_f64().filter(|value| value.is_finite()))
.collect()
}
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,
{
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(|| compare_vertices_by_coordinates(a_vertex, b_vertex))
.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: Kernel<D>, U, V, const D: usize> {
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_options_and_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_options_and_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: 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,
batch_repair_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,
batch_repair_policy,
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,
batch_repair_policy,
use_global_repair_fallback,
);
}
}
}
Self::build_with_kernel_inner(
<K as Clone>::clone(kernel),
vertices,
topology_guarantee,
grid_cell_size,
batch_repair_policy,
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"
)]
#[expect(
clippy::too_many_lines,
reason = "Statistics constructor handles preprocessing, retry, and fallback aggregation"
)]
pub fn with_options_and_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,
batch_repair_policy,
use_global_repair_fallback,
} = options;
let preprocessing_started = Instant::now();
let preprocessed = match Self::preprocess_vertices_for_construction(
vertices,
dedup_policy,
insertion_order,
initial_simplex,
) {
Ok(preprocessed) => preprocessed,
Err(error) => {
let mut statistics = ConstructionStatistics::default();
statistics
.telemetry
.record_construction_preprocessing_timing(duration_nanos_saturating(
preprocessing_started.elapsed(),
));
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics,
});
}
};
let preprocessing_nanos = duration_nanos_saturating(preprocessing_started.elapsed());
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,
batch_repair_policy,
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,
batch_repair_policy,
use_global_repair_fallback,
);
}
}
}
Self::build_with_kernel_inner_with_construction_statistics(
<K as Clone>::clone(kernel),
vertices,
topology_guarantee,
grid_cell_size,
batch_repair_policy,
use_global_repair_fallback,
)
};
match build_with_vertices(primary_vertices) {
Ok((dt, mut stats)) => {
stats
.telemetry
.record_construction_preprocessing_timing(preprocessing_nanos);
Ok((dt, stats))
}
Err(mut primary_err) => {
let Some(fallback) = fallback_vertices else {
primary_err
.statistics
.telemetry
.record_construction_preprocessing_timing(preprocessing_nanos);
return Err(primary_err);
};
match build_with_vertices(fallback) {
Ok((dt, stats)) => {
let mut aggregate = primary_err.statistics;
aggregate.merge_from(&stats);
aggregate
.telemetry
.record_construction_preprocessing_timing(preprocessing_nanos);
Ok((dt, aggregate))
}
Err(fallback_err) => {
let mut aggregate = primary_err.statistics;
aggregate.merge_from(&fallback_err.statistics);
aggregate
.telemetry
.record_construction_preprocessing_timing(preprocessing_nanos);
Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: fallback_err.error,
statistics: aggregate,
})
}
}
}
}
}
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)
}
}
InitialSimplexStrategy::MaxVolume => {
let base = owned_vertices.unwrap_or_else(|| vertices.to_vec());
if let Some(indices) = select_max_volume_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(
DelaunayConstructionFailure::Tds {
reason: TdsConstructionFailure::DuplicateUuid { .. }
| TdsConstructionFailure::Validation { .. },
} | DelaunayConstructionFailure::InternalInconsistency { .. }
| DelaunayConstructionFailure::DelaunayRepair { .. }
| DelaunayConstructionFailure::InsertionTopologyValidation { .. }
| DelaunayConstructionFailure::FinalTopologyValidation { .. },
)
)
}
#[expect(
clippy::too_many_lines,
reason = "construction retry flow keeps seed selection, validation, and diagnostics together"
)]
#[expect(
clippy::too_many_arguments,
reason = "private construction retry helper threads orthogonal batch knobs explicitly"
)]
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>,
batch_repair_policy: DelaunayRepairPolicy,
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 = 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"
);
}
log_construction_retry_result(0, None, 0_u64, "started", None, None);
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,
batch_repair_policy,
use_global_repair_fallback,
) {
Ok(candidate) => match candidate.is_delaunay_via_flips() {
Ok(()) => {
log_construction_retry_result(0, None, 0_u64, "succeeded", None, None);
return Ok(candidate);
}
Err(err) => format!("Delaunay property violated after construction: {err}"),
},
Err(err) => {
let err_string = err.to_string();
if Self::is_non_retryable_construction_error(&err) {
log_construction_retry_result(
0,
None,
0_u64,
"failed",
Some(&err_string),
None,
);
return Err(err);
}
err_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}"
);
}
log_construction_retry_result(0, None, 0_u64, "failed", Some(&last_error), None);
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"
);
}
log_construction_retry_start(attempt, attempt_seed, perturbation_seed);
match Self::build_with_kernel_inner_seeded(
<K as Clone>::clone(kernel),
&shuffled,
topology_guarantee,
perturbation_seed,
true,
grid_cell_size,
batch_repair_policy,
use_global_repair_fallback,
) {
Ok(candidate) => match candidate.is_delaunay_via_flips() {
Ok(()) => {
log_construction_retry_result(
attempt,
Some(attempt_seed),
perturbation_seed,
"succeeded",
None,
None,
);
return Ok(candidate);
}
Err(err) => {
last_error =
format!("Delaunay property violated after construction: {err}");
}
},
Err(err) => {
let err_string = err.to_string();
if Self::is_non_retryable_construction_error(&err) {
log_construction_retry_result(
attempt,
Some(attempt_seed),
perturbation_seed,
"failed",
Some(&err_string),
None,
);
return Err(err);
}
last_error = err_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}"
);
}
log_construction_retry_result(
attempt,
Some(attempt_seed),
perturbation_seed,
"failed",
Some(&last_error),
None,
);
}
Err(TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Delaunay construction failed after shuffled reconstruction attempts: {last_error}"
),
}
.into())
}
#[expect(
clippy::too_many_lines,
reason = "statistics variant mirrors construction retry flow for comparable diagnostics"
)]
#[expect(
clippy::result_large_err,
reason = "Internal helper propagates public by-value construction-statistics error type"
)]
#[expect(
clippy::too_many_arguments,
reason = "statistics retry helper mirrors the non-statistics construction path"
)]
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>,
batch_repair_policy: DelaunayRepairPolicy,
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 = 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 aggregate_stats = ConstructionStatistics::default();
log_construction_retry_result(0, None, 0_u64, "started", None, 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,
batch_repair_policy,
use_global_repair_fallback,
) {
Ok((candidate, mut stats)) => {
let delaunay_started = Instant::now();
let delaunay_result = candidate.is_delaunay_via_flips();
stats
.telemetry
.record_construction_final_delaunay_validation_timing(
duration_nanos_saturating(delaunay_started.elapsed()),
);
match delaunay_result {
Ok(()) => {
aggregate_stats.merge_from(&stats);
log_construction_retry_result(
0,
None,
0_u64,
"succeeded",
None,
Some(&stats),
);
return Ok((candidate, aggregate_stats));
}
Err(err) => {
aggregate_stats.merge_from(&stats);
last_stats.replace(stats);
format!("Delaunay property violated after construction: {err}")
}
}
}
Err(err) => {
let DelaunayTriangulationConstructionErrorWithStatistics { error, statistics } =
err;
aggregate_stats.merge_from(&statistics);
if Self::is_non_retryable_construction_error(&error) {
let last_error = error.to_string();
log_construction_retry_result(
0,
None,
0_u64,
"failed",
Some(&last_error),
Some(&statistics),
);
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: aggregate_stats,
});
}
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}"
);
}
log_construction_retry_result(
0,
None,
0_u64,
"failed",
Some(&last_error),
last_stats.as_ref(),
);
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"
);
}
log_construction_retry_start(attempt, attempt_seed, perturbation_seed);
match Self::build_with_kernel_inner_seeded_with_construction_statistics(
<K as Clone>::clone(kernel),
&shuffled,
topology_guarantee,
perturbation_seed,
true,
grid_cell_size,
batch_repair_policy,
use_global_repair_fallback,
) {
Ok((candidate, mut stats)) => {
let delaunay_started = Instant::now();
let delaunay_result = candidate.is_delaunay_via_flips();
stats
.telemetry
.record_construction_final_delaunay_validation_timing(
duration_nanos_saturating(delaunay_started.elapsed()),
);
match delaunay_result {
Ok(()) => {
aggregate_stats.merge_from(&stats);
log_construction_retry_result(
attempt,
Some(attempt_seed),
perturbation_seed,
"succeeded",
None,
Some(&stats),
);
return Ok((candidate, aggregate_stats));
}
Err(err) => {
aggregate_stats.merge_from(&stats);
last_stats.replace(stats);
last_error =
format!("Delaunay property violated after construction: {err}");
}
}
}
Err(err) => {
let DelaunayTriangulationConstructionErrorWithStatistics { error, statistics } =
err;
aggregate_stats.merge_from(&statistics);
if Self::is_non_retryable_construction_error(&error) {
let last_error = error.to_string();
log_construction_retry_result(
attempt,
Some(attempt_seed),
perturbation_seed,
"failed",
Some(&last_error),
Some(&statistics),
);
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: aggregate_stats,
});
}
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}"
);
}
log_construction_retry_result(
attempt,
Some(attempt_seed),
perturbation_seed,
"failed",
Some(&last_error),
last_stats.as_ref(),
);
}
Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: TriangulationConstructionError::GeometricDegeneracy {
message: format!(
"Delaunay construction failed after shuffled reconstruction attempts: {last_error}"
),
}
.into(),
statistics: aggregate_stats,
})
}
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>,
batch_repair_policy: DelaunayRepairPolicy,
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,
batch_repair_policy,
use_global_repair_fallback,
)?;
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>,
batch_repair_policy: DelaunayRepairPolicy,
use_global_repair_fallback: bool,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
let (dt, mut stats) = Self::build_with_kernel_inner_seeded_with_construction_statistics(
kernel,
vertices,
topology_guarantee,
0,
true,
grid_cell_size,
batch_repair_policy,
use_global_repair_fallback,
)?;
tracing::debug!("post-construction: starting Delaunay validation (build stats)");
let delaunay_started = Instant::now();
let delaunay_result = dt.is_valid();
let delaunay_elapsed = delaunay_started.elapsed();
stats
.telemetry
.record_construction_final_delaunay_validation_timing(duration_nanos_saturating(
delaunay_elapsed,
));
tracing::debug!(
elapsed = ?delaunay_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"
)]
#[expect(
clippy::too_many_arguments,
reason = "seeded construction helper carries retry, repair, and validation knobs"
)]
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>,
batch_repair_policy: DelaunayRepairPolicy,
use_global_repair_fallback: bool,
) -> Result<(Self, ConstructionStatistics), DelaunayTriangulationConstructionErrorWithStatistics>
{
if vertices.len() < D + 1 {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error: TriangulationConstructionError::InsufficientVertices {
dimension: D,
source: 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: topology_guarantee.default_validation_policy(),
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();
let mut pending_repair_seeds: Vec<CellKey> = Vec::new();
let insert_loop_started = Instant::now();
let insert_result = dt.insert_remaining_vertices_seeded(
vertices,
perturbation_seed,
grid_cell_size,
batch_repair_policy,
Some(&mut stats),
&mut pending_repair_seeds,
&mut soft_fail_seeds,
);
stats
.telemetry
.record_construction_insert_loop_timing(duration_nanos_saturating(
insert_loop_started.elapsed(),
));
if let Err(error) = insert_result {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: stats,
});
}
let finalize_started = Instant::now();
let finalize_result = dt.finalize_bulk_construction(
original_validation_policy,
original_repair_policy,
run_final_repair,
batch_repair_policy,
&pending_repair_seeds,
&soft_fail_seeds,
Some(&mut stats.telemetry),
);
stats
.telemetry
.record_construction_finalize_timing(duration_nanos_saturating(
finalize_started.elapsed(),
));
if let Err(error) = finalize_result {
return Err(DelaunayTriangulationConstructionErrorWithStatistics {
error,
statistics: stats,
});
}
Ok((dt, stats))
}
#[expect(
clippy::too_many_arguments,
reason = "seeded construction helper carries retry, repair, and validation knobs"
)]
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>,
batch_repair_policy: DelaunayRepairPolicy,
use_global_repair_fallback: bool,
) -> Result<Self, DelaunayTriangulationConstructionError> {
if vertices.len() < D + 1 {
return Err(TriangulationConstructionError::InsufficientVertices {
dimension: D,
source: 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: topology_guarantee.default_validation_policy(),
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();
let mut pending_repair_seeds: Vec<CellKey> = Vec::new();
dt.insert_remaining_vertices_seeded(
vertices,
perturbation_seed,
grid_cell_size,
batch_repair_policy,
None,
&mut pending_repair_seeds,
&mut soft_fail_seeds,
)?;
dt.finalize_bulk_construction(
original_validation_policy,
original_repair_policy,
run_final_repair,
batch_repair_policy,
&pending_repair_seeds,
&soft_fail_seeds,
None,
)?;
Ok(dt)
}
const fn can_soft_fail(repair_err: &DelaunayRepairError) -> bool {
matches!(
repair_err,
DelaunayRepairError::NonConvergent { .. }
| DelaunayRepairError::PostconditionFailed { .. }
)
}
fn map_hard_repair_error(
index: usize,
repair_err: DelaunayRepairError,
) -> DelaunayTriangulationConstructionError {
let message =
format!("per-insertion Delaunay repair failed at index {index}: {repair_err}");
if is_geometric_repair_error(&repair_err) {
TriangulationConstructionError::GeometricDegeneracy { message }.into()
} else {
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::DelaunayRepair {
phase: DelaunayConstructionRepairPhase::BatchLocal { index },
source: Box::new(repair_err),
},
)
}
}
fn record_successful_local_repair_telemetry(
telemetry: &mut ConstructionTelemetry,
index: usize,
trigger: BatchLocalRepairTrigger,
seed_cells_len: usize,
repair_elapsed: Duration,
phase_timing: &LocalRepairPhaseTiming,
stats: &DelaunayRepairStats,
) {
telemetry.record_local_repair_work(
stats.facets_checked,
stats.flips_performed,
stats.max_queue_len,
);
telemetry.record_local_repair_sample(LocalRepairSample {
index,
trigger,
seed_cells: seed_cells_len,
elapsed_nanos: duration_nanos_saturating(repair_elapsed),
items_checked: stats.facets_checked,
flips_performed: stats.flips_performed,
max_queue_len: stats.max_queue_len,
facet_nanos: phase_timing.attempt_facet_nanos,
ridge_nanos: phase_timing.attempt_ridge_nanos,
postcondition_nanos: phase_timing.postcondition_nanos,
});
}
fn record_local_repair_attempt_telemetry(
telemetry: &mut ConstructionTelemetry,
repair_elapsed: Duration,
phase_timing: &LocalRepairPhaseTiming,
seed_cells_len: usize,
trigger: BatchLocalRepairTrigger,
) {
telemetry.record_local_repair_timing(duration_nanos_saturating(repair_elapsed));
telemetry.record_local_repair_phase_timing(phase_timing);
telemetry.record_local_repair_frontier(seed_cells_len, trigger);
}
#[expect(
clippy::too_many_lines,
reason = "local repair control flow keeps telemetry, rollback, and soft-fail handling together"
)]
fn repair_pending_local_seed_cells(
&mut self,
index: usize,
trigger: BatchLocalRepairTrigger,
pending_seed_cells: &mut Vec<CellKey>,
pending_seen: &mut FastHashSet<CellKey>,
soft_fail_seeds: &mut Vec<CellKey>,
mut construction_telemetry: Option<&mut ConstructionTelemetry>,
) -> Result<(), DelaunayTriangulationConstructionError> {
retain_live_cell_seeds(&self.tri.tds, pending_seed_cells, pending_seen);
if pending_seed_cells.is_empty() {
return Ok(());
}
#[cfg(test)]
test_hooks::record_batch_local_repair_call();
let seed_cells_len = pending_seed_cells.len();
let max_flips = local_repair_flip_budget::<D>(seed_cells_len);
let trace_repair = batch_repair_trace_enabled();
let mut phase_timing = LocalRepairPhaseTiming::default();
if trace_repair {
tracing::debug!(
idx = index,
seed_cells = seed_cells_len,
max_flips,
trigger = ?trigger,
"bulk batch repair: starting local repair"
);
}
let collect_telemetry = construction_telemetry.is_some();
let repair_started = (collect_telemetry || trace_repair).then(Instant::now);
let repair_result = {
self.invalidate_locate_hint_cache();
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
let timing = if collect_telemetry {
Some(&mut phase_timing)
} else {
None
};
repair_delaunay_local_single_pass_timed(
tds,
kernel,
pending_seed_cells,
max_flips,
timing,
)
};
#[cfg(test)]
let repair_result = if test_hooks::force_repair_nonconvergent_enabled() {
Err(test_hooks::synthetic_nonconvergent_error())
} else {
repair_result
};
let repair_elapsed = repair_started.map(|started| started.elapsed());
if let Some(telemetry) = construction_telemetry.as_mut() {
Self::record_local_repair_attempt_telemetry(
telemetry,
repair_elapsed.unwrap_or_default(),
&phase_timing,
seed_cells_len,
trigger,
);
}
match repair_result {
Ok(stats) => {
if let Some(telemetry) = construction_telemetry.as_mut() {
Self::record_successful_local_repair_telemetry(
telemetry,
index,
trigger,
seed_cells_len,
repair_elapsed.unwrap_or_default(),
&phase_timing,
&stats,
);
}
if trace_repair {
tracing::debug!(
idx = index,
seed_cells = seed_cells_len,
flips = stats.flips_performed,
checked = stats.facets_checked,
max_queue = stats.max_queue_len,
elapsed = ?repair_elapsed.unwrap_or_default(),
"bulk batch repair: local repair succeeded"
);
}
clear_cell_seed_set(pending_seed_cells, pending_seen);
}
Err(repair_err) => {
if trace_repair {
tracing::debug!(
idx = index,
seed_cells = seed_cells_len,
error = %repair_err,
elapsed = ?repair_elapsed.unwrap_or_default(),
"bulk batch repair: local repair failed"
);
}
if !Self::can_soft_fail(&repair_err) {
return Err(Self::map_hard_repair_error(index, repair_err));
}
tracing::debug!(
idx = index,
error = %repair_err,
seed_cells = seed_cells_len,
"bulk batch repair: local repair soft-failed; deferring seeds to final repair"
);
soft_fail_seeds.extend(pending_seed_cells.iter().copied());
clear_cell_seed_set(pending_seed_cells, pending_seen);
}
}
Ok(())
}
#[expect(
clippy::too_many_lines,
reason = "seeded insertion loop keeps cache repair and retry diagnostics in one flow"
)]
#[expect(
clippy::too_many_arguments,
reason = "seeded insertion loop needs batch repair and construction-statistics state"
)]
fn insert_remaining_vertices_seeded(
&mut self,
vertices: &[Vertex<K::Scalar, U, D>],
perturbation_seed: u64,
grid_cell_size: Option<K::Scalar>,
batch_repair_policy: DelaunayRepairPolicy,
construction_stats: Option<&mut ConstructionStatistics>,
pending_repair_seeds: &mut Vec<CellKey>,
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 = env::var_os("DELAUNAY_INSERT_TRACE").is_some();
let mut batch_progress = bulk_progress_every_from_env().map(|progress_every| {
let started = Instant::now();
BatchProgressState {
total_vertices: vertices.len().saturating_sub(D + 1),
progress_every,
started,
last_progress: started,
last_processed: 0,
}
});
let mut inserted_vertices = 0usize;
let mut skipped_vertices = 0usize;
let mut pending_repair_seen: FastHashSet<CellKey> =
pending_repair_seeds.iter().copied().collect();
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_coords_f64(vertex)).flatten();
if trace_insertion && let Some(coords) = coords.as_ref() {
tracing::debug!(index, %uuid, coords = ?coords, "[bulk] start");
}
let started = trace_insertion.then(Instant::now);
let mut insert = || {
self.tri.insert_with_statistics_seeded_indexed_detailed(
*vertex,
None,
self.insertion_state.last_inserted_cell,
perturbation_seed,
grid_index.as_mut(),
Some(index),
)
};
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());
let insert_result = insert_result.map(|detail| {
let repair_seed_cells = detail.repair_seed_cells;
(
detail.outcome,
detail.stats,
repair_seed_cells,
detail.delaunay_repair_required,
)
});
match insert_result {
Ok((
InsertionOutcome::Inserted {
vertex_key: _,
hint,
},
_stats,
repair_seed_cells,
delaunay_repair_required,
)) => {
inserted_vertices = inserted_vertices.saturating_add(1);
if trace_insertion && let Some(elapsed) = elapsed {
tracing::debug!(index, %uuid, elapsed = ?elapsed, "[bulk] inserted");
}
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 delaunay_repair_required
&& batch_repair_policy != DelaunayRepairPolicy::Never
&& TopologicalOperation::FacetFlip.is_admissible_under(topology)
&& self.tri.tds.number_of_cells() > 0
{
accumulate_live_cell_seeds(
&self.tri.tds,
&repair_seed_cells,
pending_repair_seeds,
&mut pending_repair_seen,
);
if let Some(trigger) = batch_local_repair_trigger::<D>(
batch_repair_policy,
inserted_vertices,
topology,
pending_repair_seeds.len(),
) {
self.repair_pending_local_seed_cells(
index,
trigger,
pending_repair_seeds,
&mut pending_repair_seen,
soft_fail_seeds,
None,
)?;
}
}
log_bulk_progress_if_due(
BatchProgressSample {
processed: offset + 1,
inserted: inserted_vertices,
skipped: skipped_vertices,
cell_count: self.tri.tds.number_of_cells(),
perturbation_seed,
},
&mut batch_progress,
);
}
Ok((
InsertionOutcome::Skipped { error },
stats,
_repair_seed_cells,
_delaunay_repair_required,
)) => {
skipped_vertices = skipped_vertices.saturating_add(1);
if trace_insertion && let Some(elapsed) = elapsed {
tracing::debug!(
index,
%uuid,
attempts = stats.attempts,
elapsed = ?elapsed,
error = %error,
"[bulk] skipped"
);
}
#[cfg(debug_assertions)]
tracing::debug!(
attempts = stats.attempts,
error = %error,
"SKIPPED: vertex insertion during construction"
);
#[cfg(not(debug_assertions))]
{
let _ = (error, stats);
}
log_bulk_progress_if_due(
BatchProgressSample {
processed: offset + 1,
inserted: inserted_vertices,
skipped: skipped_vertices,
cell_count: self.tri.tds.number_of_cells(),
perturbation_seed,
},
&mut batch_progress,
);
}
Err(e) => {
if trace_insertion && let Some(elapsed) = elapsed {
tracing::debug!(
index,
%uuid,
elapsed = ?elapsed,
error = %e,
"[bulk] failed"
);
}
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_coords_f64(vertex)).flatten();
if trace_insertion && let Some(coords) = coords.as_ref() {
tracing::debug!(index, %uuid, coords = ?coords, "[bulk] start");
}
let started = Instant::now();
let mut insert = || {
self.tri
.insert_with_statistics_seeded_indexed_detailed_with_telemetry(
*vertex,
None,
self.insertion_state.last_inserted_cell,
perturbation_seed,
grid_index.as_mut(),
Some(index),
InsertionTelemetryMode::CountsAndTimings,
)
};
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.elapsed();
let elapsed_nanos = duration_nanos_saturating(elapsed);
let insert_result = insert_result.map(|detail| {
let repair_seed_cells = detail.repair_seed_cells;
(
detail.outcome,
detail.stats,
repair_seed_cells,
detail.delaunay_repair_required,
detail.telemetry,
)
});
match insert_result {
Ok((
InsertionOutcome::Inserted {
vertex_key: _,
hint,
},
stats,
repair_seed_cells,
delaunay_repair_required,
telemetry,
)) => {
inserted_vertices = inserted_vertices.saturating_add(1);
if trace_insertion {
tracing::debug!(
index,
%uuid,
attempts = stats.attempts,
elapsed = ?elapsed,
"[bulk] inserted"
);
}
construction_stats.record_insertion(&stats);
construction_stats.telemetry.record_insertion(&telemetry);
construction_stats
.telemetry
.record_insertion_timing(elapsed_nanos);
construction_stats.record_slow_insertion_sample(
ConstructionSlowInsertionSample {
index,
uuid,
attempts: stats.attempts,
result: stats.result,
elapsed_nanos,
cells_after: self.tri.tds.number_of_cells(),
locate_calls: telemetry.locate_calls,
locate_walk_steps_total: telemetry.locate_walk_steps_total,
conflict_region_calls: telemetry.conflict_region_calls,
conflict_region_cells_total: telemetry
.conflict_region_cells_total,
cavity_insertion_calls: telemetry.cavity_insertion_calls,
global_conflict_scans: telemetry.global_conflict_scans,
hull_extension_calls: telemetry.hull_extension_calls,
topology_validation_calls: telemetry.topology_validation_calls,
},
);
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 delaunay_repair_required
&& batch_repair_policy != DelaunayRepairPolicy::Never
&& TopologicalOperation::FacetFlip.is_admissible_under(topology)
&& self.tri.tds.number_of_cells() > 0
{
let seed_started = Instant::now();
let seed_cells_added = accumulate_live_cell_seeds(
&self.tri.tds,
&repair_seed_cells,
pending_repair_seeds,
&mut pending_repair_seen,
);
construction_stats
.telemetry
.record_repair_seed_accumulation(
duration_nanos_saturating(seed_started.elapsed()),
seed_cells_added,
);
if let Some(trigger) = batch_local_repair_trigger::<D>(
batch_repair_policy,
inserted_vertices,
topology,
pending_repair_seeds.len(),
) {
self.repair_pending_local_seed_cells(
index,
trigger,
pending_repair_seeds,
&mut pending_repair_seen,
soft_fail_seeds,
Some(&mut construction_stats.telemetry),
)?;
}
}
log_bulk_progress_if_due(
BatchProgressSample {
processed: offset + 1,
inserted: inserted_vertices,
skipped: skipped_vertices,
cell_count: self.tri.tds.number_of_cells(),
perturbation_seed,
},
&mut batch_progress,
);
}
Ok((
InsertionOutcome::Skipped { error },
stats,
_repair_seed_cells,
_delaunay_repair_required,
telemetry,
)) => {
skipped_vertices = skipped_vertices.saturating_add(1);
if trace_insertion {
tracing::debug!(
index,
%uuid,
attempts = stats.attempts,
elapsed = ?elapsed,
error = %error,
"[bulk] skipped"
);
}
construction_stats.record_insertion(&stats);
construction_stats.telemetry.record_insertion(&telemetry);
construction_stats
.telemetry
.record_insertion_timing(elapsed_nanos);
construction_stats.record_slow_insertion_sample(
ConstructionSlowInsertionSample {
index,
uuid,
attempts: stats.attempts,
result: stats.result,
elapsed_nanos,
cells_after: self.tri.tds.number_of_cells(),
locate_calls: telemetry.locate_calls,
locate_walk_steps_total: telemetry.locate_walk_steps_total,
conflict_region_calls: telemetry.conflict_region_calls,
conflict_region_cells_total: telemetry
.conflict_region_cells_total,
cavity_insertion_calls: telemetry.cavity_insertion_calls,
global_conflict_scans: telemetry.global_conflict_scans,
hull_extension_calls: telemetry.hull_extension_calls,
topology_validation_calls: telemetry.topology_validation_calls,
},
);
let (coords, coords_available) = vertex_coords_f64(vertex)
.map_or_else(|| (Vec::new(), false), |coords| (coords, true));
construction_stats.record_skip_sample(ConstructionSkipSample {
index,
uuid: vertex.uuid(),
coords,
coords_available,
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);
}
log_bulk_progress_if_due(
BatchProgressSample {
processed: offset + 1,
inserted: inserted_vertices,
skipped: skipped_vertices,
cell_count: self.tri.tds.number_of_cells(),
perturbation_seed,
},
&mut batch_progress,
);
}
Err(e) => {
if trace_insertion {
tracing::debug!(
index,
%uuid,
elapsed = ?elapsed,
error = %e,
"[bulk] failed"
);
}
return Err(Self::map_insertion_error(e).into());
}
}
}
}
}
self.spatial_index = grid_index;
Ok(())
}
#[expect(
clippy::too_many_arguments,
reason = "bulk finalization restores policies, repair state, and optional statistics telemetry"
)]
fn finalize_bulk_construction(
&mut self,
original_validation_policy: ValidationPolicy,
original_repair_policy: DelaunayRepairPolicy,
run_final_repair: bool,
batch_repair_policy: DelaunayRepairPolicy,
pending_repair_seeds: &[CellKey],
soft_fail_seeds: &[CellKey],
mut construction_telemetry: Option<&mut ConstructionTelemetry>,
) -> Result<(), DelaunayTriangulationConstructionError> {
self.tri.validation_policy = original_validation_policy;
self.insertion_state.delaunay_repair_policy = original_repair_policy;
let has_cells = self.tri.tds.number_of_cells() > 0;
let mut completion_seed_cells = Vec::new();
let mut completion_seen = FastHashSet::default();
for &cell_key in pending_repair_seeds.iter().chain(soft_fail_seeds.iter()) {
if self.tri.tds.contains_cell(cell_key) && completion_seen.insert(cell_key) {
completion_seed_cells.push(cell_key);
}
}
if run_final_repair
&& has_cells
&& batch_repair_policy != DelaunayRepairPolicy::Never
&& !completion_seed_cells.is_empty()
{
let repair_started = Instant::now();
let repair_result = self.run_seeded_completion_repair(&completion_seed_cells);
if let Some(telemetry) = construction_telemetry.as_mut() {
telemetry.record_construction_completion_repair_timing(duration_nanos_saturating(
repair_started.elapsed(),
));
}
repair_result?;
}
let orientation_started = Instant::now();
let orientation_result = self
.tri
.normalize_and_promote_positive_orientation()
.map_err(Self::map_orientation_canonicalization_error);
if let Some(telemetry) = construction_telemetry.as_mut() {
telemetry.record_construction_orientation_timing(duration_nanos_saturating(
orientation_started.elapsed(),
));
}
orientation_result?;
tracing::debug!("post-construction: starting topology validation (finalize)");
let validation_started = Instant::now();
let validation_result = self.tri.validate();
let validation_elapsed = validation_started.elapsed();
if let Some(telemetry) = construction_telemetry.as_mut() {
telemetry.record_construction_topology_validation_timing(duration_nanos_saturating(
validation_elapsed,
));
}
tracing::debug!(
elapsed = ?validation_elapsed,
success = validation_result.is_ok(),
"post-construction: topology validation (finalize) completed"
);
if let Err(err) = validation_result {
return Err(TriangulationConstructionError::FinalTopologyValidation {
message: "topology validation failed after construction".to_string(),
source: err.into(),
}
.into());
}
Ok(())
}
fn run_seeded_completion_repair(
&mut self,
completion_seed_cells: &[CellKey],
) -> Result<(), DelaunayTriangulationConstructionError> {
let seed_count = completion_seed_cells.len();
let max_flips = local_repair_flip_budget::<D>(seed_count);
tracing::debug!(
seed_count,
max_flips,
"post-construction: starting seeded completion Delaunay repair"
);
let repair_started = Instant::now();
let repair_result = {
self.invalidate_locate_hint_cache();
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_local_single_pass(tds, kernel, completion_seed_cells, max_flips)
};
let repair_outcome = match repair_result {
Ok(_) => Ok(()),
Err(error) => self.try_final_global_repair_after_seeded_failure(&error),
};
tracing::debug!(
elapsed = ?repair_started.elapsed(),
success = repair_outcome.is_ok(),
"post-construction: seeded completion Delaunay repair finished"
);
repair_outcome
}
fn try_final_global_repair_after_seeded_failure(
&mut self,
seeded_error: &DelaunayRepairError,
) -> Result<(), DelaunayTriangulationConstructionError> {
if !self.insertion_state.use_global_repair_fallback || !Self::can_soft_fail(seeded_error) {
let message = format!("Delaunay repair failed after construction: {seeded_error}");
return Err(Self::map_completion_repair_error(
message,
seeded_error.clone(),
));
}
tracing::debug!(
error = %seeded_error,
"post-construction: seeded completion repair soft-failed; trying final global repair"
);
self.invalidate_locate_hint_cache();
let topology = self.tri.topology_guarantee();
let global_result = {
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_with_flips_k2_k3(tds, kernel, None, topology, None)
};
match global_result {
Ok(_) => Ok(()),
Err(global_error) => {
let message = format!(
"Delaunay repair failed after construction: seeded local error: \
{seeded_error}; global fallback: {global_error}"
);
Err(Self::map_completion_repair_error(message, global_error))
}
}
}
fn map_completion_repair_error(
message: String,
repair_error: DelaunayRepairError,
) -> DelaunayTriangulationConstructionError {
if is_geometric_repair_error(&repair_error) {
TriangulationConstructionError::GeometricDegeneracy { message }.into()
} else {
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::DelaunayRepair {
phase: DelaunayConstructionRepairPhase::Completion,
source: Box::new(repair_error),
},
)
}
}
fn map_orientation_canonicalization_error(
error: InsertionError,
) -> TriangulationConstructionError {
match error {
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}"
),
}
}
InsertionError::DelaunayRepairFailed { source, context } => {
let message = format!(
"Failed to canonicalize orientation after post-construction repair: \
Delaunay repair failed ({context}): {source}"
);
if is_geometric_repair_error(&source) {
TriangulationConstructionError::GeometricDegeneracy { message }
} else {
TriangulationConstructionError::InternalInconsistency { message }
}
}
error @ (InsertionError::ConflictRegion(_)
| InsertionError::Location(_)
| InsertionError::NonManifoldTopology { .. }
| InsertionError::HullExtension { .. }
| InsertionError::DelaunayValidationFailed { .. }
| 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::CavityFilling { reason } => {
TriangulationConstructionError::FailedToCreateCell {
message: reason.to_string(),
}
}
InsertionError::NeighborWiring { reason } => {
TriangulationConstructionError::InternalInconsistency {
message: format!("Neighbor wiring failed: {reason}"),
}
}
InsertionError::TopologyValidation(source) => {
TriangulationConstructionError::from(TdsConstructionError::ValidationError(source))
}
InsertionError::DuplicateUuid { entity, uuid } => {
TriangulationConstructionError::from(TdsConstructionError::DuplicateUuid {
entity,
uuid,
})
}
InsertionError::DuplicateCoordinates { coordinates } => {
TriangulationConstructionError::DuplicateCoordinates { coordinates }
}
InsertionError::DelaunayRepairFailed { source, context } => {
let message = format!("Delaunay repair failed ({context}): {source}");
if is_geometric_repair_error(&source) {
TriangulationConstructionError::GeometricDegeneracy { message }
} else {
TriangulationConstructionError::InternalInconsistency { message }
}
}
InsertionError::ConflictRegion(source) => {
TriangulationConstructionError::InsertionConflictRegion { source }
}
InsertionError::Location(source) => {
TriangulationConstructionError::InsertionLocation { source }
}
InsertionError::NonManifoldTopology {
facet_hash,
cell_count,
} => TriangulationConstructionError::InsertionNonManifoldTopology {
facet_hash,
cell_count,
},
InsertionError::HullExtension { reason } => {
TriangulationConstructionError::InsertionHullExtension { reason }
}
InsertionError::DelaunayValidationFailed { source } => {
TriangulationConstructionError::InsertionDelaunayValidation { source }
}
InsertionError::TopologyValidationFailed { message, source } => {
TriangulationConstructionError::InsertionTopologyValidation { message, source }
}
}
}
}
impl<K, U, V, const D: usize> DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
{
#[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.invalidate_repair_caches();
&mut self.tri.tds
}
pub(crate) const fn invalidate_locate_hint_cache(&mut self) {
self.insertion_state.last_inserted_cell = None;
}
pub(crate) fn invalidate_repair_caches(&mut self) {
self.invalidate_locate_hint_cache();
self.spatial_index = None;
}
pub(crate) fn tds_mut_for_repair(&mut self) -> &mut Tds<K::Scalar, U, V, D> {
self.invalidate_repair_caches();
&mut self.tri.tds
}
#[must_use]
pub const fn as_triangulation(&self) -> &Triangulation<K, U, V, D> {
&self.tri
}
#[must_use]
#[deprecated(
since = "0.7.7",
note = "use safe DelaunayTriangulation APIs or read-only as_triangulation(); this mutable escape hatch is planned for removal in 0.8.0"
)]
pub fn as_triangulation_mut(&mut self) -> &mut Triangulation<K, U, V, D> {
self.invalidate_repair_caches();
&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<D>,
U: DataType,
V: DataType,
{
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<D>,
U: DataType,
V: DataType,
{
#[cfg(test)]
if test_hooks::force_repair_nonconvergent_enabled() {
return Err(test_hooks::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)",
});
}
self.invalidate_locate_hint_cache();
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>
where
U: DataType,
V: DataType,
{
self.tri
.normalize_and_promote_positive_orientation()
.map_err(|e| DelaunayRepairError::OrientationCanonicalizationFailed {
message: format!("after flip repair: {e}"),
})
}
fn repair_delaunay_with_flips_robust(
&mut self,
seed_cells: Option<&[CellKey]>,
max_flips: Option<usize>,
) -> Result<DelaunayRepairStats, DelaunayRepairError>
where
U: DataType,
V: DataType,
{
self.repair_delaunay_with_flips_robust_run(seed_cells, max_flips)
.map(|run| run.stats)
}
fn repair_delaunay_with_flips_robust_run(
&mut self,
seed_cells: Option<&[CellKey]>,
max_flips: Option<usize>,
) -> Result<DelaunayRepairRun, DelaunayRepairError>
where
U: DataType,
V: DataType,
{
let topology = self.tri.topology_guarantee();
let kernel = RobustKernel::<K::Scalar>::new();
self.invalidate_locate_hint_cache();
let (tds, kernel) = (&mut self.tri.tds, &kernel);
repair_delaunay_with_flips_k2_k3_run(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
)
}
fn should_run_delaunay_repair_after_mutation(&self, topology: TopologyGuarantee) -> bool {
if D < 2 {
return false;
}
if self.tri.tds.number_of_cells() == 0 {
return false;
}
if self.insertion_state.delaunay_repair_policy == DelaunayRepairPolicy::Never {
return false;
}
TopologicalOperation::FacetFlip.is_admissible_under(topology)
}
#[cfg_attr(
not(test),
expect(
clippy::missing_const_for_fn,
reason = "runtime feature and environment checks should remain ordinary functions"
)
)]
fn force_heuristic_rebuild_enabled() -> bool {
#[cfg(test)]
{
test_hooks::force_heuristic_rebuild_enabled()
}
#[cfg(not(test))]
{
false
}
}
}
impl<K, U, V, const D: usize> DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
K::Scalar: NumCast,
U: DataType,
V: DataType,
{
pub fn repair_delaunay_with_flips_advanced(
&mut self,
config: DelaunayRepairHeuristicConfig,
) -> Result<DelaunayRepairOutcome, DelaunayRepairError>
where
K: ExactPredicates<D>,
{
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),
}
}
#[expect(
clippy::too_many_lines,
reason = "heuristic rebuild keeps point extraction, reconstruction, and validation together"
)]
fn rebuild_with_heuristic(
&self,
base_seeds: DelaunayRepairHeuristicSeeds,
max_flips_override: Option<usize>,
) -> Result<(Self, DelaunayRepairStats, DelaunayRepairHeuristicSeeds), DelaunayRepairError>
where
K: ExactPredicates<D>,
{
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_guarantee = self.tri.topology_guarantee();
let global_topology = self.tri.global_topology();
let mut candidate = Self::with_empty_kernel_and_topology_guarantee(
self.tri.kernel.clone(),
topology_guarantee,
);
candidate.set_global_topology(global_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 insert_detail = {
let (tri, spatial_index) =
(&mut candidate.tri, &mut candidate.spatial_index);
tri.insert_with_statistics_seeded_indexed_detailed(
vertex,
None,
hint,
seeds.perturbation_seed,
spatial_index.as_mut(),
Some(idx),
)
.map_err(|e| DelaunayRepairError::HeuristicRebuildFailed {
message: format!(
"heuristic rebuild insertion failed at idx={idx} uuid={uuid} coords={coords:?}: {e}"
),
})?
};
let repair_seed_cells = insert_detail.repair_seed_cells;
let delaunay_repair_required = insert_detail.delaunay_repair_required;
match insert_detail.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);
if delaunay_repair_required {
candidate
.maybe_repair_after_insertion_capped(
vertex_key,
hint,
&repair_seed_cells,
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();
candidate.invalidate_locate_hint_cache();
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)
}
}
impl<K, U, V, const D: usize> DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
U: DataType,
V: DataType,
{
#[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)
}
}
impl<K, U, V, const D: usize> DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
K::Scalar: NumCast,
U: DataType,
V: DataType,
{
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_for_rollback(), self.insertion_state));
let insertion_result = (|| {
let hint = self.insertion_state.last_inserted_cell;
let insert_detail = {
let (tri, spatial_index) = (&mut self.tri, &mut self.spatial_index);
tri.insert_with_statistics_seeded_indexed_detailed(
vertex,
None,
hint,
0,
spatial_index.as_mut(),
None,
)?
};
let repair_seed_cells = insert_detail.repair_seed_cells;
let delaunay_repair_required = insert_detail.delaunay_repair_required;
match insert_detail.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);
if delaunay_repair_required {
self.maybe_repair_after_insertion(v_key, hint, &repair_seed_cells)?;
}
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)) = snapshot {
self.spatial_index = None;
self.tri.tds = tds;
self.insertion_state = insertion_state;
}
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_for_rollback(), self.insertion_state));
let insertion_result = (|| {
let hint = self.insertion_state.last_inserted_cell;
let insert_detail = {
let (tri, spatial_index) = (&mut self.tri, &mut self.spatial_index);
tri.insert_with_statistics_seeded_indexed_detailed(
vertex,
None,
hint,
0,
spatial_index.as_mut(),
None,
)?
};
let stats = insert_detail.stats;
let repair_seed_cells = insert_detail.repair_seed_cells;
let delaunay_repair_required = insert_detail.delaunay_repair_required;
let outcome = match insert_detail.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);
if delaunay_repair_required {
self.maybe_repair_after_insertion(vertex_key, hint, &repair_seed_cells)?;
}
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)) = snapshot {
self.spatial_index = None;
self.tri.tds = tds;
self.insertion_state = insertion_state;
}
Err(err)
}
}
}
fn maybe_repair_after_insertion(
&mut self,
vertex_key: VertexKey,
hint: Option<CellKey>,
extra_seed_cells: &[CellKey],
) -> Result<(), InsertionError> {
self.maybe_repair_after_insertion_capped(vertex_key, hint, extra_seed_cells, None)
}
fn maybe_repair_after_insertion_capped(
&mut self,
vertex_key: VertexKey,
hint: Option<CellKey>,
extra_seed_cells: &[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 = self.collect_local_repair_seed_cells(vertex_key, extra_seed_cells);
let hint_seed = hint.and_then(|ck| {
if !self.tri.tds.contains_cell(ck) {
if 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
.cell(ck)
.is_some_and(|cell| cell.contains_vertex(vertex_key));
if !contains_vertex && 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 = {
self.invalidate_locate_hint_cache();
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_with_flips_k2_k3_run(tds, kernel, seed_ref, topology, max_flips)
};
#[cfg(test)]
let repair_result = if test_hooks::force_repair_nonconvergent_enabled() {
Err(test_hooks::synthetic_nonconvergent_error())
} else {
repair_result
};
match repair_result {
Ok(run) => {
self.validate_ridge_links_after_repair(topology, &run)?;
}
Err(
e @ (DelaunayRepairError::NonConvergent { .. }
| DelaunayRepairError::PostconditionFailed { .. }),
) => {
let robust_run = self
.repair_delaunay_with_flips_robust_run(seed_ref, max_flips)
.map_err(|robust_err| InsertionError::DelaunayRepairFailed {
source: Box::new(robust_err),
context: DelaunayRepairFailureContext::LocalRepairRobustFallback {
initial: DelaunayRepairErrorSummary::from(&e),
},
})?;
self.validate_ridge_links_after_repair(topology, &robust_run)?;
}
Err(e) => {
return Err(InsertionError::DelaunayRepairFailed {
source: Box::new(e),
context: DelaunayRepairFailureContext::LocalRepairNonRecoverable,
});
}
}
self.tri.normalize_and_promote_positive_orientation()?;
self.tri
.validate_geometric_cell_orientation()
.map_err(InsertionError::TopologyValidation)?;
Ok(())
}
fn validate_ridge_links_after_repair(
&self,
topology: TopologyGuarantee,
run: &DelaunayRepairRun,
) -> Result<(), InsertionError> {
if !topology.requires_ridge_links() || run.stats.flips_performed == 0 {
return Ok(());
}
let validate_cells = |cells: &[CellKey]| {
if cells.is_empty() {
return Ok(());
}
validate_ridge_links_for_cells(&self.tri.tds, cells)
.map_err(ridge_link_repair_validation_error)
};
if !run.touched_cells.is_empty() {
if run.used_full_reseed && env::var_os("DELAUNAY_REPAIR_TRACE").is_some() {
tracing::debug!(
"[repair] validating ridge links on {} flip-created cells after full reseed",
run.touched_cells.len()
);
}
return validate_cells(&run.touched_cells);
}
let validation_cells: Vec<CellKey> = self.tri.tds.cell_keys().collect();
validate_cells(&validation_cells)
}
fn collect_local_repair_seed_cells(
&self,
vertex_key: VertexKey,
extra_seed_cells: &[CellKey],
) -> Vec<CellKey> {
let mut seen: FastHashSet<CellKey> = FastHashSet::default();
let mut seed_cells = Vec::new();
for cell_key in self.tri.adjacent_cells(vertex_key) {
if seen.insert(cell_key) {
seed_cells.push(cell_key);
}
}
for &cell_key in extra_seed_cells {
if self.tri.tds.contains_cell(cell_key) && seen.insert(cell_key) {
seed_cells.push(cell_key);
}
}
seed_cells
}
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: e })
}
pub fn remove_vertex(&mut self, vertex_key: VertexKey) -> Result<usize, InvariantError> {
let Some(removed_vertex) = self.tri.tds.vertex(vertex_key) else {
return Ok(0);
};
let removed_vertex_coords = *removed_vertex.point().coords();
let snapshot = (self.tri.tds.clone_for_rollback(), self.insertion_state);
let result = (|| {
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 { reason }) => {
return Err(TdsError::InvalidNeighbors {
reason: NeighborValidationError::FlipNeighborWiring {
reason: Box::new(reason),
},
}
.into());
}
Err(_) => self.tri.remove_vertex(vertex_key)?,
};
let topology = self.tri.topology_guarantee();
if self.should_run_delaunay_repair_after_mutation(topology) {
let seed_ref = seed_cells.as_deref();
let repair_result = {
self.invalidate_locate_hint_cache();
let (tds, kernel) = (&mut self.tri.tds, &self.tri.kernel);
repair_delaunay_with_flips_k2_k3(tds, kernel, seed_ref, topology, None)
};
#[cfg(test)]
let repair_result = if test_hooks::force_repair_nonconvergent_enabled() {
Err(test_hooks::synthetic_nonconvergent_error())
} else {
repair_result
};
repair_result.map_err(|source| {
InvariantError::Delaunay(
DelaunayTriangulationValidationError::RepairOperationFailed {
operation: DelaunayRepairOperation::VertexRemoval,
source: Box::new(source),
},
)
})?;
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)
})();
match result {
Ok(cells_removed) => {
self.insertion_state.last_inserted_cell = None;
if let Some(index) = self.spatial_index.as_mut() {
index.remove_vertex(&vertex_key, &removed_vertex_coords);
}
Ok(cells_removed)
}
Err(err) => {
let (tds, insertion_state) = snapshot;
self.tri.tds = tds;
self.insertion_state = insertion_state;
Err(err)
}
}
}
}
impl<K, U, V, const D: usize> DelaunayTriangulation<K, U, V, D>
where
K: Kernel<D>,
U: DataType,
V: DataType,
{
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> {
verify_delaunay_for_triangulation(&self.tri)
}
pub fn validate(&self) -> Result<(), DelaunayTriangulationValidationError> {
self.tri.validate().map_err(|e| match e {
InvariantError::Tds(tds_err) => tds_err.into(),
InvariantError::Triangulation(tri_err) => tri_err.into(),
InvariantError::Delaunay(dt_err) => dt_err,
})?;
self.is_valid()
}
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_delaunay_via_flips() {
report.violations.push(InvariantViolation {
kind: InvariantKind::DelaunayProperty,
error: InvariantError::Delaunay(
DelaunayTriangulationValidationError::VerificationFailed {
message: e.to_string(),
},
),
});
}
if report.violations.is_empty() {
Ok(())
} else {
Err(report)
}
}
}
}
pub fn try_from_tds(
tds: Tds<K::Scalar, U, V, D>,
kernel: K,
) -> Result<Self, DelaunayTriangulationValidationError> {
Self::try_from_tds_with_topology_context(
tds,
kernel,
TopologyGuarantee::DEFAULT,
GlobalTopology::DEFAULT,
)
}
pub fn try_from_tds_with_topology_guarantee(
tds: Tds<K::Scalar, U, V, D>,
kernel: K,
topology_guarantee: TopologyGuarantee,
) -> Result<Self, DelaunayTriangulationValidationError> {
Self::try_from_tds_with_topology_context(
tds,
kernel,
topology_guarantee,
GlobalTopology::DEFAULT,
)
}
pub fn try_from_tds_with_topology_context(
tds: Tds<K::Scalar, U, V, D>,
kernel: K,
topology_guarantee: TopologyGuarantee,
global_topology: GlobalTopology<D>,
) -> Result<Self, DelaunayTriangulationValidationError> {
let mut candidate = Self::from_tds_with_topology_guarantee(tds, kernel, topology_guarantee);
candidate.set_global_topology(global_topology);
candidate.tri.validate().map_err(|e| match e {
InvariantError::Tds(tds_err) => tds_err.into(),
InvariantError::Triangulation(tri_err) => tri_err.into(),
InvariantError::Delaunay(dt_err) => dt_err,
})?;
if candidate.global_topology().is_euclidean() {
is_delaunay_property_only(&candidate.tri.tds).map_err(|e| {
DelaunayTriangulationValidationError::VerificationFailed {
message: format!("kernel-independent reconstruction validation failed: {e}"),
}
})?;
} else {
candidate.is_valid()?;
}
Ok(candidate)
}
#[must_use]
pub(crate) const fn from_tds_with_topology_guarantee(
tds: Tds<K::Scalar, U, V, D>,
kernel: K,
topology_guarantee: TopologyGuarantee,
) -> Self {
let validation_policy = topology_guarantee.default_validation_policy();
Self {
tri: Triangulation {
kernel,
tds,
global_topology: GlobalTopology::DEFAULT,
validation_policy,
topology_guarantee,
},
insertion_state: DelaunayInsertionState::new(),
spatial_index: None,
}
}
}
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)?;
Self::try_from_tds(tds, RobustKernel::new()).map_err(serde::de::Error::custom)
}
}
#[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 => insertion_count != 0,
Self::EveryN(n) => insertion_count != 0 && 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, DelaunayRepairVerificationContext,
FlipContextError, FlipError, FlipPredicateError, FlipPredicateOperation, RepairQueueOrder,
verify_delaunay_via_flip_predicates,
};
use crate::core::algorithms::incremental_insertion::{
CavityFillingError, HullExtensionReason, NeighborWiringError,
};
use crate::core::algorithms::locate::{ConflictError, LocateError};
use crate::core::operations::InsertionResult;
use crate::core::tds::{EntityKind, GeometricError, TriangulationConstructionState};
use crate::core::vertex::VertexBuilder;
use crate::geometry::kernel::{AdaptiveKernel, FastKernel, RobustKernel};
use crate::geometry::point::Point;
use crate::geometry::traits::coordinate::{Coordinate, CoordinateConversionError};
use crate::topology::characteristics::euler::TopologyClassification;
use crate::topology::traits::topological_space::ToroidalConstructionMode;
use crate::triangulation::flips::BistellarFlips;
use crate::vertex;
use slotmap::KeyData;
use std::{collections::HashSet, error::Error as StdError, sync::Once};
type TestDelaunay<const D: usize> = DelaunayTriangulation<AdaptiveKernel<f64>, (), (), D>;
fn init_tracing() {
static INIT: Once = 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();
});
}
fn wedge_two_spheres_share_vertex_tds_2d() -> (Tds<f64, (), (), 2>, CellKey, CellKey) {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([1.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([0.0, 1.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([1.0, 1.0])).unwrap();
let incident = tds
.insert_cell_with_mapping(Cell::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
let _ = tds
.insert_cell_with_mapping(Cell::new(vec![v0, v1, v3], None).unwrap())
.unwrap();
let _ = tds
.insert_cell_with_mapping(Cell::new(vec![v0, v2, v3], None).unwrap())
.unwrap();
let nonincident = tds
.insert_cell_with_mapping(Cell::new(vec![v1, v2, v3], None).unwrap())
.unwrap();
let v4 = tds
.insert_vertex_with_mapping(vertex!([10.0, 10.0]))
.unwrap();
let v5 = tds
.insert_vertex_with_mapping(vertex!([11.0, 10.0]))
.unwrap();
let v6 = tds
.insert_vertex_with_mapping(vertex!([10.0, 11.0]))
.unwrap();
let _ = tds
.insert_cell_with_mapping(Cell::new(vec![v0, v4, v5], None).unwrap())
.unwrap();
let _ = tds
.insert_cell_with_mapping(Cell::new(vec![v0, v4, v6], None).unwrap())
.unwrap();
let _ = tds
.insert_cell_with_mapping(Cell::new(vec![v0, v5, v6], None).unwrap())
.unwrap();
let _ = tds
.insert_cell_with_mapping(Cell::new(vec![v4, v5, v6], None).unwrap())
.unwrap();
(tds, incident, nonincident)
}
#[test]
fn test_ridge_link_repair_validation_error_routes_tds_errors_to_tds_layer() {
let tds_err = TdsError::InvalidNeighbors {
reason: NeighborValidationError::Other {
message: "unit test".to_string(),
},
};
match ridge_link_repair_validation_error(ManifoldError::Tds(tds_err.clone())) {
InsertionError::TopologyValidation(source) => assert_eq!(source, tds_err),
other => panic!("expected TopologyValidation, got {other:?}"),
}
}
#[test]
fn test_ridge_link_repair_validation_error_routes_manifold_errors_to_triangulation_layer() {
let ridge_key = 0x1234_u64;
let error = ridge_link_repair_validation_error(ManifoldError::BoundaryRidgeMultiplicity {
ridge_key,
boundary_facet_count: 3,
});
match error {
InsertionError::TopologyValidationFailed { message, source } => {
assert_eq!(message, RIDGE_LINK_REPAIR_VALIDATION_MESSAGE);
assert!(matches!(
source,
TriangulationValidationError::BoundaryRidgeMultiplicity {
ridge_key: observed_ridge_key,
boundary_facet_count: 3
} if observed_ridge_key == ridge_key
));
}
other => panic!("expected TopologyValidationFailed, got {other:?}"),
}
}
macro_rules! gen_local_repair_flip_budget_tests {
($dim:literal, $floor:ident, $factor:ident) => {
pastey::paste! {
#[test]
fn [<test_local_repair_flip_budget_uses_dimension_specific_floor_and_factor_ $dim d>]() {
assert_eq!(local_repair_flip_budget::<$dim>(0), $floor);
let seed_count = 10;
let raw = seed_count * ($dim + 1) * $factor;
assert_eq!(local_repair_flip_budget::<$dim>(seed_count), raw.max($floor));
}
}
};
}
gen_local_repair_flip_budget_tests!(
2,
LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_LT_4,
LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_LT_4
);
gen_local_repair_flip_budget_tests!(
3,
LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_LT_4,
LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_LT_4
);
gen_local_repair_flip_budget_tests!(
4,
LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_GE_4,
LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_GE_4
);
gen_local_repair_flip_budget_tests!(
5,
LOCAL_REPAIR_FLIP_BUDGET_FLOOR_D_GE_4,
LOCAL_REPAIR_FLIP_BUDGET_FACTOR_D_GE_4
);
#[test]
fn test_local_repair_seed_backlog_threshold_uses_dimension_regimes() {
assert_eq!(
local_repair_seed_backlog_threshold::<3>(),
4 * LOCAL_REPAIR_SEED_BACKLOG_FACTOR_D_LT_4
);
assert_eq!(
local_repair_seed_backlog_threshold::<4>(),
5 * LOCAL_REPAIR_SEED_BACKLOG_FACTOR_D_GE_4
);
}
#[test]
fn test_batch_local_repair_trigger_prefers_cadence_over_backlog() {
let policy = DelaunayRepairPolicy::EveryN(NonZeroUsize::new(4).unwrap());
let threshold = local_repair_seed_backlog_threshold::<3>();
assert_eq!(
batch_local_repair_trigger::<3>(policy, 4, TopologyGuarantee::PLManifold, threshold),
Some(BatchLocalRepairTrigger::Cadence)
);
}
#[test]
fn test_batch_local_repair_trigger_runs_every_insertion_below_backlog() {
assert_eq!(
batch_local_repair_trigger::<3>(
DelaunayRepairPolicy::EveryInsertion,
1,
TopologyGuarantee::PLManifold,
1,
),
Some(BatchLocalRepairTrigger::Cadence)
);
assert_eq!(
batch_local_repair_trigger::<3>(
DelaunayRepairPolicy::EveryInsertion,
0,
TopologyGuarantee::PLManifold,
1,
),
None
);
}
#[test]
fn test_batch_local_repair_trigger_repairs_early_on_seed_backlog() {
let policy = DelaunayRepairPolicy::EveryN(NonZeroUsize::new(128).unwrap());
let threshold = local_repair_seed_backlog_threshold::<3>();
assert_eq!(
batch_local_repair_trigger::<3>(policy, 7, TopologyGuarantee::PLManifold, threshold),
Some(BatchLocalRepairTrigger::SeedBacklog)
);
assert_eq!(
batch_local_repair_trigger::<3>(
policy,
7,
TopologyGuarantee::PLManifold,
threshold - 1
),
None
);
}
#[test]
fn test_batch_local_repair_trigger_respects_policy_and_topology() {
let threshold = local_repair_seed_backlog_threshold::<3>();
assert_eq!(
batch_local_repair_trigger::<3>(
DelaunayRepairPolicy::Never,
7,
TopologyGuarantee::PLManifold,
threshold
),
None
);
assert_eq!(
batch_local_repair_trigger::<3>(
DelaunayRepairPolicy::EveryN(NonZeroUsize::new(128).unwrap()),
7,
TopologyGuarantee::PLManifold,
0
),
None
);
assert_eq!(
batch_local_repair_trigger::<3>(
DelaunayRepairPolicy::EveryN(NonZeroUsize::new(128).unwrap()),
7,
TopologyGuarantee::Pseudomanifold,
threshold
),
Some(BatchLocalRepairTrigger::SeedBacklog)
);
}
#[test]
fn test_log_bulk_progress_if_due_updates_progress_state_only_when_due() {
let sample = BatchProgressSample {
processed: 5,
inserted: 4,
skipped: 1,
cell_count: 7,
perturbation_seed: 0xCAFE,
};
let mut disabled = None;
log_bulk_progress_if_due(sample, &mut disabled);
assert!(disabled.is_none());
let mut state = Some(BatchProgressState {
total_vertices: 10,
progress_every: 5,
started: Instant::now(),
last_progress: Instant::now(),
last_processed: 0,
});
log_bulk_progress_if_due(
BatchProgressSample {
processed: 0,
..sample
},
&mut state,
);
assert_eq!(state.as_ref().unwrap().last_processed, 0);
log_bulk_progress_if_due(
BatchProgressSample {
processed: 3,
..sample
},
&mut state,
);
assert_eq!(state.as_ref().unwrap().last_processed, 0);
log_bulk_progress_if_due(sample, &mut state);
assert_eq!(state.as_ref().unwrap().last_processed, 5);
log_bulk_progress_if_due(
BatchProgressSample {
processed: 10,
inserted: 8,
skipped: 2,
cell_count: 11,
perturbation_seed: 0xBEEF,
},
&mut state,
);
assert_eq!(state.as_ref().unwrap().last_processed, 10);
}
#[test]
fn test_collect_local_repair_seed_cells_merges_adjacent_extra_and_ignores_stale() {
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
vertex!([1.0, 1.0]),
vertex!([0.5, 0.5]),
];
let dt: DelaunayTriangulation<_, (), (), 2> =
DelaunayTriangulation::new(&vertices).unwrap();
let all_cells: Vec<CellKey> = dt.cells().map(|(cell_key, _)| cell_key).collect();
let (vertex_key, adjacent, extra_cell) = dt
.vertices()
.find_map(|(vertex_key, _)| {
let adjacent: Vec<CellKey> = dt.tri.adjacent_cells(vertex_key).collect();
all_cells
.iter()
.copied()
.find(|cell_key| !adjacent.contains(cell_key))
.map(|extra_cell| (vertex_key, adjacent, extra_cell))
})
.expect("fixture should contain a cell outside at least one vertex star");
let stale_cell = CellKey::from(KeyData::from_ffi(999_999));
let seeds = dt.collect_local_repair_seed_cells(
vertex_key,
&[adjacent[0], extra_cell, extra_cell, stale_cell],
);
assert_eq!(seeds.len(), adjacent.len() + 1);
assert_eq!(&seeds[..adjacent.len()], adjacent.as_slice());
assert_eq!(seeds[adjacent.len()], extra_cell);
assert!(!seeds.contains(&stale_cell));
}
#[test]
fn test_validate_ridge_links_after_full_reseed_repair_uses_mutation_frontier() {
init_tracing();
let (tds, incident_to_invalid_ridge, nonincident) = wedge_two_spheres_share_vertex_tds_2d();
let dt = DelaunayTriangulation::from_tds_with_topology_guarantee(
tds,
AdaptiveKernel::new(),
TopologyGuarantee::PLManifold,
);
let stats = DelaunayRepairStats {
flips_performed: 1,
..DelaunayRepairStats::default()
};
let local_run = DelaunayRepairRun {
stats: stats.clone(),
touched_cells: std::iter::once(nonincident).collect(),
used_full_reseed: true,
};
assert!(
dt.validate_ridge_links_after_repair(TopologyGuarantee::PLManifold, &local_run)
.is_ok()
);
let invalid_scope_run = DelaunayRepairRun {
stats,
touched_cells: std::iter::once(incident_to_invalid_ridge).collect(),
used_full_reseed: true,
};
assert!(
dt.validate_ridge_links_after_repair(
TopologyGuarantee::PLManifold,
&invalid_scope_run,
)
.is_err()
);
}
struct ForceHeuristicRebuildGuard {
prior: bool,
}
impl ForceHeuristicRebuildGuard {
fn enable() -> Self {
let prior = test_hooks::set_force_heuristic_rebuild(true);
Self { prior }
}
}
impl Drop for ForceHeuristicRebuildGuard {
fn drop(&mut self) {
test_hooks::restore_force_heuristic_rebuild(self.prior);
}
}
struct ForceRepairNonconvergentGuard {
prior: bool,
}
impl ForceRepairNonconvergentGuard {
fn enable() -> Self {
let prior = test_hooks::set_force_repair_nonconvergent(true);
Self { prior }
}
}
impl Drop for ForceRepairNonconvergentGuard {
fn drop(&mut self) {
test_hooks::restore_force_repair_nonconvergent(self.prior);
}
}
#[test]
fn test_construction_options_default_uses_batch_repair_cadence() {
init_tracing();
assert_eq!(
ConstructionOptions::default().initial_simplex_strategy(),
InitialSimplexStrategy::MaxVolume
);
assert_eq!(
ConstructionOptions::default().batch_repair_policy(),
DelaunayRepairPolicy::EveryInsertion
);
assert_eq!(
DelaunayRepairPolicy::default(),
DelaunayRepairPolicy::EveryInsertion
);
}
#[test]
fn test_construction_options_builder_roundtrip() {
init_tracing();
let opts = ConstructionOptions::default()
.with_insertion_order(InsertionOrderStrategy::Input)
.with_dedup_policy(DedupPolicy::Exact)
.with_batch_repair_policy(DelaunayRepairPolicy::EveryN(NonZeroUsize::new(4).unwrap()))
.with_retry_policy(RetryPolicy::Disabled);
assert_eq!(opts.insertion_order(), InsertionOrderStrategy::Input);
assert_eq!(opts.dedup_policy(), DedupPolicy::Exact);
assert_eq!(
opts.batch_repair_policy(),
DelaunayRepairPolicy::EveryN(NonZeroUsize::new(4).unwrap())
);
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!(sample.coords_available);
assert_eq!(sample.attempts, 1);
assert!(sample.error.contains("Duplicate coordinates"));
}
#[test]
fn test_vertex_coords_f64_converts_f64_vertex_coords() {
init_tracing();
let vertex: Vertex<f64, (), 3> = vertex!([1.25, -2.5, 3.75]);
assert_eq!(vertex_coords_f64(&vertex), Some(vec![1.25, -2.5, 3.75]));
}
#[test]
fn test_vertex_coords_f64_converts_f32_vertex_coords() {
init_tracing();
let vertex: Vertex<f32, (), 3> = vertex!([1.25f32, -2.5f32, 3.75f32]);
assert_eq!(vertex_coords_f64(&vertex), Some(vec![1.25, -2.5, 3.75]));
}
#[test]
fn test_vertex_coords_f64_rejects_non_finite_coords() {
init_tracing();
let nan_vertex: Vertex<f64, (), 3> = VertexBuilder::default()
.point(Point::new([1.0, f64::NAN, 3.0]))
.build()
.unwrap();
let infinite_vertex: Vertex<f64, (), 3> = VertexBuilder::default()
.point(Point::new([1.0, f64::INFINITY, 3.0]))
.build()
.unwrap();
assert_eq!(vertex_coords_f64(&nan_vertex), None);
assert_eq!(vertex_coords_f64(&infinite_vertex), None);
}
fn coord_sequence_2d(vertices: &[Vertex<f64, (), 2>]) -> Vec<[f64; 2]> {
vertices.iter().map(|v| *v.point().coords()).collect()
}
#[test]
fn order_vertices_input_preserves_order() {
init_tracing();
let vertices = vec![
vertex!([2.0, 0.0]),
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
];
let expected = coord_sequence_2d(&vertices);
let ordered = order_vertices_by_strategy(vertices, InsertionOrderStrategy::Input);
assert_eq!(coord_sequence_2d(&ordered), expected);
}
#[test]
fn dedup_exact_sorted_without_grid() {
init_tracing();
let vertices = vec![
vertex!([1.0, 0.0]),
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 1.0]),
];
let unique = dedup_vertices_exact_sorted(vertices);
assert_eq!(
coord_sequence_2d(&unique),
vec![[0.0, 0.0], [0.0, 1.0], [1.0, 0.0]]
);
}
#[test]
fn dedup_exact_grid_fallback() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([1.0, 0.0]),
vertex!([0.0, 0.0]),
];
let mut grid = HashGridIndex::<f64, 2, usize>::new(1.0e-10);
let unique = dedup_vertices_exact_hash_grid(vertices, &mut grid);
assert_eq!(coord_sequence_2d(&unique), vec![[0.0, 0.0], [1.0, 0.0]]);
let vertices_6d = vec![
vertex!([1.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
];
let mut unusable_grid = HashGridIndex::<f64, 6, usize>::new(1.0e-10);
let fallback_unique = dedup_vertices_exact_hash_grid(vertices_6d, &mut unusable_grid);
assert_eq!(fallback_unique.len(), 1);
}
#[test]
fn epsilon_dedup_quantized_paths() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([0.09, 0.0]),
vertex!([0.25, 0.0]),
];
let unique = dedup_vertices_epsilon_quantized(vertices, 0.1);
assert_eq!(coord_sequence_2d(&unique), vec![[0.0, 0.0], [0.25, 0.0]]);
let zero_epsilon_vertices = vec![vertex!([0.0, 0.0]), vertex!([0.0, 0.0])];
let zero_epsilon_unique = dedup_vertices_epsilon_quantized(zero_epsilon_vertices, 0.0);
assert_eq!(zero_epsilon_unique.len(), 2);
let nonfinite_vertices = vec![
vertex!([0.0, 0.0]),
Vertex::new_with_uuid(Point::new([f64::NAN, 0.0]), Uuid::new_v4(), None),
];
let nonfinite_unique = dedup_vertices_epsilon_quantized(nonfinite_vertices, 0.1);
assert_eq!(nonfinite_unique.len(), 2);
let vertices_6d = vec![
vertex!([0.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
vertex!([0.01, 0.0, 0.0, 0.0, 0.0, 0.0]),
];
let fallback_unique = dedup_vertices_epsilon_quantized(vertices_6d, 0.1);
assert_eq!(fallback_unique.len(), 1);
}
#[test]
fn dedup_epsilon_grid_fallback() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0]),
vertex!([0.05, 0.0]),
vertex!([0.25, 0.0]),
];
let mut grid = HashGridIndex::<f64, 2, usize>::new(0.1);
let unique = dedup_vertices_epsilon_hash_grid(vertices, 0.1, &mut grid);
assert_eq!(coord_sequence_2d(&unique), vec![[0.0, 0.0], [0.25, 0.0]]);
let fallback_vertices = vec![vertex!([0.0, 0.0]), vertex!([0.05, 0.0])];
let mut unusable_grid = HashGridIndex::<f64, 2, usize>::new(0.0);
let fallback_unique =
dedup_vertices_epsilon_hash_grid(fallback_vertices, 0.1, &mut unusable_grid);
assert_eq!(fallback_unique.len(), 1);
}
#[test]
fn preprocess_falls_back_when_grid_unusable() {
init_tracing();
let exact_vertices = vec![
vertex!([1.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
vertex!([0.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
];
let exact = TestDelaunay::<6>::preprocess_vertices_for_construction(
&exact_vertices,
DedupPolicy::Exact,
InsertionOrderStrategy::Input,
InitialSimplexStrategy::First,
)
.unwrap();
assert_eq!(exact.primary_slice(&exact_vertices).len(), 2);
assert!(exact.grid_cell_size().is_none());
let epsilon_vertices = vec![
vertex!([0.0, 0.0, 0.0, 0.0, 0.0, 0.0]),
vertex!([0.01, 0.0, 0.0, 0.0, 0.0, 0.0]),
vertex!([0.5, 0.0, 0.0, 0.0, 0.0, 0.0]),
];
let epsilon = TestDelaunay::<6>::preprocess_vertices_for_construction(
&epsilon_vertices,
DedupPolicy::Epsilon { tolerance: 0.1 },
InsertionOrderStrategy::Input,
InitialSimplexStrategy::First,
)
.unwrap();
assert_eq!(epsilon.primary_slice(&epsilon_vertices).len(), 2);
assert!(epsilon.grid_cell_size().is_none());
}
#[test]
fn preprocess_zero_epsilon_keeps_base() {
init_tracing();
let vertices = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
];
let preprocess = TestDelaunay::<3>::preprocess_vertices_for_construction(
&vertices,
DedupPolicy::Epsilon { tolerance: 0.0 },
InsertionOrderStrategy::Input,
InitialSimplexStrategy::Balanced,
)
.unwrap();
assert!(preprocess.grid_cell_size().is_some());
assert_eq!(preprocess.primary_slice(&vertices).len(), vertices.len());
assert!(preprocess.fallback_slice().is_none());
}
#[test]
fn quantize_and_neighbor_edges() {
init_tracing();
assert_eq!(quantize_coords(&[0.25, -0.25], 10.0), Some([2, -3]));
assert_eq!(quantize_coords(&[f64::NAN, 0.0], 10.0), None);
assert_eq!(quantize_coords(&[1.0e308, 0.0], 1.0e308), None);
let mut visited = Vec::new();
let mut current = [0_i64, 0_i64];
let completed = visit_quantized_neighbors(0, &[4, 7], &mut current, &mut |neighbor| {
visited.push(neighbor);
visited.len() < 4
});
assert!(!completed);
assert_eq!(visited.len(), 4);
}
#[test]
fn hilbert_fallback_for_nonfinite_coords() {
init_tracing();
let vertices = vec![
vertex!([1.0, 0.0]),
Vertex::new_with_uuid(Point::new([f64::NAN, 0.0]), Uuid::new_v4(), None),
vertex!([0.0, 0.0]),
];
let ordered = order_vertices_hilbert(vertices, true);
assert_eq!(ordered.len(), 3);
assert!(
ordered.iter().any(|v| v.point().coords()[0].is_nan()),
"fallback ordering should preserve the non-finite vertex"
);
assert!(
ordered
.iter()
.any(|v| coords_equal_exact(v.point().coords(), &[0.0, 0.0]))
);
assert!(
ordered
.iter()
.any(|v| coords_equal_exact(v.point().coords(), &[1.0, 0.0]))
);
}
#[test]
fn hilbert_fallback_for_unsupported_dim() {
init_tracing();
let vertices = vec![vertex!([1.0; 17]), vertex!([0.0; 17])];
let ordered = order_vertices_hilbert(vertices, true);
assert!(coords_equal_exact(ordered[0].point().coords(), &[0.0; 17]));
assert!(coords_equal_exact(ordered[1].point().coords(), &[1.0; 17]));
}
#[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: 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, 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: InsertionResult::SkippedDuplicate,
};
let skipped_degeneracy = InsertionStatistics {
attempts: 2,
cells_removed_during_repair: 5,
result: 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,
],
coords_available: true,
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_construction_statistics_records_slowest_insertion_samples() {
init_tracing();
let mut summary = ConstructionStatistics::default();
for index in 0..10 {
let sample_index_u32 = u32::try_from(index).unwrap();
summary.record_slow_insertion_sample(ConstructionSlowInsertionSample {
index,
uuid: Uuid::from_u128(
<u128 as std::convert::From<u32>>::from(sample_index_u32) + 1,
),
attempts: 1,
result: InsertionResult::Inserted,
elapsed_nanos: <u64 as std::convert::From<u32>>::from(sample_index_u32) * 1_000,
cells_after: index,
locate_calls: 1,
locate_walk_steps_total: index,
conflict_region_calls: 1,
conflict_region_cells_total: index,
cavity_insertion_calls: 1,
global_conflict_scans: 0,
hull_extension_calls: 0,
topology_validation_calls: 1,
});
}
assert_eq!(summary.slow_insertions.len(), 8);
assert_eq!(summary.slow_insertions.first().map(|s| s.index), Some(9));
assert_eq!(summary.slow_insertions.last().map(|s| s.index), Some(2));
assert!(
summary
.slow_insertions
.windows(2)
.all(|pair| pair[0].elapsed_nanos >= pair[1].elapsed_nanos)
);
}
#[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(Point::new([f64::NAN, 0.0, 0.0]), Uuid::new_v4(), None),
];
let result = select_balanced_simplex_indices(&vertices);
assert!(result.is_none());
}
macro_rules! max_volume_axis_simplex_test {
($test_name:ident, $dimension:literal, [$($coords:expr),+ $(,)?], [$($expected_idx:expr),+ $(,)?]) => {
#[test]
fn $test_name() {
init_tracing();
let vertices: Vec<Vertex<f64, (), $dimension>> = vec![$(vertex!($coords)),+];
let result = select_max_volume_simplex_indices(&vertices)
.expect("max-volume simplex selection failed");
let expected_indices = [$($expected_idx),+];
assert_eq!(result.len(), expected_indices.len());
for expected_idx in expected_indices {
assert!(
result.contains(&expected_idx),
"expected selected simplex {result:?} to contain vertex index {expected_idx}"
);
}
}
};
}
max_volume_axis_simplex_test!(
test_select_max_volume_simplex_indices_prefers_largest_triangle_2d,
2,
[
[0.0, 0.0],
[1.0, 0.0],
[0.0, 1.0],
[10.0, 0.0],
[0.0, 10.0],
[1.0, 1.0],
],
[0, 3, 4]
);
max_volume_axis_simplex_test!(
test_select_max_volume_simplex_indices_prefers_largest_tetrahedron,
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],
[10.0, 0.0, 0.0],
[0.0, 10.0, 0.0],
[0.0, 0.0, 10.0],
],
[0, 4, 5, 6]
);
max_volume_axis_simplex_test!(
test_select_max_volume_simplex_indices_prefers_largest_simplex_4d,
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],
[10.0, 0.0, 0.0, 0.0],
[0.0, 10.0, 0.0, 0.0],
[0.0, 0.0, 10.0, 0.0],
[0.0, 0.0, 0.0, 10.0],
],
[0, 5, 6, 7, 8]
);
max_volume_axis_simplex_test!(
test_select_max_volume_simplex_indices_prefers_largest_simplex_5d,
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],
[10.0, 0.0, 0.0, 0.0, 0.0],
[0.0, 10.0, 0.0, 0.0, 0.0],
[0.0, 0.0, 10.0, 0.0, 0.0],
[0.0, 0.0, 0.0, 10.0, 0.0],
[0.0, 0.0, 0.0, 0.0, 10.0],
],
[0, 6, 7, 8, 9, 10]
);
#[test]
fn test_select_max_volume_simplex_indices_rejects_degenerate_pool() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 3>> = vec![
vertex!([0.0, 0.0, 0.0]),
vertex!([1.0, 0.0, 0.0]),
vertex!([2.0, 0.0, 0.0]),
vertex!([3.0, 0.0, 0.0]),
];
let result = select_max_volume_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_for_construction_max_volume_sets_largest_simplex_first() {
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!([10.0, 0.0, 0.0]),
vertex!([0.0, 10.0, 0.0]),
vertex!([0.0, 0.0, 10.0]),
];
let preprocess = DelaunayTriangulation::<
AdaptiveKernel<f64>,
(),
(),
3,
>::preprocess_vertices_for_construction(
&vertices,
DedupPolicy::Off,
InsertionOrderStrategy::Input,
InitialSimplexStrategy::MaxVolume,
)
.expect("preprocess failed");
let primary = preprocess.primary_slice(&vertices);
assert!(primary.len() >= 4);
let first_simplex = &primary[..4];
let first_simplex_contains = |expected_coords: [f64; 3]| {
first_simplex.iter().any(|vertex| {
vertex
.point()
.coords()
.iter()
.zip(expected_coords)
.all(|(actual, expected)| (*actual - expected).abs() <= f64::EPSILON)
})
};
assert!(preprocess.fallback_slice().is_some());
assert!(first_simplex_contains([0.0, 0.0, 0.0]));
assert!(first_simplex_contains([10.0, 0.0, 0.0]));
assert!(first_simplex_contains([0.0, 10.0, 0.0]));
assert!(first_simplex_contains([0.0, 0.0, 10.0]));
}
#[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(
DelaunayConstructionFailure::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)
}
fn simplex_with_interior<const D: usize>() -> Vec<Vertex<f64, (), D>> {
let mut verts = simplex_vertices::<D>();
let dimension = safe_usize_to_scalar::<f64>(D).expect("test dimensions fit in f64");
let interior = [0.1_f64 / dimension; 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::try_from_tds(dt_new.tds().clone(), FastKernel::new()).unwrap();
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_finalize_bulk_construction_validates_pseudomanifold_topology() {
init_tracing();
let vertices: Vec<Vertex<f64, (), 2>> = vec![
vertex!([0.0, 0.0]),
vertex!([2.0, 0.0]),
vertex!([0.0, 2.0]),
vertex!([2.0, 1.0]),
];
let mut dt = DelaunayTriangulation::new_with_topology_guarantee(
&vertices,
TopologyGuarantee::Pseudomanifold,
)
.unwrap();
assert!(
dt.tri.tds.number_of_cells() > 1,
"regression setup needs an interior facet"
);
dt.tri.tds.clear_all_neighbors();
let err = dt
.finalize_bulk_construction(
ValidationPolicy::OnSuspicion,
DelaunayRepairPolicy::Never,
false,
DelaunayRepairPolicy::Never,
&[],
&[],
None,
)
.unwrap_err();
assert!(matches!(
err,
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::FinalTopologyValidation { .. }
)
));
}
#[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, 0));
assert!(!dt.should_run_delaunay_repair_for(topology, 1));
assert!(dt.should_run_delaunay_repair_for(topology, 2));
}
#[test]
fn test_delaunay_repair_policy_zero_insertions_never_repairs() {
assert!(!DelaunayRepairPolicy::EveryInsertion.should_repair(0));
assert!(!DelaunayRepairPolicy::EveryN(NonZeroUsize::new(2).unwrap()).should_repair(0));
}
#[test]
fn test_non_insertion_mutation_repair_gate_ignores_insertion_cadence() {
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();
let topology = dt.topology_guarantee();
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::EveryN(NonZeroUsize::new(2).unwrap()));
assert!(dt.should_run_delaunay_repair_after_mutation(topology));
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::Never);
assert!(!dt.should_run_delaunay_repair_after_mutation(topology));
}
#[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.vertex(remapped).is_some());
assert!(dt.validate().is_ok());
let _ = vertex_key;
}
#[test]
fn test_heuristic_rebuild_preserves_global_topology() {
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 global_topology = GlobalTopology::Toroidal {
domain: [1.0, 1.0],
mode: ToroidalConstructionMode::PeriodicImagePoint,
};
dt.set_global_topology(global_topology);
let _guard = ForceHeuristicRebuildGuard::enable();
let outcome = dt
.repair_delaunay_with_flips_advanced(DelaunayRepairHeuristicConfig::default())
.unwrap();
assert!(
outcome.used_heuristic(),
"Expected forced heuristic rebuild to be used"
);
assert_eq!(dt.global_topology(), global_topology);
assert_eq!(dt.topology_guarantee(), TopologyGuarantee::PLManifold);
}
#[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_key = dt
.vertices()
.find(|(_, v)| v.uuid() == inserted_uuid)
.map(|(k, _)| k)
.expect("Inserted vertex not found");
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::Never);
let removed_cells = dt.remove_vertex(vertex_key).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 remove_vertex_invalidates_locate_hint_and_prunes_spatial_index() {
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();
let vertex_key = dt.insert(vertex!([0.25, 0.25])).unwrap();
let hint_cell = dt.cells().next().map(|(key, _)| key);
dt.insertion_state.last_inserted_cell = hint_cell;
let mut spatial_index = HashGridIndex::<f64, 2>::new(1.0);
for (vertex_key, vertex) in dt.vertices() {
spatial_index.insert_vertex(vertex_key, vertex.point().coords());
}
dt.spatial_index = Some(spatial_index);
assert!(dt.insertion_state.last_inserted_cell.is_some());
assert!(dt.spatial_index.is_some());
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::Never);
let removed_cells = dt.remove_vertex(vertex_key).unwrap();
assert!(removed_cells > 0);
assert!(dt.insertion_state.last_inserted_cell.is_none());
let spatial_index = dt
.spatial_index
.as_ref()
.expect("successful vertex removal should retain the spatial index");
let mut found_removed_key = false;
assert!(
spatial_index.for_each_candidate_vertex_key(&[0.25, 0.25], |candidate| {
found_removed_key |= candidate == vertex_key;
true
})
);
assert!(!found_removed_key);
assert!(dt.as_triangulation().validate().is_ok());
}
#[test]
fn flip_k1_insert_invalidates_caches() {
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 cell_key = dt.cells().next().unwrap().0;
dt.insertion_state.last_inserted_cell = Some(cell_key);
let mut spatial_index = HashGridIndex::<f64, 3>::new(1.0);
for (vertex_key, vertex) in dt.vertices() {
spatial_index.insert_vertex(vertex_key, vertex.point().coords());
}
dt.spatial_index = Some(spatial_index);
dt.flip_k1_insert(cell_key, vertex!([0.2, 0.2, 0.2]))
.unwrap();
assert!(dt.insertion_state.last_inserted_cell.is_none());
assert!(dt.spatial_index.is_none());
assert!(dt.as_triangulation().validate().is_ok());
}
fn non_delaunay_quad_tds() -> Tds<f64, (), (), 2> {
let mut tds: Tds<f64, (), (), 2> = Tds::empty();
let v0 = tds.insert_vertex_with_mapping(vertex!([0.0, 0.0])).unwrap();
let v1 = tds.insert_vertex_with_mapping(vertex!([4.0, 0.0])).unwrap();
let v2 = tds.insert_vertex_with_mapping(vertex!([4.0, 2.0])).unwrap();
let v3 = tds.insert_vertex_with_mapping(vertex!([1.0, 2.0])).unwrap();
tds.insert_cell_with_mapping(Cell::new(vec![v0, v1, v2], None).unwrap())
.unwrap();
tds.insert_cell_with_mapping(Cell::new(vec![v0, v2, v3], None).unwrap())
.unwrap();
tds.construction_state = TriangulationConstructionState::Constructed;
tds.assign_neighbors().unwrap();
tds.assign_incident_cells().unwrap();
tds
}
#[test]
fn as_triangulation_mut_invalidates_caches() {
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();
let cell_key = dt.cells().next().unwrap().0;
dt.insertion_state.last_inserted_cell = Some(cell_key);
let mut spatial_index = HashGridIndex::<f64, 2>::new(1.0);
for (vertex_key, vertex) in dt.vertices() {
spatial_index.insert_vertex(vertex_key, vertex.point().coords());
}
dt.spatial_index = Some(spatial_index);
assert!(dt.insertion_state.last_inserted_cell.is_some());
assert!(dt.spatial_index.is_some());
#[allow(deprecated)]
{
assert!(dt.as_triangulation_mut().validate().is_ok());
}
assert!(dt.insertion_state.last_inserted_cell.is_none());
assert!(dt.spatial_index.is_none());
}
#[test]
fn try_from_tds_rejects_non_delaunay_connectivity() {
init_tracing();
let tds = non_delaunay_quad_tds();
let err = DelaunayTriangulation::try_from_tds(tds, AdaptiveKernel::new())
.expect_err("checked TDS reconstruction must reject non-Delaunay connectivity");
assert!(
matches!(
err,
DelaunayTriangulationValidationError::VerificationFailed { .. }
),
"expected Level 4 validation failure, got {err:?}"
);
}
#[test]
fn robust_deserialize_rejects_non_delaunay_connectivity() {
init_tracing();
let json = serde_json::to_string(&non_delaunay_quad_tds()).unwrap();
let err =
serde_json::from_str::<DelaunayTriangulation<RobustKernel<f64>, (), (), 2>>(&json)
.expect_err("serde reconstruction must reject non-Delaunay connectivity");
let message = err.to_string();
assert!(
message.contains("Delaunay verification failed"),
"serde error should preserve the Level 4 validation failure: {message}"
);
}
fn interior_vertex_for_k1_insert<const D: usize>() -> Vertex<f64, (), D> {
let denominator = safe_usize_to_scalar::<f64>(D + 2)
.expect("D + 2 should convert exactly for rollback test dimensions");
let coord = 1.0 / denominator;
vertex!([coord; D])
}
fn rollback_probe_vertex<const D: usize>(point_index: usize) -> Vertex<f64, (), D> {
let dimension =
safe_usize_to_scalar::<f64>(D).expect("test dimensions should convert exactly");
let point_index_scalar =
safe_usize_to_scalar::<f64>(point_index).expect("point index should convert exactly");
let mut coords = [0.2 / dimension; D];
let axis = point_index % D;
coords[axis] += point_index_scalar.mul_add(0.005, 0.02);
vertex!(coords)
}
fn incident_cell_count<const D: usize>(
dt: &DelaunayTriangulation<AdaptiveKernel<f64>, (), (), D>,
vertex_key: VertexKey,
) -> usize {
dt.cells()
.filter(|(_, cell)| cell.vertices().contains(&vertex_key))
.count()
}
fn assert_forced_remove_vertex_rolls_back<const D: usize>(
dt: &mut DelaunayTriangulation<AdaptiveKernel<f64>, (), (), D>,
vertex_key: VertexKey,
inserted_uuid: Uuid,
) {
let vertex_count_before = dt.number_of_vertices();
let cell_count_before = dt.number_of_cells();
let hint_cell_before = dt.cells().next().map(|(key, _)| key);
dt.insertion_state.last_inserted_cell = hint_cell_before;
let mut spatial_index = HashGridIndex::<f64, D>::new(1.0);
for (vertex_key, vertex) in dt.vertices() {
spatial_index.insert_vertex(vertex_key, vertex.point().coords());
}
dt.spatial_index = Some(spatial_index);
let last_inserted_cell_before = dt.insertion_state.last_inserted_cell;
let spatial_index_before = dt
.spatial_index
.as_ref()
.map(HashGridIndex::<f64, D>::debug_snapshot);
let _guard = ForceRepairNonconvergentGuard::enable();
let result = dt.remove_vertex(vertex_key);
let err = result.expect_err("forced repair failure should make removal fail");
match err {
InvariantError::Delaunay(
DelaunayTriangulationValidationError::RepairOperationFailed {
operation: DelaunayRepairOperation::VertexRemoval,
source,
},
) if matches!(
source.as_ref(),
DelaunayRepairError::NonConvergent { max_flips: 0, .. }
) =>
{
}
InvariantError::Tds(TdsError::FacetSharingViolation { .. }) => {
}
other => panic!(
"expected vertex-removal RepairOperationFailed from forced repair path, got {other:?}"
),
}
assert_eq!(dt.number_of_vertices(), vertex_count_before);
assert_eq!(dt.number_of_cells(), cell_count_before);
assert_eq!(
dt.insertion_state.last_inserted_cell, last_inserted_cell_before,
"remove_vertex rollback should restore last_inserted_cell"
);
assert_eq!(
dt.spatial_index
.as_ref()
.map(HashGridIndex::<f64, D>::debug_snapshot),
spatial_index_before,
"remove_vertex rollback should restore spatial_index"
);
assert!(dt.vertices().any(|(_, v)| v.uuid() == inserted_uuid));
assert!(dt.as_triangulation().validate().is_ok());
}
fn assert_remove_vertex_rollback<const D: usize>() {
init_tracing();
let vertices = simplex_vertices::<D>();
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), D> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.set_topology_guarantee(TopologyGuarantee::PLManifold);
let cell_key = dt.cells().next().unwrap().0;
let inserted_vertex = interior_vertex_for_k1_insert::<D>();
let inserted_uuid = inserted_vertex.uuid();
dt.flip_k1_insert(cell_key, inserted_vertex).unwrap();
let vertex_key = dt
.vertices()
.find(|(_, v)| v.uuid() == inserted_uuid)
.map(|(k, _)| k)
.expect("Inserted vertex not found");
assert_forced_remove_vertex_rolls_back(&mut dt, vertex_key, inserted_uuid);
}
fn assert_remove_vertex_fallback_rollback<const D: usize>() {
init_tracing();
let vertices = simplex_vertices::<D>();
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), D> =
DelaunayTriangulation::new(&vertices).unwrap();
dt.set_topology_guarantee(TopologyGuarantee::PLManifold);
let mut inserted_vertices = Vec::new();
for point_index in 0..(D + 3) {
let inserted_vertex = rollback_probe_vertex::<D>(point_index);
let inserted_uuid = inserted_vertex.uuid();
let vertex_key = dt
.insert(inserted_vertex)
.expect("rollback fallback fixture insertion should succeed");
inserted_vertices.push((vertex_key, inserted_uuid));
}
let (vertex_key, inserted_uuid, incident_cells) = inserted_vertices
.iter()
.find_map(|&(vertex_key, inserted_uuid)| {
let incident_cells = incident_cell_count(&dt, vertex_key);
(incident_cells != D + 1).then_some((vertex_key, inserted_uuid, incident_cells))
})
.expect("expected at least one inserted vertex with a non-simplex star");
assert_ne!(
incident_cells,
D + 1,
"fallback rollback fixture must avoid the inverse-k=1 simplex-star path"
);
assert_forced_remove_vertex_rolls_back(&mut dt, vertex_key, inserted_uuid);
}
macro_rules! gen_remove_vertex_rollback_tests {
($dim:literal) => {
pastey::paste! {
#[test]
fn [<remove_vertex_rollback_ $dim d>]() {
assert_remove_vertex_rollback::<$dim>();
}
#[test]
fn [<remove_vertex_fallback_rollback_ $dim d>]() {
assert_remove_vertex_fallback_rollback::<$dim>();
}
}
};
}
gen_remove_vertex_rollback_tests!(2);
gen_remove_vertex_rollback_tests!(3);
gen_remove_vertex_rollback_tests!(4);
gen_remove_vertex_rollback_tests!(5);
#[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]));
let inserted_key = result
.as_ref()
.copied()
.expect("Insertion should succeed via robust fallback");
assert!(
result.is_ok(),
"Insertion should succeed via robust fallback: {result:?}"
);
let spatial_index = dt
.spatial_index
.as_ref()
.expect("topology-only repair should preserve the duplicate-detection index");
let mut found_inserted_key = false;
assert!(
spatial_index.for_each_candidate_vertex_key(&[0.5, 0.5], |candidate| {
found_inserted_key |= candidate == inserted_key;
true
})
);
assert!(found_inserted_key);
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 kernel = AdaptiveKernel::<f64>::new();
let robust_kernel = RobustKernel::<f64>::new();
let tds = non_delaunay_quad_tds();
assert!(verify_delaunay_via_flip_predicates(&tds, &kernel).is_err());
assert!(verify_delaunay_via_flip_predicates(&tds, &robust_kernel).is_err());
let mut dt: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::from_tds_with_topology_guarantee(
tds,
kernel,
TopologyGuarantee::PLManifold,
);
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 tds2 = non_delaunay_quad_tds();
let mut dt2: DelaunayTriangulation<AdaptiveKernel<f64>, (), (), 2> =
DelaunayTriangulation::from_tds_with_topology_guarantee(
tds2,
AdaptiveKernel::new(),
TopologyGuarantee::PLManifold,
);
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::try_from_tds(tds, FastKernel::new()).unwrap();
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(
DelaunayConstructionFailure::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(
DelaunayConstructionFailure::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.vertex(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();
dt.set_delaunay_repair_policy(DelaunayRepairPolicy::Never);
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(
DelaunayConstructionFailure::Tds {
reason: TdsConstructionFailure::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.vertex_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::try_from_tds(tds, AdaptiveKernel::new()).unwrap();
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: HashSet<_> = dt.edges().collect();
let edges_tri: 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: HashSet<_> = dt.edges_with_index(&index).collect();
let edges_tri_index: 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: HashSet<_> = dt.incident_edges(v0).collect();
let incident_tri: HashSet<_> = tri.incident_edges(v0).collect();
assert_eq!(incident_dt, incident_tri);
assert_eq!(incident_dt.len(), 3);
let incident_dt_index: HashSet<_> = dt.incident_edges_with_index(&index, v0).collect();
let incident_tri_index: 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_batch_4d_forced_nonconvergent_local_repair_canonicalizes_without_stats() {
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]),
vertex!([0.2, 0.2, 0.2, 0.2]),
vertex!([0.35, 0.25, 0.15, 0.3]),
];
let _guard = ForceRepairNonconvergentGuard::enable();
let kernel = RobustKernel::<f64>::new();
let dt =
DelaunayTriangulation::<RobustKernel<f64>, (), (), 4>::with_kernel(&kernel, &vertices)
.expect(
"D>=4 construction should continue after forced local repair non-convergence",
);
assert_eq!(dt.number_of_vertices(), vertices.len());
assert!(dt.validate().is_ok());
}
#[test]
fn test_batch_4d_forced_nonconvergent_local_repair_canonicalizes_with_stats() {
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]),
vertex!([0.2, 0.2, 0.2, 0.2]),
vertex!([0.35, 0.25, 0.15, 0.3]),
];
let _guard = ForceRepairNonconvergentGuard::enable();
let kernel = RobustKernel::<f64>::new();
let (dt, stats) =
DelaunayTriangulation::<RobustKernel<f64>, (), (), 4>::with_options_and_statistics(
&kernel,
&vertices,
TopologyGuarantee::DEFAULT,
ConstructionOptions::default(),
)
.expect(
"D>=4 stats construction should continue after forced local repair non-convergence",
);
assert_eq!(dt.number_of_vertices(), vertices.len());
assert_eq!(stats.inserted, vertices.len());
assert!(dt.validate().is_ok());
}
#[test]
fn test_batch_4d_every_n_repair_cadence_runs_with_pending_seeds() {
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]),
vertex!([0.2, 0.2, 0.2, 0.2]),
vertex!([0.35, 0.25, 0.15, 0.3]),
];
test_hooks::reset_batch_local_repair_calls();
let _guard = ForceRepairNonconvergentGuard::enable();
let kernel = RobustKernel::<f64>::new();
let options = ConstructionOptions::default()
.with_batch_repair_policy(DelaunayRepairPolicy::EveryN(NonZeroUsize::new(2).unwrap()));
let (dt, stats) =
DelaunayTriangulation::<RobustKernel<f64>, (), (), 4>::with_options_and_statistics(
&kernel,
&vertices,
TopologyGuarantee::DEFAULT,
options,
)
.expect("EveryN batch repair should soft-fail forced local non-convergence and finish");
assert_eq!(dt.number_of_vertices(), vertices.len());
assert_eq!(stats.inserted, vertices.len());
assert_eq!(
test_hooks::batch_local_repair_calls(),
1,
"EveryN(2) should run one cadenced repair before finalize_bulk_construction"
);
assert!(dt.validate().is_ok());
}
#[test]
fn test_repair_soft_fail_classification() {
let nonconvergent = test_hooks::synthetic_nonconvergent_error();
assert!(TestDelaunay::<4>::can_soft_fail(&nonconvergent));
let postcondition = DelaunayRepairError::PostconditionFailed {
message: "unresolved facet".to_string(),
};
assert!(TestDelaunay::<4>::can_soft_fail(&postcondition));
let flip_error =
DelaunayRepairError::Flip(FlipError::UnsupportedDimension { dimension: 1 });
assert!(!TestDelaunay::<4>::can_soft_fail(&flip_error));
let topology_error = DelaunayRepairError::InvalidTopology {
required: TopologyGuarantee::PLManifold,
found: TopologyGuarantee::Pseudomanifold,
message: "local repair requires manifold topology",
};
assert!(!TestDelaunay::<4>::can_soft_fail(&topology_error));
let verification_error = DelaunayRepairError::VerificationFailed {
context: DelaunayRepairVerificationContext::LocalK3PostconditionVerification,
source: Box::new(FlipError::InvalidFlipContext {
reason: FlipContextError::MissingRemovedCellFrame,
}),
};
assert!(!TestDelaunay::<4>::can_soft_fail(&verification_error));
let canonicalization_error = DelaunayRepairError::OrientationCanonicalizationFailed {
message: "after flip repair: broken orientation".to_string(),
};
assert!(!TestDelaunay::<4>::can_soft_fail(&canonicalization_error));
let mapped_hard = TestDelaunay::<4>::map_hard_repair_error(23, flip_error);
assert!(
matches!(
mapped_hard,
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::DelaunayRepair {
phase: DelaunayConstructionRepairPhase::BatchLocal { index: 23 },
ref source,
}
) if matches!(**source, DelaunayRepairError::Flip(FlipError::UnsupportedDimension { dimension: 1 }))
),
"deterministic hard D>=4 repair failures should stop shuffled retries: {mapped_hard:?}"
);
let geometric_error = DelaunayRepairError::Flip(FlipError::DegenerateCell);
let mapped_geometric = TestDelaunay::<4>::map_hard_repair_error(24, geometric_error);
assert!(
matches!(
mapped_geometric,
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::GeometricDegeneracy { ref message }
) if message.contains("per-insertion Delaunay repair failed at index 24")
&& message.contains("degenerate cell")
),
"geometric hard D>=4 repair failures should remain retryable degeneracies: {mapped_geometric:?}"
);
let mapped_verification = TestDelaunay::<4>::map_hard_repair_error(25, verification_error);
assert!(
matches!(
mapped_verification,
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::DelaunayRepair {
phase: DelaunayConstructionRepairPhase::BatchLocal { index: 25 },
ref source,
}
) if matches!(**source, DelaunayRepairError::VerificationFailed { .. })
),
"verification context failures should stop shuffled retries: {mapped_verification:?}"
);
let predicate_verification = DelaunayRepairError::VerificationFailed {
context: DelaunayRepairVerificationContext::StrictValidation,
source: Box::new(FlipError::PredicateFailure {
reason: FlipPredicateError::CoordinateConversion {
operation: FlipPredicateOperation::K2CellAInSphere,
source: CoordinateConversionError::ConversionFailed {
coordinate_index: 0,
coordinate_value: "in_sphere failed".to_string(),
from_type: "f64",
to_type: "f64",
},
},
}),
};
let mapped_predicate = TestDelaunay::<4>::map_hard_repair_error(26, predicate_verification);
assert!(
matches!(
mapped_predicate,
DelaunayTriangulationConstructionError::Triangulation(
DelaunayConstructionFailure::GeometricDegeneracy { ref message }
) if message.contains("per-insertion Delaunay repair failed at index 26")
&& message.contains("in_sphere failed")
),
"verification predicate failures should remain geometric: {mapped_predicate:?}"
);
}
#[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: 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_topology_validation_failed_is_internal() {
let error = InsertionError::TopologyValidationFailed {
message: "post-insertion".to_string(),
source: 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 {
reason: CavityFillingError::EmptyFanTriangulation,
};
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 {
reason: NeighborWiringError::MissingCell {
cell_key: CellKey::from(slotmap::KeyData::from_ffi(1)),
},
};
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() {
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: DelaunayTriangulationValidationError::VerificationFailed {
message: "test".to_string(),
},
},
InsertionError::DelaunayRepairFailed {
source: Box::new(DelaunayRepairError::PostconditionFailed {
message: "test".to_string(),
}),
context: DelaunayRepairFailureContext::LocalRepair,
},
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_orientation_canonicalization_error_hard_repair_is_internal() {
let error = InsertionError::DelaunayRepairFailed {
source: Box::new(DelaunayRepairError::VerificationFailed {
context: DelaunayRepairVerificationContext::LocalK3PostconditionVerification,
source: Box::new(FlipError::InvalidFlipContext {
reason: FlipContextError::MissingRemovedCellFrame,
}),
}),
context: DelaunayRepairFailureContext::OrientationCanonicalization,
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_orientation_canonicalization_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { ref message }
if message.contains("orientation canonicalization")
&& message.contains("removed cell frame")
),
"hard repair errors during orientation canonicalization should be internal: {mapped:?}"
);
}
#[test]
fn test_map_insertion_error_cavity_filling() {
let error = InsertionError::CavityFilling {
reason: CavityFillingError::EmptyFanTriangulation,
};
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 {
reason: NeighborWiringError::MissingCell {
cell_key: CellKey::from(slotmap::KeyData::from_ffi(1)),
},
};
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_preserves_typed_insertion_sources() {
let conflict = InsertionError::ConflictRegion(ConflictError::OpenBoundary {
facet_count: 2,
ridge_vertex_count: 1,
open_cell: CellKey::from(slotmap::KeyData::from_ffi(1)),
});
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(conflict);
assert!(matches!(
mapped,
TriangulationConstructionError::InsertionConflictRegion {
source: ConflictError::OpenBoundary { .. },
}
));
let location = InsertionError::Location(LocateError::EmptyTriangulation);
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(location);
assert!(matches!(
mapped,
TriangulationConstructionError::InsertionLocation {
source: LocateError::EmptyTriangulation,
}
));
let non_manifold = InsertionError::NonManifoldTopology {
facet_hash: 0xab,
cell_count: 3,
};
let mapped = DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(
non_manifold,
);
assert!(matches!(
mapped,
TriangulationConstructionError::InsertionNonManifoldTopology {
facet_hash: 0xab,
cell_count: 3,
}
));
let hull = InsertionError::HullExtension {
reason: HullExtensionReason::NoVisibleFacets,
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(hull);
assert!(matches!(
mapped,
TriangulationConstructionError::InsertionHullExtension {
reason: HullExtensionReason::NoVisibleFacets,
}
));
let delaunay = InsertionError::DelaunayValidationFailed {
source: DelaunayTriangulationValidationError::VerificationFailed {
message: "test".to_string(),
},
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(delaunay);
assert!(matches!(
mapped,
TriangulationConstructionError::InsertionDelaunayValidation { .. }
));
let topology = InsertionError::TopologyValidationFailed {
message: "test".to_string(),
source: TriangulationValidationError::EulerCharacteristicMismatch {
computed: 3,
expected: 2,
classification: TopologyClassification::Ball(3),
},
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(topology);
assert!(matches!(
mapped,
TriangulationConstructionError::InsertionTopologyValidation { .. }
));
}
#[test]
fn test_map_insertion_error_hard_repair_is_internal() {
let error = InsertionError::DelaunayRepairFailed {
source: Box::new(DelaunayRepairError::Flip(FlipError::UnsupportedDimension {
dimension: 1,
})),
context: DelaunayRepairFailureContext::LocalRepair,
};
let mapped =
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::map_insertion_error(error);
assert!(
matches!(
mapped,
TriangulationConstructionError::InternalInconsistency { ref message }
if message.contains("local repair")
&& message.contains("Bistellar flip not supported for D=1")
),
"hard repair errors during insertion should be internal: {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: 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 repair_operation_failed_preserves_source() {
let source = DelaunayRepairError::NonConvergent {
max_flips: 7,
diagnostics: Box::new(DelaunayRepairDiagnostics {
facets_checked: 3,
flips_performed: 7,
max_queue_len: 5,
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 err = DelaunayTriangulationValidationError::RepairOperationFailed {
operation: DelaunayRepairOperation::VertexRemoval,
source: Box::new(source),
};
let msg = err.to_string();
assert!(msg.contains("vertex removal"));
match &err {
DelaunayTriangulationValidationError::RepairOperationFailed {
operation: DelaunayRepairOperation::VertexRemoval,
source,
} if matches!(
source.as_ref(),
DelaunayRepairError::NonConvergent { max_flips: 7, .. }
) => {}
other => panic!("expected typed vertex-removal repair source, got {other:?}"),
}
let chained = err
.source()
.expect("typed repair failure should expose source error")
.to_string();
assert!(chained.contains("failed to converge after 7 flips"));
}
#[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().vertex(vk).unwrap().uuid();
dt.tds_mut().uuid_to_vertex_key.remove(&uuid);
match dt.validate() {
Err(DelaunayTriangulationValidationError::Tds(source))
if matches!(source.as_ref(), 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(source))
if matches!(
source.as_ref(),
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() {
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_retry_policy_default_is_shuffled_in_all_profiles() {
let policy = RetryPolicy::default();
match policy {
RetryPolicy::Shuffled {
attempts,
base_seed,
} => {
assert_eq!(
attempts.get(),
DELAUNAY_SHUFFLE_ATTEMPTS,
"default retry attempts should equal DELAUNAY_SHUFFLE_ATTEMPTS"
);
assert_eq!(base_seed, None, "default base_seed should be None");
}
other => panic!("RetryPolicy::default() should be Shuffled, got {other:?}"),
}
}
#[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_tds_validation() {
let err: DelaunayTriangulationConstructionError = TriangulationConstructionError::Tds(
TdsConstructionError::ValidationError(TdsError::InconsistentDataStructure {
message: "test".to_string(),
}),
)
.into();
assert!(
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::is_non_retryable_construction_error(
&err
),
"TDS validation failures should be non-retryable"
);
}
#[test]
fn test_is_non_retryable_construction_error_topology_validation_buckets() {
let vertex_key = VertexKey::from(KeyData::from_ffi(1));
let insertion_err: DelaunayTriangulationConstructionError =
TriangulationConstructionError::InsertionTopologyValidation {
message: "test".to_string(),
source: TriangulationValidationError::IsolatedVertex {
vertex_key,
vertex_uuid: Uuid::nil(),
},
}
.into();
let final_err: DelaunayTriangulationConstructionError =
TriangulationConstructionError::FinalTopologyValidation {
message: "test".to_string(),
source: InvariantError::Triangulation(
TriangulationValidationError::IsolatedVertex {
vertex_key,
vertex_uuid: Uuid::nil(),
},
)
.into(),
}
.into();
assert!(
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::is_non_retryable_construction_error(
&insertion_err
),
"InsertionTopologyValidation should be non-retryable"
);
assert!(
DelaunayTriangulation::<AdaptiveKernel<f64>, (), (), 3>::is_non_retryable_construction_error(
&final_err
),
"FinalTopologyValidation 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: Box::new(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: 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}"
);
}
}