Crate delaunay

Expand description

§delaunay

Rust crate providing D-dimensional Delaunay triangulations and convex hulls (2D through 5D explicitly tested) constructed with a PL-manifold (default) or pseudomanifold guarantee on finite point sets with Euclidean and toroidal global topologies. Uses exact predicates and Simulation of Simplicity for robustness and degeneracy handling, and Hilbert curves for deterministic insertion ordering and efficient spatial indexing. Provides an explicit 4-level validation hierarchy on individual elements, triangulation data structure validity, manifold topology, and Delaunay property adherence. Allows for the complete set of Pachner moves up to D=5 using bistellar flips, vertex insertion and deletion, and the conversion of non-Delaunay triangulations into Delaunay triangulations via bounded flip/rebuilds. Auxiliary data may be stored directly in vertices and simplices with external secondary maps provided for vertex- and simplex-keyed algorithm use, and the entire data structure is serializable/deserializable. Written in safe Rust with no unsafe code.

§📐 Introduction

This library implements dimension-generic Delaunay triangulations in Rust for computational geometry and scientific workflows. It is inspired by CGAL, which is a C++ library for computational geometry, and Spade, a Rust library focused on 2D triangulations. The goal is to provide a lightweight but rigorous Rust-native option for workflows that need explicit topology settings, validation levels, deterministic construction controls, and repair behavior.

The core idea is an implemented and validated algorithmic framework for robust Delaunay construction, PL-manifold-aware local moves, and bistellar repair. The software artifact is part of the contribution: public APIs, examples, property-based tests, diagnostics, and generated performance summaries are kept together so the library can be inspected, reused, and benchmarked rather than treated as a one-off implementation.

Use this crate when you want:

Delaunay triangulations or convex hulls in 2D through 5D.
A Rust-native bistellar flip / Pachner move API for topological editing and Delaunay repair.
Exact predicates and deterministic Simulation of Simplicity (SoS) handling for degenerate inputs.
PL-manifold checks and explicit topology guarantees for triangulations that need more than a bag of simplices.
Typed construction, insertion, validation, topology, and repair diagnostics instead of stringly error handling.
Validation reports that separate element, structure, topology, and Delaunay failures.
Batch construction controls for insertion order, deduplication, repair cadence, and retry behavior.
Release-mode 3D construction through 10,000 vertices with final Levels 1–4 validation in the current large-scale characterization harness.
PL-manifold-aware editing via bistellar flips.

This is not a replacement for full meshing packages such as CGAL, TetGen, or Gmsh when you need constrained Delaunay triangulations, out-of-core meshing, GPU/parallel meshing, or production-scale dynamic remeshing.

§🧪 Scientific Basis

This crate models triangulations of finite point sets in R^d as oriented simplicial complexes with explicit combinatorial and geometric checks. The framework couples robust predicates, topology-aware local moves, repair policies, validation reports, and benchmarked workflows instead of treating these as separate utilities.

Core operational invariant for editing/repair: coherent orientation + PL-manifold validity.
Local move system: exposed bistellar flips (k = 1, 2, 3 and inverses), providing the supported Pachner moves set in dimensions up to 5D.
Geometric convergence basis in finite-point workflows: Herbert Edelsbrunner and Nimish R. Shah, Incremental Topological Flipping Works for Regular Triangulations, Algorithmica (1996), https://doi.org/10.1007/BF01975867.
Robust predicate basis: Shewchuk-style floating-point filters with exact fallback, plus deterministic Simulation of Simplicity for exact degeneracies.
Topology basis: Level 3 validation checks PL-manifold structure, links, and Euler/topological consistency before Level 4 Delaunay predicates are trusted.
Artifact basis: unit tests, integration tests, property tests, examples, release benchmark summaries, and docs.rs documentation exercise the same public APIs users copy.
Scope of claims: guarantees apply to supported library workflows (construction, flip-based repair, and validation APIs), not arbitrary external mutation of internal structures.

See REFERENCES.md, Invariants, and the Numerical Robustness Guide for the complete technical background.

§✨ Features

