delaunay

D-dimensional Delaunay triangulations and convex hulls in Rust, with exact predicates, deterministic degeneracy handling, explicit topology validation, and bistellar flips for finite point sets.

Contents

• Introduction
• Features
• Quickstart
• Scientific Basis
• Validation Model
• Documentation Map
• Ecosystem
• Benchmarking
• Limitations and Roadmap
• Contributing
• Citation
• References
• AI-assisted Development
• License

📐 Introduction

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.

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.
• Typed construction, insertion, validation, topology, and repair diagnostics.
• Validation reports that separate element, structure, topology, and Delaunay failures.

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

✨ Features

• 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: .try_toroidal(...) builds the periodic image-point quotient in validated dimensions, while .try_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 history and docs/roadmap.md for current direction, near-term candidates, and non-goals.

🚀 Quickstart

Add the crate to your project:

cargo add delaunay@0.7.8

Use cargo add delaunay instead if you want Cargo to select the newest published release.

• Rust 1.96.0 or newer, pinned by Cargo.toml and rust-toolchain.toml.
• f64 coordinates for caller-facing construction, predicate, validation, and generator APIs.

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

fn main() -> DelaunayResult<()> {
    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::<()>()?;

    assert_eq!(dt.dim(), 3);
    assert_eq!(dt.number_of_vertices(), 4);
    assert!(dt.validate().is_ok());
    Ok(())
}

For toroidal domains, auxiliary vertex/simplex data, insertion statistics, vertex removal, and explicit flips, see docs/workflows.md.

🧪 Scientific Basis

The crate models triangulations as oriented simplicial complexes with separate combinatorial and geometric checks. Robustness comes from the same layered predicate strategy used throughout the code: fast f64 filters when the sign is provable, exact arithmetic fallback when it is not, and deterministic SoS resolution for degenerate configurations.

The validation contract is computational and finite-dimensional. The crate checks that constructed or edited triangulations satisfy implemented element, topology, and Delaunay invariants; it does not claim to solve meshing constraints or certify unsupported geometric models.

For the detailed contract, see REFERENCES.md, docs/invariants.md, and docs/numerical_robustness_guide.md.

✅ Validation Model

Level	Validates	Primary API
1	Vertex, simplex, and facet element invariants	vertex.is_valid() / simplex.is_valid()
2	TDS keys, incidences, and neighbor links	dt.tds().is_valid()
3	Manifold topology, ridge links, and Euler consistency	dt.as_triangulation().is_valid()
4	Delaunay property via local predicates	dt.is_valid()
1-4	Cumulative diagnostics	dt.validate() / dt.validation_report()

TopologyGuarantee controls which Level 3 topology invariants are enforced. ValidationPolicy controls when Level 3 checks run during incremental insertion. The default is PL-manifold topology with explicit full-validation checkpoints.

🗺️ Documentation Map

• API Design - Builder vs Edit APIs and explicit bistellar flips.
• Benchmarks - Criterion suites, perf-profile workflow, release summaries, and canary sizes.
• Code Organization - Module layout, focused preludes, and contributor orientation.
• Diagnostics - Structured reports, telemetry, and debug switches.
• Examples - Runnable examples for construction, hulls, topology editing, diagnostics, and repair.
• Invariants - Topological and geometric invariants enforced by the crate.
• Limitations - Supported dimensions, predicate limits, toroidal modes, and feature gaps.
• Numerical Robustness Guide - Predicate kernels, SoS, retry, and repair behavior.
• Orientation Spec - Coherent combinatorial and geometric orientation rules.
• Property Testing Summary - Property-test layout and coverage summary.
• Releasing - Changelog, benchmark, and publish workflow.
• Roadmap - Current release sequence and deferred feature tracks.
• Topology - Level 3 topology validation and global topology models.
• Validation Guide - Validation hierarchy and policy configuration.
• Workflows - Practical recipes for construction, repair, toroidal domains, payloads, and flips.

🧩 Ecosystem

delaunay sits in a small Rust research stack:

• la-stack - stack-allocated linear algebra and exact determinant support.
• causal-triangulations - downstream CDT research crate built on Delaunay-backed geometry primitives.
• markov-chain-monte-carlo - composable MCMC traits used by the broader simulation ecosystem.

Within this crate, src/core/ owns the topology data structures, src/geometry/ owns predicates and geometric helpers, src/delaunay/ owns user-facing construction/query/repair APIs, and src/topology/ owns topology spaces and validation.

📈 Benchmarking

Correctness validation and performance measurement are separate workflows. For ordinary local validation:

just check
just test
just examples

For full CI parity:

just ci

Performance-sensitive work uses Criterion suites and same-machine baselines:

just perf-no-regressions
just bench-ci
just bench-perf-summary

See benches/README.md for benchmark selection, fixture sizes, release baselines, and large-scale profiling guidance.

🛣️ Limitations and Roadmap

Current routine coverage targets 2D through 5D. 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 determinant exceeds the current stack-matrix limit.

Toroidal support has two modes:

• .try_canonicalized_toroidal([..]) wraps coordinates into the fundamental domain before Euclidean construction.
• .try_toroidal([..]) builds a true periodic quotient through the image-point method; it is validated in 2D and compact 3D, while 4D/5D fail fast pending scalable quotient work.

Not implemented today: constrained Delaunay triangulations, Voronoi diagram extraction, built-in visualization, massively parallel/GPU construction, out-of-core meshing, and full spherical or hyperbolic triangulation semantics.

See docs/limitations.md for operational limits and docs/roadmap.md for the v0.8.0 paper-facing API/topology push and later feature tracks.

🤝 Contributing

See CONTRIBUTING.md for the full contributor guide: project layout, development workflow, code style, testing, documentation, benchmarking, and release support. Community expectations live in CODE_OF_CONDUCT.md. AI assistants should follow AGENTS.md.

Quick local workflow:

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

For the full command list, run just --list.

📚 Citation

If you use this software in academic work or downstream research software, 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 such as version, release date, and ORCID, prefer CITATION.cff.

🔎 References

For academic references and bibliographic citations used throughout the library, see REFERENCES.md.

This includes foundational work on:

• Delaunay triangulations and convex hulls.
• Robust geometric predicates and exact arithmetic.
• Simulation of Simplicity.
• PL-manifold topology and Pachner moves.

🤖 AI-assisted Development

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

Portions of this library were developed with the assistance of AI tools including ChatGPT, Claude, Codex, and CodeRabbit. All accepted code and documentation changes are reviewed, edited, and validated by the author.

For tool citation metadata, see the AI-assisted development tools section of REFERENCES.md.

📜 License

This project is licensed under the BSD 3-Clause License.

---