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.

This library is for computational geometry and scientific workflows that need more than a set of triangles: explicit topology settings, deterministic construction controls, typed diagnostics, validation levels, and repair behavior. It is inspired by CGAL and Spade, but focuses on a safe, inspectable, d-dimensional Rust API.

Use this crate when you want:

• Delaunay triangulations or convex hulls in 2D through 5D.
• Exact predicates and deterministic SoS handling for degenerate inputs.
• PL-manifold checks and explicit topology guarantees.
• PL-manifold-aware editing via bistellar flips and bounded Delaunay repair.
• Validation reports that separate element, structure, topology, and Delaunay failures.
• Typed construction, insertion, validation, topology, and repair diagnostics.

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.

The crate models finite point-set triangulations as oriented simplicial complexes with separate combinatorial and geometric checks. Its robustness story comes from Shewchuk-style floating-point filters, exact arithmetic fallback, deterministic Simulation of Simplicity, and topology validation before Delaunay predicates are trusted.

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

• Batch construction controls for insertion order, deduplication, repair cadence, and deterministic retries.
• Complete set of bistellar flip / Pachner moves through D=5 via the Edit API, plus bounded Delaunay repair.
• Configurable predicate kernels: AdaptiveKernel by default, RobustKernel for exact degeneracy-preserving predicates, and FastKernel for well-conditioned exploratory work.
• D-dimensional Convex hulls and Delaunay triangulations.
• Euclidean and toroidal construction through DelaunayTriangulationBuilder: .toroidal(...) builds the periodic image-point quotient in validated dimensions, while .canonicalized_toroidal(...) wraps coordinates without quotient rewiring.
• Exact predicates, stack-allocated linear algebra through la-stack, and deterministic SoS degeneracy handling.
• Focused public preludes for common construction, query, geometry, repair, topology, and diagnostic workflows.
• Geometry measures and simplex quality metrics such as simplex volume, inradius, radius ratio, and normalized volume, plus Jaccard set-similarity diagnostics.
• Incremental insertion, insertion statistics, and transactional remove_vertex rollback on failed repair/canonicalization.
• Optional Cargo feature gates for allocation counting, diagnostics, benchmark logging, and slow correctness tests.
• PL-manifold validation by default, with pseudomanifold checks available as an explicit opt-out.
• Safe Rust: #![forbid(unsafe_code)].
• Serialization/deserialization through JSON.
• Vertex/simplex payloads plus secondary maps for caller-owned algorithm state.

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

For ordinary point-cloud construction, start with one of two common entry points:

• DelaunayTriangulationBuilder - primary construction interface for common and advanced configuration.
• DelaunayTriangulation::new(&vertices) - convenience constructor.

Add the library to your crate:

cargo add delaunay

Examples prefer focused preludes so imports document intent. For the full prelude map and namespace policy, see the Focused Prelude Reference.

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(())
}

For coordinate wrapping on a toroidal domain, use DelaunayTriangulationBuilder::canonicalized_toroidal:

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)
        .canonicalized_toroidal([1.0, 1.0])
        .build::<()>()?;

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

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

• 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.
• Insertion outcomes and statistics (insert_with_statistics, insert_best_effort_with_statistics, InsertionOutcome, InsertionStatistics): see docs/workflows.md and docs/numerical_robustness_guide.md.
• Release benchmark summaries: see benches/README.md and benches/PERFORMANCE_RESULTS.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.
• Topology guarantees (TopologyGuarantee) and automatic topology validation (ValidationPolicy): see docs/validation.md and docs/topology.md.

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.

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

• ConstructionOptions for repair cadence and batch-construction behavior.
• DedupPolicy for preprocessing duplicate coordinates.
• InsertionOrderStrategy for Hilbert ordering or caller-provided input order.
• RetryPolicy for deterministic retry behavior.
• TopologyGuarantee and ValidationPolicy for topology/validation policy.

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

• 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.
• 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.
• Feature gaps: Constrained Delaunay triangulations, Voronoi diagrams, built-in visualization, GPU/parallel meshing, and out-of-core construction are out of scope today.
• Large 4D+ batches: just debug-large-scale-4d 900 1 is the current release-mode acceptance harness; the documented 2026-05-14 local run inserted all 900 vertices, skipped none, and passed validation_report in about 60 seconds. The 3,000-point 4D harness remains a manual characterization probe for issue #340 rather than routine CI.
• Periodic domains: .toroidal() uses the periodic image-point method and is release-validated in 2D and compact 3D. .canonicalized_toroidal() canonicalizes coordinates into the fundamental domain without quotient rewiring. 4D/5D periodic quotients fail fast pending scalable construction work in issue #416.
• Validation/repair guarantees assume the library-managed construction/editing pipeline.

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

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

We welcome contributions. Start with the contributor guide, then use just for the common local workflows:

git clone https://github.com/acgetchell/delaunay.git
cd delaunay
cargo install --locked just
just setup
just help-workflows
just check
just test

See CONTRIBUTING.md for development setup, testing, benchmarks, style, and pull-request guidance. Run just ci before opening or updating a pull request.

just examples
cargo run --release --example delaunayize_repair
cargo run --release --example triangulation_and_hull

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 sample output and usage notes for each example, see examples/README.md.

• 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
• Limitations and Scope - Supported dimensions, predicate limits, and feature gaps
• 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)
• 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)

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.

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

AI coding assistants should read AGENTS.md before proposing or applying changes. See CONTRIBUTING.md for the repository's AI-assisted development note.