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 constructed with a PL-manifold (default) or pseudomanifold guarantee on finite point sets. Euclidean construction is explicitly tested in 2D through 5D, periodic toroidal construction is validated on T² and for compact T³ inputs, and bounded spherical S²/S³ construction is available as a prototype. 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 5-level validation hierarchy on individual elements, combinatorial consistency, intrinsic PL topology, valid realization in the active model, and geometric predicates such as Delaunay. 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.
• Valid-realization checks for Euclidean, toroidal, and spherical models independent of Delaunay predicates.
• 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, combinatorial, intrinsic topology, realization, and geometric-predicate 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 construction and periodic T^2/T^3 image-point quotients through DelaunayTriangulationBuilder.
• 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 delete_vertex rollback on failed repair/canonicalization.
• JSON-exportable simplicial-complex primitives with stable vertex/simplex UUIDs for notebooks and downstream analysis tools.
• Jupyter notebook interface for quickstart visualization, generated JSON artifacts, and README hero image reproduction.
• 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.
• Prototype spherical S^2/S^3 construction through SphericalDelaunayBuilder, with Level 3 Intrinsic PL Topology, spherical Level 4 realization checks, and spherical Level 5 empty-cap predicate checks.
• Safe Rust: #![forbid(unsafe_code)].
• Serialization/deserialization through JSON.
• Topology-aware simplex barycenters for local-editing workflows, including periodic image-point lifting and canonicalization.
• 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

Choose the path that matches your use case:

• Consume the crate as a Rust library when your application needs D-dimensional Delaunay triangulations, convex hulls, validation, or local-editing APIs.
• Use the repository notebook and binary workflow when you want to generate JSON or PNG artifacts, reproduce the README image, or explore larger point clouds interactively.

Rust library

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.97.0 or newer. The minimum supported version is declared in Cargo.toml, while rust-toolchain.toml pins the exact repository toolchain.
• 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);
    dt.validate()?;
    Ok(())
}

For runnable Rust workflows spanning toroidal and spherical construction, auxiliary data, serialization, insertion statistics, deletion, queries, quality metrics, and explicit flips, see the examples/ coverage index.

Notebook and binary

From a repository checkout, start with the notebook-first workflow:

just notebook-setup
just notebook

just notebook-setup installs the uv-managed notebook dependency group, and just notebook launches JupyterLab with notebooks/00_quickstart.ipynb. The notebook uses the opt-in delaunay binary as the engine, loads generic simplicial-complex visualization and convex-hull JSON, and writes a transparent preview under target/notebooks/00_quickstart/. The notebook and just run recipes enable the Cargo cli feature, which pulls in the binary and notebook-support dependencies; ordinary library builds do not need them. The reviewer artifact guide and paper-claim mapping consume this visual-inspection workflow without duplicating its implementation. For validation-layer failure visuals, open notebooks/01_validation.ipynb; it runs delaunay validation-demo and renders generated validation figures for docs and papers. The tracked spherical hero is generated from the real S² prototype by notebooks/02_spherical_hero.ipynb. Refresh it deliberately with just spherical-readme-hero; routine notebook checks only lint this computational artifact.

For headless CI or batch execution, use:

just notebook-execute

Use the binary directly when you want a scriptable artifact run:

just run generate visualization \
  --dimension 3 --vertices 1000 --distribution ball --seed 873 \
  --output target/notebooks/00_quickstart/visualization_3d.json

Before committing edited notebooks, clear generated outputs and execution counts:

just notebook-clear-outputs-all

🧪 Scientific Basis

The crate treats a finite point-set triangulation as an oriented abstract simplicial complex plus a coordinate realization in a supported geometric model. Level 1 certifies element validity, including coordinate storage and local coordinate invariants. Levels 2-3 certify combinatorial consistency and intrinsic PL topology without depending on coordinates: Level 2 checks coherent stored simplex orderings, while Level 3 independently certifies intrinsic orientability for supported 2D/3D PL-manifold guarantees, including periodic quotient constraints. Level 4 certifies geometric validity: Euclidean/toroidal affine-chart maximal simplices must be positively oriented and nondegenerate, and their realizations may intersect only in shared abstract faces. The bounded spherical prototype separately certifies model-specific simplex nondegeneracy in S^D \subset R^(D+1). Level 5 certifies geometric optimality or predicate satisfaction, currently the Delaunay empty-circumsphere property.