Copyable data types associated with vertices and simplices (integers, floats, chars, custom enums), plus SimplexSecondaryMap and VertexSecondaryMap aliases for caller-owned key-indexed algorithm state
D-dimensional Delaunay triangulations
D-dimensional Convex hulls
Bistellar flip / Pachner moves Edit API up to 5D: k-flips for k = 1, 2, 3 plus inverse moves
Delaunay repair using bistellar flips for k=2/k=3 with inverse edge/triangle queues in 4D/5D
Simulation of Simplicity (SoS) for deterministic handling of degenerate orientation and in-sphere configurations
PL-manifold topology validation by default, with Pseudomanifold available as an explicit opt-out
Toroidal (periodic) triangulations via DelaunayTriangulationBuilder: .toroidal(...) canonicalizes points into the fundamental domain, while .toroidal_periodic(...) builds a validated periodic image-point quotient in 2D and compact 3D
Geometry quality metrics for simplices: radius ratio and normalized volume (dimension-agnostic)
Serialization/deserialization of all data structures to/from JSON
Tested for 2-, 3-, 4-, and 5-dimensional triangulations
Focused public preludes for construction, insertion, repair, validation, topology, query, geometry, generators, ordering, collections, TDS, and diagnostics workflows
Configurable predicate kernels: AdaptiveKernel (default; exact arithmetic + SoS), RobustKernel (exact, preserves degeneracy signals), FastKernel (raw floating-point predicates for well-conditioned exploratory work; not accepted by explicit repair APIs)
Bulk insertion ordering (InsertionOrderStrategy): Hilbert curve (default) or input order
Batch construction options (ConstructionOptions): optional deduplication, configurable local Delaunay repair cadence, and deterministic retries
Incremental construction APIs: insertion, insertion statistics, and transactional vertex removal (remove_vertex)
4-level validation hierarchy (element validity → TDS structural validity → manifold topology → Delaunay property), including full diagnostics via validation_report
Coherent combinatorial orientation validation/normalization for simplices, maintaining oriented simplicial complexes
Typed construction, insertion, TDS, topology, validation, and repair errors that preserve source context for callers and diagnostics
Reusable research software artifact: public examples, property tests, diagnostics, docs.rs landing-page documentation, and benchmark summaries generated from checked public workflows
Release performance summaries generated from the public API benchmark contract, current Criterion run metadata, and generated simplex counts
10,000-vertex 3D large-scale characterization run: zero skipped vertices, final flip repair clean, and validation_report OK for Levels 1–4 in roughly 100 seconds on maintainer Apple M4 Max hardware
Safe Rust: #![forbid(unsafe_code)]

See CHANGELOG.md for release details. Older releases are archived under docs/archive/changelog/.

§🟢 Minimal Construction Example

The construction API has two entry points:

DelaunayTriangulationBuilder - primary construction interface for the common case and advanced configuration (custom options, toroidal topology, custom kernels)
DelaunayTriangulation::new(&vertices) - legacy convenience constructor

Add the library to your crate:

cargo add delaunay

Choose the smallest prelude that matches the task:

Task	Import
Construct/configure a Delaunay triangulation	`use delaunay::prelude::construction::*`
Read-only traversal, adjacency, convex hulls, and comparison helpers	`use delaunay::prelude::query::*`
Points, kernels, predicates, and geometric measures	`use delaunay::prelude::geometry::*`
Random points or triangulations for examples, tests, and benchmarks	`use delaunay::prelude::generators::*`
Low-level incremental insertion building blocks	`use delaunay::prelude::insertion::*`
Bistellar flips / Edit API	`use delaunay::prelude::flips::*`
Delaunay repair diagnostics and policies	`use delaunay::prelude::repair::*`
Delaunayize workflow	`use delaunay::prelude::delaunayize::*`
Construction telemetry diagnostics	`use delaunay::prelude::diagnostics::*`
Construction validation cadence/policy	`use delaunay::prelude::validation::*`
Hilbert ordering and quantization utilities	`use delaunay::prelude::ordering::*`
Low-level TDS simplices, facets, keys, and validation reports	`use delaunay::prelude::tds::*`
Collection aliases and small buffers	`use delaunay::prelude::collections::*`
Topology validation and Euler characteristic helpers	`use delaunay::prelude::topology::validation::*`
Topological spaces and topology traits	`use delaunay::prelude::topology::spaces::*`

use delaunay::prelude::* remains available for quick experiments, but examples and benchmarks in this repository prefer focused preludes so imports document intent. The broad delaunay::prelude::* import is retained for compatibility, but new docs and tests should prefer the narrow workflow preludes above.

§Low-level imports

delaunay::core is an internal implementation namespace. Public low-level APIs are exposed through delaunay::tds, delaunay::collections, delaunay::algorithms, and delaunay::query, plus the matching focused preludes. Contributors should follow the namespace policy in CONTRIBUTING.md and docs/code_organization.md.

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, vertex,
};

fn main() -> Result<(), DelaunayTriangulationConstructionError> {
    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]),
    ];

    let dt = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

    assert_eq!(dt.dim(), 4);
    assert_eq!(dt.number_of_vertices(), 6);

    // Optional verification:
    // - `dt.is_valid()` checks Level 4 only (Delaunay property).
    // - `dt.validate()` checks Levels 1-4 (elements + structure + topology + Delaunay).
    assert!(dt.validate().is_ok());
    Ok(())
}

§Toroidal (Periodic) Triangulations

For periodic boundary conditions, use DelaunayTriangulationBuilder:

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, TopologyKind, vertex,
};

fn main() -> Result<(), DelaunayTriangulationConstructionError> {
    let vertices = vec![
        vertex!([0.1, 0.2]),
        vertex!([0.8, 0.3]),
        vertex!([0.5, 0.7]),
        vertex!([1.2, 0.4]), // Wraps to [0.2, 0.4]
    ];

    let dt = DelaunayTriangulationBuilder::new(&vertices)
        .toroidal([1.0, 1.0])
        .build::<()>()?;

    assert_eq!(dt.topology_kind(), TopologyKind::Toroidal);
    Ok(())
}

