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.

Security checks include source analysis, Rust and Python dependency audits, secret scanning, and GitHub Actions security analysis. See SECURITY.md for supported versions and private vulnerability reporting.

Contents

• Introduction
• Use this crate for
• API at a glance
• Quickstart
• Features
• Scientific Basis
• Validation Model
• Documentation Map
• Ecosystem
• Benchmarking
• Limitations and Roadmap
• Project History
• Contributing
• Citation
• References
• AI Agents
• 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 for

• 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.
• General triangulations with validated geometry and topology independent of the Delaunay property.
• Typed construction, insertion, validation, topology, and repair diagnostics.
• Valid-realization checks for Euclidean, toroidal, and spherical models independent of Delaunay predicates.
• 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.

API at a glance

The public API separates three owners: Tds validates elements and connectivity through Levels 1–2, Triangulation adds topology and realization through Levels 3–4, and DelaunayTriangulation adds the Level 5 Delaunay contract. Use Triangulation for general geometric editing and DelaunayTriangulation when operations must preserve the Delaunay property.

Use these public entry points with the linked recipes and runnable examples. The full import selector stays in the API documentation. Here, dt is a DelaunayTriangulation and tri is a Triangulation.

Toroidal construction covers T^2 and compact T^3; spherical construction is a bounded S^2/S^3 prototype. These library workflows use default features. The diagnostics example requires diagnostics; the notebook/binary workflow below requires cli. Checkpoint contracts describe versioned persistence; dt.to_visualization_data() creates a detached export.

Use build_triangulation() when construction should stop at Levels 1–4, or build() for a Delaunay result. For Pachner editing, consume a Delaunay owner with into_triangulation(), edit the Triangulation, and use DelaunayRefinementBuilder to certify or repair Level 5 afterward. Point location and general vertex editing have geometry-specific restrictions; see scope and limitations before choosing a model or operation.

🚀 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

• Rust 1.99.1 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, follow prerequisite setup, then discover every command and run the Rust examples:

just
just examples

For interactive exploration:

just notebook-setup
just notebook

just notebook-setup installs the uv-managed notebook dependency group, and just notebook launches JupyterLab at the repository root. Open 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 spherical hero comes from the real S² prototype in notebooks/02_spherical_hero.ipynb.

For headless 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

JSON file output replaces the destination atomically after serialization and flush succeed, preserving an existing file on failure. Destination symlinks and non-regular files are rejected; symlinked parent directories are supported. JSON written to stdout and progress CSV output continue to stream directly.

✨ Features

• Batch construction controls for insertion order, deduplication, repair cadence, and deterministic retries.
• Complete set of bistellar flip / Pachner moves through D=5 on Triangulation, plus bounded Delaunay repair.
• Configurable predicate kernels: AdaptiveKernel by default for deterministic SoS tie-breaking, RobustKernel for exact diagnostics and higher-dimensional fallbacks, and FastKernel for a lean filtered-exact path that preserves degeneracy signals through D ≤ 6.
• 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.
• General Triangulation construction, queries, Euclidean vertex editing, and persistence through Levels 1–4, with explicit refinement to a DelaunayTriangulation when Level 5 is required.
• 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.

🧪 Scientific Basis

The crate separates the abstract simplicial complex, its coordinate realization, and the Delaunay predicate contract through the five validation levels below. The scientific basis overview connects API selection, supported geometric models, numerical assumptions, and methods to their sources. It also distinguishes correctness evidence from performance measurements.

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

✅ Validation Model

TopologyGuarantee controls which Level 3 Intrinsic PL Topology invariants are enforced. ValidationPolicy controls when cumulative Levels 1–4 audits 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 the manuscript source and reviewer PDF in acgetchell/Papers.

🗺️ Documentation Map

• API Design - construction, vertex lifecycle, and explicit Pachner moves.
• Artifact Guide - v0.8.0 reviewer reproduction paths, claim map, evidence, and limits.
• 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.
• Construction and Validation Guide - Proof-bearing construction, validation hierarchy, and policy configuration.
• Construction and Validation Paper - Reviewer-facing architecture paper.
• 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.
• Performance Report - Legacy release-to-release benchmark evidence without a retained artifact bundle.
• Property Testing Summary - Property-test layout and coverage summary.
• Releasing - Changelog, benchmark, and publish workflow.
• Roadmap - Current release preparation, ongoing work, and future candidates.
• Scientific Basis - API selection, scientific scope, assumptions, methods, and supporting sources.
• Topology - Level 3 Intrinsic PL Topology validation, orientability, and global topology models.
• Workflows - Practical recipes for construction, repair, toroidal domains, payloads, and flips.

Within this crate, src/core/tds/ owns the checked TDS, src/triangulation/ owns general triangulations and topology editing, and src/delaunay/ owns Delaunay construction, refinement, and maintenance. src/geometry/ supplies predicates and geometric helpers; src/topology/ supplies topology models and checks. See Code Organization for the ownership map.

🧩 Ecosystem

delaunay is part of a Rust research ecosystem with public libraries and shared development tooling:

• causal-triangulations - downstream CDT research crate built on Delaunay-backed geometry primitives.
• la-stack - stack-allocated linear algebra, exact rational determinants, and exact linear solves.
• markov-chain-monte-carlo - composable Metropolis-Hastings sampling and proposal interfaces.
• research-repo-tools - shared Python tooling for development, validation, and releases.

📈 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.

See CONTRIBUTING.md for local validation and CI checks.

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

just performance-local  # Fresh current/baseline comparison

# Or measure absolute performance, then render without measuring again:
just bench-latest
just bench-perf-summary

See the legacy docs/performance.md report for historical, provenance-limited release evidence and benches/README.md for benchmark selection, fixture sizes, baseline workflows, and large-scale profiling guidance.

Release PRs publish a compact group-level snapshot from the validated retained .comparison.json/.evidence.json bundle. The geometric-mean ratios are descriptive summaries; the generated full report retains every benchmark result represented in that bundle.

No retained release-comparison bundle has been published to the README yet.

🛣️ Limitations and Roadmap

Caller-facing coordinates are finite f64. Built-in exact predicates and complete SoS tie-breaking support D ≤ 6; higher-dimensional robust fallbacks do not extend the ExactPredicates construction contract. See the Numerical Robustness Guide for filter and fallback details.

Point location currently requires Euclidean geometry. General Triangulation vertex insertion and deletion are also Euclidean; periodic edits use chart-bound Pachner proposals. The toroidal builder canonicalizes coordinates and applies deterministic perturbations of at most approximately 2^-32 of each domain period, preserving vertex UUIDs and payloads.

Construction is single-threaded and in-memory. Constrained Delaunay triangulations, direct Voronoi extraction, concurrent topology mutation, GPU/out-of-core construction, full spherical integration, and hyperbolic triangulation semantics remain future work. Notebook visualization and JSON export are available; a native Rust plotting or viewer layer is not provided.

See docs/limitations.md for operational limits and docs/roadmap.md for current follow-up work and later feature tracks.

🚧 Project History

This crate was originally maintained in oovm/shape-rs through version 0.1.0.

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

🤝 Contributing

See CONTRIBUTING.md for prerequisite setup, checks, fixes, tests, security scans, PR preparation, documentation, benchmarking, and release support. Community expectations live in CODE_OF_CONDUCT.md. AI assistants should follow AGENTS.md.

📚 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 Agents

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

📜 License

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