Correctness evidence comes from the invariant model, exact predicate fallbacks, deterministic Simulation of Simplicity, validation reports, property tests, regression tests, and public examples. Performance evidence is separate: Hilbert ordering, allocation-conscious data structures, validation-level benchmarks, math-kernel benchmarks, and release-to-release Criterion reports characterize cost and observability, but they do not replace correctness checks.

The crate guarantees the implemented finite-dimensional Delaunay, topology, and validation contracts for the documented coordinate models and dimensions. It does not replace constrained meshing packages, prove arbitrary abstract PL-manifolds realizable from coordinates, or certify unsupported spherical/hyperbolic workflows.

For the detailed contract, see docs/validation.md, docs/invariants.md, docs/topology.md, docs/numerical_robustness_guide.md, docs/limitations.md, and benches/README.md.

✅ Validation Model

Level	Validates	Primary API
1	Element Validity: vertex, simplex, facet, coordinate, and local-object invariants	is_valid() / element reports
2	Combinatorial Consistency: TDS incidence, adjacency, indexes, and stored orientation	is_valid_structure() / structure_report()
3	Intrinsic PL Topology: manifold links, components, Euler consistency, and orientability	is_valid_topology() / topology_report()
4	Valid Realization: affine-chart validity or bounded spherical simplex nondegeneracy, by backend	is_valid_realization() / realization_report()
5	Geometric Predicates: Delaunay and future geometry-specific optimality predicates	is_valid_delaunay() / delaunay_report()
1-5	Cumulative diagnostics	dt.validate() / dt.validation_report()

TopologyGuarantee controls which Level 3 Intrinsic PL Topology invariants are enforced. ValidationPolicy controls when Level 3 checks run during incremental insertion. Level 4 realization validation is backend-specific: Euclidean and toroidal paths validate affine-chart realizations, with toroidal checks lifted to periodic covering-space charts, while the spherical prototype validates simplices on S^D \subset R^(D+1). Level 5 geometric predicates are likewise backend-specific: Euclidean/toroidal Delaunay paths use empty-circumsphere predicates, while the spherical prototype uses the empty-cap / ambient-hull-facet predicate. Use dt.as_triangulation().validate_realization() when you want cumulative Levels 1-4 validation for ordinary triangulations. dt.as_triangulation().realization_report() returns simplex keys, simplex UUIDs, and offending vertex keys/UUIDs for Level 4 repair planning. The default is PL-manifold topology with explicit full-validation checkpoints. Layer-local APIs use is_valid() for unambiguous element/TDS owners, is_valid_* for higher-level fast-fail checks, and *_diagnostic / *_report for diagnostics; cumulative APIs use validate() / validation_report(). orientation_witness() exposes the supported 2D/3D Level 3 orientability certificate directly.

For generated failure pictures, public test anchors, and diagnostics for each layer, run notebooks/01_validation.ipynb. For the paper-facing mathematical exposition, see papers/validation.tex and the compiled reviewer copy at papers/validation.pdf.

🗺️ Documentation Map

• Artifact Guide - v0.8.0 reviewer reproduction paths, claim map, evidence, and limits.
• API Design - construction, vertex lifecycle, and explicit Pachner moves.
• Benchmarks - Criterion suites, perf-profile workflow, release summaries, and canary sizes.
• Code Organization - Architecture hub with links to module maps, focused preludes, and file layout.
• Diagnostics - Structured reports, telemetry, and debug switches.
• Examples and Notebooks - Coverage map for runnable Rust workflows and visual computational artifacts.
• Invariants - Topological and geometric invariants enforced by the crate.
• Limitations - Supported dimensions, predicate limits, toroidal modes, and feature gaps.
• Mesh Export - Stable UUID-based simplicial-complex export for notebooks and downstream tools.
• 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 Intrinsic PL Topology validation, orientability, and global topology models.
• Validation Guide - Validation hierarchy and policy configuration.
• Validation Paper - Reviewer-facing PDF for the validation architecture.
• 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.

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

Benchmarking follows the same invariant-first model as the rest of the crate: first confirm the measured workflow maintains the scientific invariants, then compare same-machine performance, then publish curated release evidence. A fast run that violates triangulation, predicate, topology, or diagnostic invariants is a failed run, not a performance improvement.

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.

.try_toroidal([..]) builds a periodic quotient through the image-point method. It is validated on T^2 and compact T^3, while T^4/T^5 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, full spherical integration beyond the bounded S^2/S^3 prototype, and 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.

---