For boundary-facet identification and periodic neighbor pointers, use .toroidal_periodic([..]) in 2D or compact 3D; see the toroidal construction workflow for the full recipe and current 4D/5D guardrails.

§Need more control?

Editing with flips (Edit API): see docs/workflows.md for a minimal example and docs/api_design.md for details.
Flip-based Delaunay repair, including the heuristic rebuild fallback (repair_delaunay_with_flips*): see docs/workflows.md.
Repair diagnostics and mutating-operation rollback: remove_vertex rolls back if post-removal repair or orientation canonicalization fails, and repair failures preserve typed source errors for debugging.
Insertion outcomes and statistics (insert_with_statistics, insert_best_effort_with_statistics, InsertionOutcome, InsertionStatistics): see docs/workflows.md and docs/numerical_robustness_guide.md.
Topology guarantees (TopologyGuarantee) and automatic topology validation (ValidationPolicy): see docs/validation.md and docs/topology.md.
Release benchmark summaries: see benches/README.md and benches/PERFORMANCE_RESULTS.md.

§✅ Validation and Guarantees

Level	What is validated	Primary API
1	Element validity (vertex/simplex primitives)	`dt.validate()` / `dt.validation_report()`
2	TDS structural validity (keys, incidences, neighbors)	`dt.tds().is_valid()`
3	Manifold topology (link checks, Euler/topological consistency)	`dt.as_triangulation().is_valid()`
4	Delaunay property (empty-circumsphere via local predicates)	`dt.is_valid()`
1-4	Cumulative checks with diagnostics	`dt.validate()` or `dt.validation_report()`

TopologyGuarantee controls which Level 3 manifold constraints are enforced, and ValidationPolicy controls when Level 3 checks run automatically during incremental insertion. Incompatible combinations are rejected by the fallible try_set_* policy setters; use ValidationPolicy::ExplicitOnly for caller-owned full-validation checkpoints with the default PL-manifold guarantee.

§🔬 Reproducibility

The construction pipeline exposes deterministic controls for experiments and regression testing:

Deterministic insertion ordering via InsertionOrderStrategy: Hilbert (default) or Input (use Input to preserve caller-provided order exactly)
Deterministic preprocessing via DedupPolicy
Deterministic retry behavior via RetryPolicy (including seeded shuffled retries) or RetryPolicy::Disabled
Cadenced batch repair behavior via ConstructionOptions when large batch construction should repair local Delaunay fronts during insertion
Explicit topology/validation configuration via TopologyGuarantee and ValidationPolicy

use delaunay::prelude::construction::{
    ConstructionOptions, DedupPolicy, DelaunayTriangulationBuilder, InsertionOrderStrategy,
    RetryPolicy, TopologyGuarantee, DelaunayTriangulationConstructionError, vertex,
};
use delaunay::prelude::validation::ValidationPolicy;

fn main() -> Result<(), DelaunayTriangulationConstructionError> {
    let vertices = vec![
        vertex!([0.0, 0.0]),
        vertex!([1.0, 0.0]),
        vertex!([0.0, 1.0]),
    ];

    let options = ConstructionOptions::default()
        .with_insertion_order(InsertionOrderStrategy::Input)
        .with_dedup_policy(DedupPolicy::Exact)
        .with_retry_policy(RetryPolicy::Disabled);

    let mut dt = DelaunayTriangulationBuilder::new(&vertices)
        .topology_guarantee(TopologyGuarantee::PLManifold)
        .construction_options(options)
        .build::<()>()?;

    dt.set_validation_policy(ValidationPolicy::Always);
    assert!(dt.validate().is_ok());
    Ok(())
}

For reproducible checks in CI/local runs, use just check, just test, just doc-check, or just ci.

§⚠️ Limitations

Dimension coverage: CI and property-test coverage target 2D–5D.
Exact predicate limits: exact orientation is available through D=6; exact in-sphere is available through D=5. For D≥6, in-sphere classification relies on symbolic perturbation and deterministic tie-breaking because the (D+2)×(D+2) determinant exceeds the stack matrix limit.
Periodic domains: .toroidal() canonicalizes coordinates into the fundamental domain. .toroidal_periodic() uses the periodic image-point method and is release-validated in 2D and compact 3D. 4D/5D periodic quotients fail fast pending scalable construction work in issue #416.
Large 4D+ batches: thousands of 4D points can be expensive to investigate. Use release mode and the large-scale debug harness for characterization.
3D scale: the default just debug-large-scale-3d helper uses 7,500 vertices for the near-one-minute acceptance path. The 10,000-vertex run has also passed full Levels 1–4 validation as a heavier characterization probe; use just debug-large-scale-3d 10000 1 for local numbers.
Feature gaps: Constrained Delaunay triangulations, Voronoi diagrams, built-in visualization, GPU/parallel meshing, and out-of-core construction are out of scope today.
Validation/repair guarantees assume the library-managed construction/editing pipeline.

