# delaunay
[](https://doi.org/10.5281/zenodo.16931097)
[](https://crates.io/crates/delaunay)
[](https://crates.io/crates/delaunay)
[](https://github.com/acgetchell/delaunay/blob/main/LICENSE)
[](https://docs.rs/delaunay)
[![CI][ci-badge]][ci-workflow]
[![CodeQL][codeql-badge]][codeql-workflow]
[![rust-clippy analyze][clippy-badge]][clippy-workflow]
[](https://codecov.io/gh/acgetchell/delaunay)
[![Audit dependencies][audit-badge]][audit-workflow]
[![Codacy Badge][codacy-badge]][codacy-dashboard]
D-dimensional [Delaunay triangulations] and [convex hulls][Convex hulls] in [Rust], with exact predicates,
deterministic degeneracy handling, explicit topology validation, and bistellar flips for finite point sets.
![S² Delaunay triangulation with 160 points][readme-hero]
## Contents
- [Introduction](#-introduction)
- [Features](#-features)
- [Quickstart](#-quickstart)
- [Scientific Basis](#-scientific-basis)
- [Validation Model](#-validation-model)
- [Documentation Map](#-documentation-map)
- [Ecosystem](#-ecosystem)
- [Benchmarking](#-benchmarking)
- [Limitations and Roadmap](#-limitations-and-roadmap)
- [Contributing](#-contributing)
- [Citation](#-citation)
- [References](#-references)
- [AI-assisted Development](#-ai-assisted-development)
- [License](#-license)
## 📐 Introduction
Rust crate providing D-dimensional [Delaunay triangulations] and [convex hulls][Convex hulls]
constructed with a [PL-manifold] (default) or [pseudomanifold][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 curve]s for deterministic insertion ordering and efficient spatial indexing.
Provides an explicit [5-level validation hierarchy][Validation Guide] 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][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
- [x] Batch construction controls for insertion order, deduplication, repair cadence, and deterministic
retries.
- [x] Complete set of bistellar flip / [Pachner moves] through D=5 via the Edit API, plus bounded
Delaunay repair.
- [x] Configurable predicate kernels: `AdaptiveKernel` by default, `RobustKernel` for exact
degeneracy-preserving predicates, and `FastKernel` for well-conditioned exploratory work.
- [x] D-dimensional [Convex hulls] and [Delaunay triangulations].
- [x] Euclidean construction and periodic `T^2`/`T^3` image-point quotients through
`DelaunayTriangulationBuilder`.
- [x] Exact predicates, stack-allocated linear algebra through [la-stack], and deterministic SoS
degeneracy handling.
- [x] Focused public preludes for common construction, query, geometry, repair, topology, and diagnostic
workflows.
- [x] Geometry measures and simplex quality metrics such as simplex volume, inradius, radius ratio, and
normalized volume, plus Jaccard set-similarity diagnostics.
- [x] Incremental insertion, insertion statistics, and transactional `delete_vertex` rollback on failed
repair/canonicalization.
- [x] JSON-exportable simplicial-complex primitives with stable vertex/simplex UUIDs for notebooks and
downstream analysis tools.
- [x] [Jupyter] notebook interface for quickstart visualization, generated JSON artifacts, and README
hero image reproduction.
- [x] Optional Cargo feature gates for allocation counting, diagnostics, benchmark logging, and slow
correctness tests.
- [x] PL-manifold validation by default, with pseudomanifold checks available as an explicit opt-out.
- [x] 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.
- [x] Safe Rust: `#![forbid(unsafe_code)]`.
- [x] Serialization/deserialization through [JSON].
- [x] Topology-aware simplex barycenters for local-editing workflows, including periodic image-point
lifting and canonicalization.
- [x] Vertex/simplex payloads plus secondary maps for caller-owned algorithm state.
See [CHANGELOG.md](CHANGELOG.md) for release history and [`docs/roadmap.md`](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:
```bash
cargo add delaunay@0.8.0
```
Use `cargo add delaunay` instead if you want Cargo to select the newest published release.
- Rust 1.97.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.
```rust
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](examples/README.md).
### Notebook and binary
From a repository checkout, start with the notebook-first workflow:
```bash
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`](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](papers/ARTIFACT.md) and paper-claim mapping consume
this visual-inspection workflow without duplicating its implementation.
For validation-layer failure visuals, open
[`notebooks/01_validation.ipynb`](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`](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:
```bash
just notebook-execute
```
Use the binary directly when you want a scriptable artifact run:
```bash
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:
```bash
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/validation.md),
[`docs/invariants.md`](docs/invariants.md), [`docs/topology.md`](docs/topology.md),
[`docs/numerical_robustness_guide.md`](docs/numerical_robustness_guide.md),
[`docs/limitations.md`](docs/limitations.md), and [`benches/README.md`](benches/README.md).
## ✅ Validation Model
| 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`](notebooks/01_validation.ipynb). For the paper-facing mathematical
exposition, see [`papers/validation.tex`](papers/validation.tex) and the compiled reviewer copy at
[`papers/validation.pdf`](papers/validation.pdf).
## 🗺️ Documentation Map
- [Artifact Guide](papers/ARTIFACT.md) - v0.8.0 reviewer reproduction paths, claim map, evidence, and limits.
- [API Design](docs/api_design.md) - construction, vertex lifecycle, and explicit Pachner moves.
- [Benchmarks](benches/README.md) - Criterion suites, perf-profile workflow, release summaries, and canary sizes.
- [Code Organization](docs/code_organization.md) - Architecture hub with links to module maps, focused preludes, and file layout.
- [Diagnostics](docs/diagnostics.md) - Structured reports, telemetry, and debug switches.
- [Examples and Notebooks](examples/README.md) - Coverage map for runnable Rust workflows and visual computational artifacts.
- [Invariants](docs/invariants.md) - Topological and geometric invariants enforced by the crate.
- [Limitations](docs/limitations.md) - Supported dimensions, predicate limits, toroidal modes, and feature gaps.
- [Mesh Export](docs/mesh_export.md) - Stable UUID-based simplicial-complex export for notebooks and downstream tools.
- [Numerical Robustness Guide](docs/numerical_robustness_guide.md) - Predicate kernels, SoS, retry, and repair behavior.
- [Orientation Spec](docs/ORIENTATION_SPEC.md) - Coherent combinatorial and geometric orientation rules.
- [Property Testing Summary](docs/property_testing_summary.md) - Property-test layout and coverage summary.
- [Releasing](docs/RELEASING.md) - Changelog, benchmark, and publish workflow.
- [Roadmap](docs/roadmap.md) - Current release sequence and deferred feature tracks.
- [Topology](docs/topology.md) - Level 3 Intrinsic PL Topology validation, orientability, and global topology models.
- [Validation Guide](docs/validation.md) - Validation hierarchy and policy configuration.
- [Validation Paper](papers/validation.pdf) - Reviewer-facing PDF for the validation architecture.
- [Workflows](docs/workflows.md) - Practical recipes for construction, repair, toroidal domains, payloads, and flips.
## 🧩 Ecosystem
`delaunay` sits in a small Rust research stack:
- [`la-stack`](https://crates.io/crates/la-stack) - stack-allocated linear algebra and exact determinant support.
- [`causal-triangulations`](https://crates.io/crates/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:
```bash
just check
just test
just examples
```
For full CI parity:
```bash
just ci
```
Performance-sensitive work uses Criterion suites and same-machine baselines:
```bash
just perf-no-regressions
just bench-ci
just bench-perf-summary
```
See [`benches/README.md`](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, the determinant exceeds the current stack-matrix limit,
so classification first uses a floating-point circumcenter/radius distance predicate and applies
symbolic perturbation only to boundary or failed distance evaluations. Near-degenerate D≥6 inputs
therefore do not have exact-sign protection.
`.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`](docs/limitations.md) for operational limits and [`docs/roadmap.md`](docs/roadmap.md)
for the v0.8.0 paper-facing API/topology push and later feature tracks.
## 🤝 Contributing
See [CONTRIBUTING.md](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](CODE_OF_CONDUCT.md). AI assistants should follow [AGENTS.md](AGENTS.md).
Quick local workflow:
```bash
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](CITATION.cff).
- DOI: <https://doi.org/10.5281/zenodo.16931097>
- Citation metadata: [CITATION.cff](CITATION.cff)
```bibtex
@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](CITATION.cff).
## 🔎 References
For academic references and bibliographic citations used throughout the library, see [REFERENCES.md](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](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](REFERENCES.md#ai-assisted-development-tools)
section of [REFERENCES.md](REFERENCES.md).
## 📜 License
This project is licensed under the [BSD 3-Clause License](https://github.com/acgetchell/delaunay/blob/main/LICENSE).
---
[Rust]: https://rust-lang.org
[audit-badge]: https://github.com/acgetchell/delaunay/actions/workflows/audit.yml/badge.svg
[audit-workflow]: https://github.com/acgetchell/delaunay/actions/workflows/audit.yml
[ci-badge]: https://github.com/acgetchell/delaunay/actions/workflows/ci.yml/badge.svg
[ci-workflow]: https://github.com/acgetchell/delaunay/actions/workflows/ci.yml
[clippy-badge]: https://github.com/acgetchell/delaunay/actions/workflows/rust-clippy.yml/badge.svg
[clippy-workflow]: https://github.com/acgetchell/delaunay/actions/workflows/rust-clippy.yml
[codacy-badge]: https://app.codacy.com/project/badge/Grade/3cad94f994f5434d877ae77f0daee692
[codacy-dashboard]: https://app.codacy.com/gh/acgetchell/delaunay/dashboard?utm_source=gh&utm_medium=referral&utm_content=&utm_campaign=Badge_grade
[codeql-badge]: https://github.com/acgetchell/delaunay/actions/workflows/codeql.yml/badge.svg
[codeql-workflow]: https://github.com/acgetchell/delaunay/actions/workflows/codeql.yml
[CGAL]: https://www.cgal.org/
[ChatGPT]: https://openai.com/chatgpt
[Claude]: https://www.anthropic.com/claude
[CodeRabbit]: https://coderabbit.ai/
[Codex]: https://openai.com/codex
[Convex hulls]: https://en.wikipedia.org/wiki/Convex_hull
[Delaunay triangulations]: https://en.wikipedia.org/wiki/Delaunay_triangulation
[exact predicates]: docs/numerical_robustness_guide.md
[Hilbert curve]: https://en.wikipedia.org/wiki/Hilbert_curve
[Jupyter]: https://jupyter.org/
[JSON]: https://www.json.org/json-en.html
[la-stack]: https://crates.io/crates/la-stack
[Pachner moves]: https://en.wikipedia.org/wiki/Pachner_move
[PL-manifold]: https://en.wikipedia.org/wiki/Piecewise_linear_manifold
[Pseudomanifold]: https://en.wikipedia.org/wiki/Pseudomanifold
[readme-hero]: https://raw.githubusercontent.com/acgetchell/delaunay/main/docs/assets/readme/delaunay_spherical_readme.png
[Secondary maps]: docs/workflows.md#builder-api-auxiliary-vertex-and-simplex-data
[Simulation of Simplicity]: docs/numerical_robustness_guide.md#simulation-of-simplicity-sos
[Validation Guide]: docs/validation.md