See Limitations and Scope for details and Roadmap for active follow-up work.

§🚧 Project History

This crate was originally maintained at https://github.com/oovm/shape-rs through version 0.1.0. The original implementation provided basic Delaunay triangulation functionality.

Starting with version 0.3.4, maintenance transferred to this repository, which hosts a rewritten d-dimensional implementation focused on computational geometry research applications.

📚 Docs for the original implementation (0.1.0): https://docs.rs/delaunay/0.1.0/delaunay/
📚 Docs for the rewritten implementation (0.3.4+): https://docs.rs/delaunay

§🤝 How to Contribute

We welcome contributions! Here’s a quickstart:

# Clone and setup
git clone https://github.com/acgetchell/delaunay.git
cd delaunay

# Setup development environment (installs tools, builds project)
cargo install just
just setup            # Installs all development tools and dependencies

# Development workflow
just check            # All non-mutating lints/validators
just fix              # Apply formatters/auto-fixes (mutating)
just test             # Tests + benchmark/release compile smoke
just ci               # Comprehensive checks + tests + examples
just --list           # See all available commands
just help-workflows   # Show common workflow patterns

Benchmark commands that produce performance data use the perf Cargo profile for consistent ThinLTO settings. just ci remains the comprehensive validation path: it runs checks, the test workflow, and examples, but it does not pay the perf profile cost unless measuring performance.

For release performance documentation, run just bench-perf-summary from the release PR branch after version and documentation updates. It refreshes benches/PERFORMANCE_RESULTS.md from the public API Criterion suite, circumsphere predicate benchmarks, current run metadata, and generated simplex counts.

Try the examples:

just examples         # Run all examples
# Or run specific examples:
cargo run --release --example triangulation_and_hull
cargo run --release --example delaunayize_repair

§📋 Examples

The examples/ directory contains several demonstrations:

delaunayize_repair: Demonstrates the delaunayize_by_flips workflow (bounded topology repair + flip-based Delaunay repair + optional fallback)
diagnostics: Opt-in structured diagnostics for validation and deliberately non-Delaunay TDS examples
into_from_conversions: Demonstrates Into/From trait conversions and utilities
numerical_robustness: Compares FastKernel, RobustKernel, and AdaptiveKernel on degenerate predicate inputs
point_comparison_and_hashing: Demonstrates point comparison and hashing behavior
topology_editing: Builder API vs Edit API in 2D/3D (bistellar flips and Delaunay preservation)
triangulation_and_hull: Seeded 3D and 4D triangulations, boundary traversal, convex hull extraction, and hull containment/visibility queries

For detailed documentation, sample output, and usage instructions for each example, see examples/README.md.

For comprehensive guidelines on development environment setup, testing, benchmarking, performance analysis, and development workflow, please see CONTRIBUTING.md.

This includes information about:

Building and testing the library
Running benchmarks and performance analysis
Code style and standards
Submitting changes and pull requests
Project structure and development tools

§📖 Documentation

API Design - Builder vs Edit API design (explicit bistellar flips)
Benchmarks - Benchmark suites, perf-profile workflow, generated summaries, and release canaries
Code Organization - Project structure and module patterns
Diagnostics - Diagnostic helpers, structured reports, telemetry, and debug switches
Invariants - Theoretical background and rationale for the topological and geometric invariants
Numerical Robustness Guide - Robustness strategies, kernels, and retry/repair behavior
Orientation Spec - Coherent combinatorial and geometric orientation rules
Property Testing Summary - Property-based testing with proptest (where tests live, how to run)
Limitations and Scope - Supported dimensions, predicate limits, and feature gaps
Releasing - Release workflow (changelog + benchmarks + publish)
Roadmap - Current follow-up work and deferred features
Topology - Level 3 topology validation (manifoldness + Euler characteristic) and module overview
Validation Guide - Comprehensive 4-level validation hierarchy guide (element → structural → manifold → Delaunay)
Workflows - Happy-path construction plus practical Builder/Edit recipes (stats, repairs, and minimal flips)

§📎 How to Cite

If you use this software in academic work, cite the Zenodo DOI and include the software metadata from CITATION.cff.

DOI: https://doi.org/10.5281/zenodo.16931097
Citation metadata: CITATION.cff

@software{getchell_delaunay,
  author = {Adam Getchell},
  title = {delaunay: A d-dimensional Delaunay triangulation library},
  doi = {10.5281/zenodo.16931097},
  url = {https://github.com/acgetchell/delaunay}
}

For release-specific fields (version, release date, ORCID), prefer CITATION.cff.

§📚 References

For a comprehensive list of academic references and bibliographic citations used throughout the library, see REFERENCES.md.

§🤖 AI Agents

This repository contains an AGENTS.md file, which defines the canonical rules and invariants for all AI coding assistants and autonomous agents working on this codebase.

AI tools (including ChatGPT, Claude, CodeRabbit, Codex, Cursor, GitHub Copilot, KiloCode, Warp, and CI repair agents) are expected to read and follow AGENTS.md when proposing or applying changes.

Portions of this library were developed with the assistance of these AI tools:

All code was written and/or reviewed and validated by the author.

§Documentation map

The README above is included verbatim and serves as the user-facing introduction to the crate (overview, features, and quick-start examples).

Everything below this line specifies the semantic and correctness contract of the delaunay crate and is intended for users who need stronger guarantees, deeper understanding of invariants, or who are extending the implementation.

This crate’s documentation is intentionally layered by audience and intent:

README.md (included above): User-facing overview, feature list, and quick-start examples.
Crate-level documentation (lib.rs) (this document): The programming contract of the library: what invariants are enforced, when validation runs, and what errors mean.

In particular, this document covers:
- The validation hierarchy and invariant stack (Levels 1–4)
- Topological guarantees (TopologyGuarantee) and insertion-time validation policy (ValidationPolicy)
- High-level error semantics and programming contract (transactional operations, duplicate rejection)
docs/workflows.md: Task-oriented, end-to-end usage recipes (Builder API, Edit API, validation, repairs, diagnostics, and statistics).
docs/validation.md: Formal definitions of validation Levels 1–4, their costs, and guidance on when each level should be applied.
docs/diagnostics.md: Opt-in diagnostic helpers, structured reports, debug switches, and guidance for producing useful failure reports without expanding the default API surface.
docs/invariants.md: Deeper theoretical discussion of topological and geometric invariants (PL-manifold conditions, ridge/vertex links, ordering heuristics, and convergence assumptions), plus algorithmic background and limitations.

§Which import do I need?

The crate provides several focused prelude modules. Pick the one that matches your task:

Task	Import
Construct/configure a Delaunay triangulation	`use delaunay::prelude::construction::*`
Build/validate/repair generic triangulations	`use delaunay::prelude::triangulation::*`
Low-level incremental insertion building blocks	`use delaunay::prelude::insertion::*`
Read-only queries, traversal, convex hull	`use delaunay::prelude::query::*`
Point location and conflict-region algorithms	`use delaunay::prelude::algorithms::*`
Geometry helpers, predicates, points	`use delaunay::prelude::geometry::*`
Random points / triangulations for examples and tests	`use delaunay::prelude::generators::*`
Hilbert ordering and quantization utilities	`use delaunay::prelude::ordering::*`
Bistellar flips (Pachner moves)	`use delaunay::prelude::flips::*`
Delaunay repair and flip-based Level 4 validation	`use delaunay::prelude::repair::*`
Delaunayize workflow (repair + flip)	`use delaunay::prelude::delaunayize::*`
Construction telemetry diagnostics	`use delaunay::prelude::diagnostics::*`
Construction validation cadence/policy	`use delaunay::prelude::validation::*`
Topology validation, Euler characteristic	`use delaunay::prelude::topology::validation::*`
Topological spaces and topology traits	`use delaunay::prelude::topology::spaces::*`
Low-level TDS simplices, facets, keys	`use delaunay::prelude::tds::*`
Collection types (`FastHashMap`, etc.)	`use delaunay::prelude::collections::*`
Broad convenience import for exploratory code	`use delaunay::prelude::*`

§Public low-level namespace policy

High-level Delaunay APIs are available directly from the crate root and focused root modules: DelaunayTriangulation, DelaunayTriangulationBuilder, construction, flips, repair, validation, and delaunayize. The nested delaunay::delaunay::* facade is intentionally not part of the public API; use the crate root or a focused prelude instead.

use delaunay::delaunay::DelaunayTriangulation;

The low-level implementation namespace is private. The public low-level surface is exposed through curated modules: tds, collections, algorithms, and query, plus the matching focused preludes. These names describe the data structures and workflows users compose without colliding with Rust’s standard core vocabulary.

Prefer these curated modules and focused preludes in examples, doctests, benchmarks, and downstream-style integration tests. High-level Delaunay construction remains outside the low-level TDS/query surface.

§Examples (contract-oriented)

§Validation hierarchy (Levels 1–4)

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, vertex,
};
use delaunay::prelude::insertion::InsertionError;

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 = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

// Levels 1–2: elements + structural (TDS)
assert!(dt.tds().validate().is_ok());

// Levels 1–3: elements + structural + topology
assert!(dt.as_triangulation().validate().is_ok());

// Level 4 only: Delaunay property (assumes Levels 1–3)
assert!(dt.is_valid().is_ok());

// Levels 1–4: full cumulative validation
assert!(dt.validate().is_ok());

§Topology guarantees and insertion-time validation (`TopologyGuarantee`, `ValidationPolicy`)

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, TopologyGuarantee,
    vertex,
};
use delaunay::prelude::validation::ValidationPolicy;

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 = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

assert_eq!(dt.topology_guarantee(), TopologyGuarantee::PLManifold);
assert_eq!(dt.validation_policy(), ValidationPolicy::ExplicitOnly);

dt.set_topology_guarantee(TopologyGuarantee::Pseudomanifold);
dt.set_validation_policy(ValidationPolicy::Always);

assert_eq!(dt.topology_guarantee(), TopologyGuarantee::Pseudomanifold);
assert_eq!(dt.validation_policy(), ValidationPolicy::Always);

§Transactional operations and duplicate rejection

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, vertex,
};
use delaunay::prelude::insertion::InsertionError;

let vertices = vec![
    vertex!([0.0, 0.0]),
    vertex!([1.0, 0.0]),
    vertex!([0.0, 1.0]),
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

let before_vertices = dt.number_of_vertices();
let before_simplices = dt.number_of_simplices();

// Duplicate coordinates are rejected.
let result = dt.insert(vertex!([0.0, 0.0]));
assert!(matches!(result, Err(InsertionError::DuplicateCoordinates { .. })));

// On error, the triangulation is unchanged.
assert_eq!(dt.number_of_vertices(), before_vertices);
assert_eq!(dt.number_of_simplices(), before_simplices);

§Triangulation invariants and validation hierarchy

The crate is organized as a small validation stack, where each layer adds additional invariants on top of the preceding one:

Vertex and Simplex provide element validity checks. Level 1 (elements) validation checks invariants such as:
- Vertex coordinates – finite (no NaN/∞) and UUID is non-nil.
- Simplex shape – exactly D+1 distinct vertex keys, valid UUID, and neighbor buffer length (if present) is D+1.
These checks are surfaced via Vertex::is_valid and Simplex::is_valid, and are automatically run by Tds::validate (Levels 1–2).
Tds (Triangulation Data Structure) stores the combinatorial / structural representation. Level 2 (structural) validation checks invariants such as:
- Vertex mappings – every vertex UUID has a corresponding key and vice versa.
- Simplex mappings – every simplex UUID has a corresponding key and vice versa.
- No duplicate simplices – no two maximal simplices share the same vertex set.
- Facet sharing – each facet is shared by at most 2 simplices (1 on the boundary, 2 in the interior).
- Neighbor consistency – neighbor relationships are mutual and reference a shared facet.
These checks are surfaced via Tds::is_valid (structural only) and Tds::validate (Levels 1–2, elements + structural). For cumulative diagnostics across the full stack, use DelaunayTriangulation::validation_report.
Triangulation builds on the TDS and validates manifold topology. Level 3 (topology) validation is performed by Triangulation::is_valid (Level 3 only) and Triangulation::validate (Levels 1–3), which:
- Strengthens facet sharing to the manifold facet property: each facet belongs to exactly 1 simplex (boundary) or exactly 2 simplices (interior).
- Checks the Euler characteristic of the triangulation (using the topology module).
DelaunayTriangulation builds on Triangulation and validates the geometric Delaunay condition. Level 4 (Delaunay property) validation is performed by DelaunayTriangulation::is_valid (Level 4 only) and DelaunayTriangulation::validate (Levels 1–4). Construction is designed to satisfy the Delaunay property, but in rare cases it may be violated for near-degenerate inputs (see Issue #120).

§Validation

The crate exposes four validation levels (element → structural → manifold → Delaunay). The canonical guide (when to use each level, complexity, examples, troubleshooting) lives in docs/validation.md: https://github.com/acgetchell/delaunay/blob/main/docs/validation.md

In brief:

Level 1 (elements / Vertex + Simplex): Vertex::is_valid() / Simplex::is_valid() for element checks, or dt.tds().validate() for Levels 1–2.
Level 2 (structural / Tds): dt.tds().is_valid() for a quick check, or dt.tds().validate() for Levels 1–2.
Level 3 (topology / Triangulation): dt.as_triangulation().is_valid() for topology-only checks, or dt.as_triangulation().validate() for Levels 1–3.
Level 4 (Delaunay / DelaunayTriangulation): dt.is_valid() for the empty-circumsphere property, or dt.validate() for Levels 1–4.
Full diagnostics: dt.validation_report() returns all violated invariants across Levels 1–4.

§Automatic topology validation during insertion (`ValidationPolicy`)

In addition to explicit validation calls, incremental construction (new() / insert*()) can run an automatic Level 3 topology validation pass after insertion, controlled by ValidationPolicy.

The initial policy is derived from the active topology guarantee. The default TopologyGuarantee::PLManifold uses ValidationPolicy::ExplicitOnly: mandatory local topology checks still run during insertion, while full Level 3 validation is a caller-owned explicit checkpoint.

This automatic pass only runs Level 3 (Triangulation::is_valid()). It does not run Level 4.

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, vertex,
};
use delaunay::prelude::insertion::InsertionError;
use delaunay::prelude::validation::{ValidationConfigurationError, ValidationPolicy};

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 = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

// Caller-owned validation mode: keep mandatory topology checks, but run full
// Level 3 validation only through explicit validation calls.
dt.try_set_validation_policy(ValidationPolicy::ExplicitOnly)?;

// Do incremental work...
dt.insert(vertex!([0.2, 0.2, 0.2]))?;

// ...then explicitly validate the topology layer when you need a certificate.
assert!(dt.as_triangulation().validate().is_ok());

§Choosing Level 3 topology guarantee (`TopologyGuarantee`)

This section specifies what invariants are enforced. The formal topological definitions and rationale live in docs/invariants.md.

Level 3 topology validation is parameterized by TopologyGuarantee. This is separate from ValidationPolicy: it controls what invariants Level 3 enforces, not when automatic validation runs.

TopologyGuarantee::PLManifold (default): enforces manifold facet degree, boundary closure, connectedness, Euler characteristic, and link-based manifold conditions. Ridge-link checks are applied incrementally during insertion, with vertex-link validation performed at construction completion.

The formal topological definitions, link conditions, and rationale for this validation strategy are documented in docs/invariants.md.
TopologyGuarantee::PLManifoldStrict: vertex-link validation after every insertion (slowest, maximum safety).
TopologyGuarantee::Pseudomanifold: skips vertex-link validation (may be faster), but bistellar flip convergence is not guaranteed and you may want to validate the Delaunay property explicitly for near-degenerate inputs.

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, vertex,
};

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 = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

// For `TopologyGuarantee::PLManifold`, full certification includes a completion-time
// vertex-link validation pass.
assert!(dt.as_triangulation().validate_at_completion().is_ok());

use delaunay::prelude::construction::{
    DelaunayTriangulationBuilder, DelaunayTriangulationConstructionError, vertex,
};

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 = DelaunayTriangulationBuilder::new(&vertices).build::<()>()?;

// `validate()` returns the first violation; `validation_report()` is intended for
// debugging/telemetry where you want the full set of violated invariants.
assert!(dt.validation_report().is_ok());

For implementation details on invariant enforcement, see the incremental insertion implementation.

§Programming contract (high-level)

Transactional mutations: Construction and incremental operations are designed to be all-or-nothing. If an operation returns Err(_), the triangulation is rolled back to its previous state.
Duplicate detection: Near-duplicate coordinates are rejected using a scale-aware Euclidean tolerance based on nearby geometry and floating-point resolution, returning InsertionError::DuplicateCoordinates. Duplicate UUIDs return InsertionError::DuplicateUuid.
Explicit verification: Use dt.validate() for cumulative verification (Levels 1–4), or dt.is_valid() for Level 4 only.

Re-exports§

pub use crate::builder::DelaunayTriangulationBuilder;
pub use crate::construction::ConstructionOptions;
pub use crate::construction::ConstructionSkipSample;
pub use crate::construction::ConstructionSlowInsertionSample;
pub use crate::construction::ConstructionStatistics;
pub use crate::construction::DedupPolicy;
pub use crate::construction::DelaunayConstructionFailure;
pub use crate::construction::DelaunayConstructionRepairPhase;
pub use crate::construction::DelaunayTriangulationConstructionError;
pub use crate::construction::DelaunayTriangulationConstructionErrorWithStatistics;
pub use crate::construction::InitialSimplexStrategy;
pub use crate::construction::InsertionOrderStrategy;
pub use crate::construction::RetryPolicy;
pub use crate::repair::DelaunayCheckPolicy;
pub use crate::repair::DelaunayRepairHeuristicConfig;
pub use crate::repair::DelaunayRepairHeuristicSeeds;
pub use crate::repair::DelaunayRepairOperation;
pub use crate::repair::DelaunayRepairOutcome;
pub use crate::repair::DelaunayRepairPolicy;
pub use crate::validation::DelaunayTriangulationValidationError;

Modules§

algorithms: Public low-level algorithms that are useful outside full construction.
builder: Fluent builder for Delaunay triangulations. Fluent builder for DelaunayTriangulation with optional toroidal topology.
collections: Public collection aliases and small-buffer types used by low-level APIs.
construction: Batch construction options, errors, statistics, and policy helpers. Batch construction options, errors, statistics, and policy helpers.
delaunayize: End-to-end “repair then delaunayize” workflow. End-to-end “repair then delaunayize” workflow.
diagnostics: Construction and performance diagnostics. Construction and performance diagnostics for triangulation workflows.
flips: Triangulation editing operations (bistellar flips). Triangulation editing operations (bistellar flips).
geometry: Contains geometric types including the Point struct and geometry predicates.
prelude: A prelude module that re-exports commonly used types and macros. This makes it easier to import the most commonly used items from the crate.
query: Public read-only traversal, adjacency, convex-hull, and set-comparison APIs.
repair: Repair policies and outcomes for Delaunay triangulations. Repair policies and outcomes for Delaunay triangulations.
tds: Public low-level topology data structures and TDS helpers.
topology: Topology analysis and validation for triangulated spaces.
validation: Validation scheduling helpers for triangulation diagnostics. Validation scheduling helpers for triangulation construction diagnostics.

Macros§

assert_jaccard_gte: Assert that the Jaccard index between two sets meets or exceeds a threshold.
vertex: Convenience macro for creating vertices with less boilerplate.

Structs§

DelaunayRepairErrorSummary: Compact summary of a DelaunayRepairError for small by-value error payloads.
DelaunayTriangulation: Delaunay triangulation with incremental insertion support.
DelaunayViolationDetaildiagnostics: Details for the first simplex in a DelaunayViolationReport.
DelaunayViolationReportdiagnostics: Structured summary of Delaunay empty-circumsphere violations.
DuplicateDetectionMetrics: Telemetry counters for duplicate-coordinate detection.
InsertionErrorSummary: Compact summary of an InsertionError for small by-value error payloads.
InsertionStatistics: Statistics about a vertex insertion operation.
PlManifoldRepairStats: Statistics and artifacts collected during PL-manifold repair.
SuspicionFlags: Adaptive error-checking on suspicious operations.
Triangulation: Generic triangulation combining kernel and data structure.

Enums§

CavityFillingError: Structured reason why cavity filling failed.
CavityRepairStage: Stage where cavity repair detected invalid facet sharing.
DeduplicationError: Errors returned by fallible vertex deduplication helpers.
DelaunayRepairErrorKind: Flip-repair failure category used by compact error summaries.
DelaunayRepairFailureContext: Insertion-stage context for flip-based Delaunay repair failures.
DelaunayValidationError: Errors that can occur during Delaunay property validation.
HullExtensionReason: Reason for hull extension failure.
InitialSimplexConstructionError: Structured reason why initial-simplex construction failed during insertion.
InsertionError: Error during incremental insertion.
InsertionErrorKind: Insertion failure category used by compact error summaries.
InsertionErrorSourceKind: Nested discriminant preserved by an InsertionErrorSummary.
InsertionOutcome: Outcome of a single-vertex insertion attempt.
InsertionResult: Result of an insertion attempt.
NeighborRebuildError: Structured reason why neighbor repair failed after cavity repair.
NeighborWiringError: Structured reason why neighbor wiring failed.
PlManifoldRepairError: Errors that can occur during PL-manifold repair.
RepairDecision: Decision outcome for a flip-based Delaunay repair attempt.
RepairSkipReason: Reason why flip-based repair was skipped.
TdsConstructionFailure: Compact, typed summary of a TdsConstructionError.
TdsValidationFailure: Compact, typed summary of a TdsError used inside insertion-stage errors.
TopologicalOperation: Semantic classification of topological modifications to a triangulation.
TopologyGuarantee: Selects which topological invariants are checked by Level 3 validation.
TriangulationConstructionError: Errors that can occur during triangulation construction.
TriangulationValidationError: Errors that can occur during triangulation topology validation (Level 3).
ValidationConfigurationError: Errors returned when validation scheduling and topology guarantees are incoherent.
ValidationPolicy: Policy controlling when the triangulation runs global validation passes.

Functions§

debug_print_first_delaunay_violationdiagnostics: Debug helper: print detailed information about the first detected Delaunay violation (or all vertices if none are found) to aid in debugging.
delaunay_violation_reportdiagnostics: Build a structured Delaunay violation report.
extend_hull: Extend the convex hull by connecting an exterior vertex to visible boundary facets.
fill_cavity: Fill cavity by creating new simplices connecting boundary facets to new vertex.
find_delaunay_violations: Find simplices that violate the Delaunay property.
is_normal: The function is_normal checks that structs implement auto traits. Traits are checked at compile time, so this function is only used for testing.
repair_neighbor_pointers: Repair neighbor pointers using a global facet-incidence rebuild.
repair_neighbor_pointers_local: Repair neighbor pointers for a locally affected simplex set.
wire_cavity_neighbors: Wire neighbor relationships for newly created cavity simplices.

Crate delaunay

Crate delaunay Copy item path

§delaunay

§📐 Introduction

§🧪 Scientific Basis

§✨ Features

§🟢 Minimal Construction Example

§Low-level imports

§Toroidal (Periodic) Triangulations

§Need more control?

§✅ Validation and Guarantees

§🔬 Reproducibility

§⚠️ Limitations

§🚧 Project History

§🤝 How to Contribute

§📋 Examples

§📖 Documentation

§📎 How to Cite

§📚 References

§🤖 AI Agents

§Documentation map

§Which import do I need?

§Public low-level namespace policy

§Examples (contract-oriented)

§Validation hierarchy (Levels 1–4)

§Topology guarantees and insertion-time validation (TopologyGuarantee, ValidationPolicy)

§Transactional operations and duplicate rejection

§Triangulation invariants and validation hierarchy

§Validation

§Automatic topology validation during insertion (ValidationPolicy)

§Choosing Level 3 topology guarantee (TopologyGuarantee)

§Programming contract (high-level)

Re-exports§

Modules§

Macros§

Structs§

Enums§

Functions§

Crate delaunay

§Topology guarantees and insertion-time validation (`TopologyGuarantee`, `ValidationPolicy`)

§Automatic topology validation during insertion (`ValidationPolicy`)

§Choosing Level 3 topology guarantee (`TopologyGuarantee`)