Crate delaunay 

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

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

---

---

Documentation map

The README above is included verbatim and serves as the user-facing introduction to the crate (overview, features, and quick-start examples).

Everything below this line specifies the semantic and correctness contract of the delaunay crate and is intended for users who need stronger guarantees, deeper understanding of invariants, or who are extending the implementation.

This crate’s documentation is intentionally layered by audience and intent:

• README.md (included above): User-facing overview, feature list, and quick-start examples.

• Crate-level documentation (lib.rs) (this document): The programming contract of the library: what invariants are enforced, when validation runs, and what errors mean.

  In particular, this document covers:

  • The validation hierarchy and invariant stack (Levels 1–5)
  • Topological guarantees (TopologyGuarantee) and insertion-time validation policy (ValidationPolicy)
  • High-level error semantics and programming contract (transactional operations, duplicate rejection)

• docs/workflows.md: Task-oriented, end-to-end usage recipes (Builder API, Edit API, validation, repairs, diagnostics, and statistics).

• docs/validation.md: Formal definitions of validation Levels 1–5, their costs, and guidance on when each level should be applied.

• docs/diagnostics.md: Opt-in diagnostic helpers, structured reports, debug switches, and guidance for producing useful failure reports without expanding the default API surface.

• docs/invariants.md: Deeper theoretical discussion of topological and geometric invariants (PL-manifold conditions, ridge/vertex links, ordering heuristics, and convergence assumptions), plus algorithmic background and limitations.

Which import do I need?

The crate provides several focused prelude modules. Pick the one that matches your task:

Task	Import
Construct/configure a Delaunay triangulation	use delaunay::prelude::construction::*
Build/validate/repair generic triangulations	use delaunay::prelude::triangulation::*
Incremental insertion diagnostics and result types	use delaunay::prelude::insertion::*
Post-construction vertex deletion errors and keys	use delaunay::prelude::deletion::*
Read-only queries, traversal, ridge views, simplex barycenters, convex hull	use delaunay::prelude::query::*
Point location and conflict-region algorithms	use delaunay::prelude::algorithms::*
Geometry helpers, simplex realizations, coordinate ranges, predicates, points	use delaunay::prelude::geometry::*
Random points / triangulations for examples and tests	use delaunay::prelude::generators::*
Hilbert ordering and quantization utilities	use delaunay::prelude::ordering::*
Unified Pachner move workflow	use delaunay::prelude::pachner::*
Delaunay repair and flip-based Level 5 validation	use delaunay::prelude::repair::*
Delaunayize workflow (repair + flip)	use delaunay::prelude::delaunayize::*
Construction telemetry diagnostics	use delaunay::prelude::diagnostics::*
Export stable mesh and visualization primitives	use delaunay::prelude::export::*
Validation policies, errors, reports, PL-manifold link errors, and Level 5 diagnostics	use delaunay::prelude::validation::*
Topology validation, Euler characteristic, ridge queries	use delaunay::prelude::topology::validation::*
Topological spaces, topology traits, spherical point/metric backends, lifted toroidal IDs	use delaunay::prelude::topology::spaces::*
Low-level TDS simplices, facets, keys	use delaunay::prelude::tds::*
Collection types (FastHashMap, etc.)	use delaunay::prelude::collections::*
Broad convenience import for exploratory code	use delaunay::prelude::*

Public low-level namespace policy

High-level Delaunay APIs are available directly from the crate root and focused root modules: DelaunayTriangulation, DelaunayTriangulationBuilder, construction, flips, repair, validation, and delaunayize. The nested delaunay::delaunay::* facade is intentionally not part of the public API; use the crate root or a focused prelude instead.

use delaunay::delaunay::DelaunayTriangulation;

The low-level implementation namespace is private. The public low-level surface is exposed through curated modules: tds, collections, algorithms, and query, plus the matching focused preludes. These names describe the data structures and workflows users compose without colliding with Rust’s standard core vocabulary.

Prefer these curated modules and focused preludes in examples, doctests, benchmarks, and downstream-style integration tests. High-level Delaunay construction remains outside the low-level TDS/query surface.

Examples (contract-oriented)

Validation hierarchy (Levels 1–5)

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

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()?;

// Levels 1–2: Element Validity + Combinatorial Consistency
assert!(dt.validate_structure().is_ok());

// Levels 1–3: + Intrinsic PL Topology
assert!(dt.as_triangulation().validate().is_ok());

// Levels 1–4: elements + combinatorics + topology + realization validity
assert!(dt.as_triangulation().validate_realization().is_ok());

// Level 5 only: Geometric Predicates (Delaunay today; assumes Levels 1–4)
assert!(dt.is_valid_delaunay().is_ok());

// Levels 1–5: full cumulative validation
assert!(dt.validate().is_ok());

Topology guarantees and insertion-time validation (TopologyGuarantee, ValidationPolicy)

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

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 mut dt = DelaunayTriangulationBuilder::new(&vertices).build()?;

assert_eq!(dt.topology_guarantee(), TopologyGuarantee::PLManifold);
assert_eq!(dt.validation_policy(), ValidationPolicy::ExplicitOnly);

dt.set_topology_guarantee(TopologyGuarantee::Pseudomanifold);
dt.set_validation_policy(ValidationPolicy::Always);

assert_eq!(dt.topology_guarantee(), TopologyGuarantee::Pseudomanifold);
assert_eq!(dt.validation_policy(), ValidationPolicy::Always);

Transactional operations and duplicate rejection

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

let vertices = vec![
    vertex![0.0, 0.0]?,
    vertex![1.0, 0.0]?,
    vertex![0.0, 1.0]?,
];
let mut dt = DelaunayTriangulationBuilder::new(&vertices).build()?;

let before_vertices = dt.number_of_vertices();
let before_simplices = dt.number_of_simplices();

// Duplicate coordinates are rejected.
let result = dt.insert_vertex(vertex![0.0, 0.0]?);
std::assert_matches!(result, Err(InsertionError::DuplicateCoordinates { .. }));

// On error, the triangulation is unchanged.
assert_eq!(dt.number_of_vertices(), before_vertices);
assert_eq!(dt.number_of_simplices(), before_simplices);

Triangulation invariants and validation hierarchy

The crate is organized as a small validation stack, where each layer adds additional invariants on top of the preceding one:

• Vertex and Simplex provide element validity checks. Level 1 (elements) validation checks invariants such as:

  • Vertex coordinates – finite (no NaN/∞) and UUID is non-nil.
  • Simplex shape – exactly D+1 distinct vertex keys, valid UUID, and neighbor buffer length (if present) is D+1.

  These checks are surfaced via Vertex::is_valid, Vertex::vertex_report, Simplex::is_valid, and Simplex::simplex_report, and are automatically run by Tds::validate (Levels 1–2).

• Tds (Triangulation Data Structure) stores the combinatorial representation. Level 2 (Combinatorial Consistency) validation checks invariants such as:

  • Vertex mappings – every vertex UUID has a corresponding key and vice versa.
  • Simplex mappings – every simplex UUID has a corresponding key and vice versa.
  • No duplicate simplices – no two maximal simplices share the same vertex set.
  • Facet incidence – each facet is one-sided or two-sided; topology metadata decides whether a one-sided facet is semantic boundary.
  • Neighbor consistency – neighbor relationships are mutual and reference a shared facet.

  These checks are surfaced via Tds::is_valid (structural only) and Tds::validate (Levels 1–2, elements + combinatorics). For cumulative diagnostics across the full stack, use DelaunayTriangulation::validation_report.

• Triangulation builds on the TDS and validates intrinsic PL topology. Level 3 (Intrinsic PL Topology) validation is performed by Triangulation::is_valid_topology (Level 3 only) and Triangulation::validate (Levels 1–3), which:

  • Strengthens facet incidence to the manifold facet property: one-sided facets are valid only when the declared topology admits boundary; two-sided facets are interior.
  • Checks the Euler characteristic of the triangulation (using the topology module).

• Triangulation also validates the realization validity of the abstract complex in the active ambient model. Level 4 validation is performed by Triangulation::is_valid_realization (Level 4 only) and Triangulation::validate_realization (Levels 1–4). Euclidean topology is checked directly in its ambient chart; toroidal topology is checked in periodic covering-space charts.

• DelaunayTriangulation builds on Triangulation and validates the implemented geometric predicate family for Delaunay triangulations. Level 5 (Geometric Predicates) validation is performed by DelaunayTriangulation::is_valid_delaunay (Level 5 only) and DelaunayTriangulation::validate (Levels 1–5). Batch construction normally runs final Delaunay validation before returning; ConstructionOptions::without_final_delaunay_enforcement opts into returning after Levels 1–4 validation for exact degenerate or externally constrained connectivity. Incremental insertion can run global Level 5 checks according to DelaunayCheckPolicy. If robust fallback and repair cannot certify a checked result, the operation returns a typed error rather than silently accepting a known violation.

Validation

The crate exposes five validation levels (Element Validity → Combinatorial Consistency → Intrinsic PL Topology → Valid Realization → Geometric Predicates). The canonical guide (when to use each level, complexity, examples, troubleshooting) lives in docs/validation.md: https://github.com/acgetchell/delaunay/blob/main/docs/validation.md

In brief:

• Level 1 (elements / Vertex + Simplex): Vertex::is_valid() / Simplex::is_valid() for fast checks, or vertex_report() / simplex_report() for element-local diagnostics.
• Level 2 (Combinatorial Consistency / Tds): dt.is_valid_structure() for a quick check, or dt.validate_structure() for Levels 1–2.
• Level 3 (Intrinsic PL Topology / Triangulation): dt.as_triangulation().is_valid_topology() for topology-only checks, or dt.as_triangulation().validate() for Levels 1–3.
• Level 4 (Valid Realization / Triangulation): dt.as_triangulation().validate_realization() for cumulative realized-geometry checks, or dt.as_triangulation().realization_report() for layer-local diagnostics.
• Level 5 (Geometric Predicates / DelaunayTriangulation): dt.is_valid_delaunay() for the implemented Delaunay predicate family, or dt.delaunay_report() for layer-local diagnostics.
• Cumulative Delaunay validation: dt.validate() for Levels 1–5, or dt.validation_report() for full diagnostics.

Automatic topology and changed-scope realization validation during insertion (ValidationPolicy)

In addition to explicit validation calls, incremental construction (new() / insert*()) can run an automatic global Level 3 plus changed-scope Level 4 validation pass after insertion, controlled by ValidationPolicy.

The initial policy is derived from the active topology guarantee. The default TopologyGuarantee::PLManifold uses ValidationPolicy::ExplicitOnly: mandatory local topology and orientation/nondegeneracy realization checks still run during insertion, while automatic global-topology/changed-scope realization validation is a caller-owned explicit checkpoint.

This automatic pass runs Level 3 (Triangulation::is_valid_topology()), changed-simplex Level 4 orientation/nondegeneracy checks, and changed-vs-current Level 4 pairwise checks. It does not run Level 5 geometric-predicate validation, and old-vs-old Level 4 rescans remain an explicit Triangulation::validate_realization() checkpoint.

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

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 mut dt = DelaunayTriangulationBuilder::new(&vertices).build()?;

// Caller-owned validation mode: keep mandatory topology checks, but run full
// Level 3 validation only through explicit validation calls.
dt.try_set_validation_policy(ValidationPolicy::ExplicitOnly)?;

// Do incremental work...
dt.insert_vertex(vertex![0.2, 0.2, 0.2]?)?;

// ...then explicitly validate the Intrinsic PL Topology layer when you need a certificate.
assert!(dt.as_triangulation().validate().is_ok());

Choosing Level 3 Intrinsic PL Topology guarantee (TopologyGuarantee)

This section specifies what invariants are enforced. The formal topological definitions and rationale live in docs/invariants.md.

Level 3 Intrinsic PL Topology validation is parameterized by TopologyGuarantee. This is separate from ValidationPolicy: it controls what invariants Level 3 enforces, not when automatic validation runs.

• TopologyGuarantee::PLManifold (default): enforces manifold facet degree, boundary closure, connectedness, Euler characteristic, and link-based manifold conditions. Ridge-link checks are applied incrementally during insertion, with vertex-link validation performed at construction completion.

  The formal topological definitions, link conditions, and rationale for this validation strategy are documented in docs/invariants.md.

• TopologyGuarantee::PLManifoldStrict: vertex-link validation after every insertion (slowest, maximum safety).

• TopologyGuarantee::Pseudomanifold: skips vertex-link validation (may be faster), but bistellar flip convergence is not guaranteed and you may want to validate the Delaunay property explicitly for near-degenerate inputs.

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

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()?;

// For `TopologyGuarantee::PLManifold`, full certification includes a completion-time
// vertex-link validation pass.
assert!(dt.as_triangulation().validate_at_completion().is_ok());

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

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()?;

// `validate()` returns the first violation; `validation_report()` is intended for
// debugging/telemetry where you want the full set of violated invariants.
assert!(dt.validation_report().is_ok());

Coordinate scalar policy

The default supported coordinate input type is f64, matching the crate’s current linear algebra backend and geometric-primitive correctness guarantees. Exact arithmetic is already used internally for robust predicate fallbacks, and exact coordinate input may be supported explicitly in the future.

Programming contract (high-level)

• Transactional mutations: Construction and incremental operations are designed to be all-or-nothing. If an operation returns Err(_), the triangulation is rolled back to its previous state.
• Duplicate detection: Near-duplicate coordinates are rejected using a scale-aware Euclidean tolerance based on nearby geometry and floating-point resolution, returning InsertionError::DuplicateCoordinates. Duplicate UUIDs return InsertionError::DuplicateUuid.
• Explicit verification: Use dt.validate() for cumulative verification (Levels 1–5), or dt.is_valid_delaunay() for Level 5 only.

Re-exports

pub use crate::builder::DelaunayTriangulationBuilder;

pub use crate::construction::ConstructionOptions;

pub use crate::construction::ConstructionSkipSample;

pub use crate::construction::ConstructionSlowInsertionSample;

pub use crate::construction::ConstructionStatistics;

pub use crate::construction::DedupPolicy;

pub use crate::construction::DedupTolerance;

pub use crate::construction::DelaunayConstructionFailure;

pub use crate::construction::DelaunayConstructionRepairPhase;

pub use crate::construction::DelaunayConstructionRetryFailure;

pub use crate::construction::DelaunayError;

pub use crate::construction::DelaunayResult;

pub use crate::construction::DelaunayTriangulationConstructionError;

pub use crate::construction::DelaunayTriangulationConstructionErrorWithStatistics;

pub use crate::construction::InitialSimplexStrategy;

pub use crate::construction::InsertionOrderStrategy;

pub use crate::construction::RetryPolicy;

pub use crate::io::visualization::AdjacencyRecord;

pub use crate::io::visualization::MESH_EXPORT_SCHEMA;

pub use crate::io::visualization::MESH_EXPORT_SCHEMA_VERSION;

pub use crate::io::visualization::MeshAdjacencyRecord;

pub use crate::io::visualization::MeshExport;

pub use crate::io::visualization::MeshExportError;

pub use crate::io::visualization::MeshExportValidationError;

pub use crate::io::visualization::MeshSimplexRecord;

pub use crate::io::visualization::MeshVertexRecord;

pub use crate::io::visualization::SimplexRecord;

pub use crate::io::visualization::VISUALIZATION_SCHEMA;

pub use crate::io::visualization::VISUALIZATION_SCHEMA_VERSION;

pub use crate::io::visualization::ValidatedMeshExport;

pub use crate::io::visualization::ValidatedVisualizationData;

pub use crate::io::visualization::VertexRecord;

pub use crate::io::visualization::VisualizationData;

pub use crate::io::visualization::VisualizationDataValidationError;

pub use crate::io::visualization::VisualizationExportError;

pub use crate::io::visualization::VisualizationMetadata;

pub use crate::io::visualization::VisualizationTopologyGuarantee;

pub use crate::io::visualization::VisualizationTopologyKind;

pub use crate::repair::DelaunayCheckPolicy;

pub use crate::repair::DelaunayRepairHeuristicConfig;

pub use crate::repair::DelaunayRepairHeuristicSeeds;

pub use crate::repair::DelaunayRepairOperation;

pub use crate::repair::DelaunayRepairOutcome;

pub use crate::repair::DelaunayRepairPolicy;

pub use crate::spherical::SphericalDelaunayBuilder;

pub use crate::spherical::SphericalDelaunayConstructionError;

pub use crate::spherical::SphericalDelaunayTriangulation;

pub use crate::spherical::SphericalDelaunayValidationError;

pub use crate::spherical::SphericalSimplex;

pub use crate::spherical::SphericalSimplexError;

pub use crate::spherical::SphericalValidationLayer;

pub use crate::tds::InvariantError;

pub use crate::tds::InvariantKind;

pub use crate::tds::InvariantViolation;

pub use crate::tds::TriangulationValidationReport;

pub use crate::topology::spaces::spherical::SphericalMetric;

pub use crate::topology::spaces::spherical::SphericalPoint;

pub use crate::topology::spaces::spherical::SphericalPointError;

pub use crate::validation::DelaunayTriangulationValidationError;

pub use crate::validation::DelaunayVerificationError;

pub use crate::validation::DelaunayVerificationErrorKind;

Modules

algorithms

Public low-level algorithms that are useful outside full construction.

builder

Fluent builder for Delaunay triangulations. Fluent builder for DelaunayTriangulation with optional toroidal topology and typed simplex storage.

collections

Public collection aliases and small-buffer types used by low-level APIs.

construction

Batch construction options, errors, statistics, and policy helpers. Batch construction options, errors, statistics, and policy helpers.

delaunayize

End-to-end “repair then delaunayize” workflow. End-to-end “repair then delaunayize” workflow.

diagnostics

Construction and performance diagnostics. Construction and performance diagnostics for triangulation workflows.

flips

Triangulation editing operations (bistellar flips). Triangulation editing operations (bistellar flips).

geometry

Contains geometric types including the Point struct and geometry predicates.

io

I/O and downstream-facing export data models.

pachner

Unified Pachner move workflow API for local topology editing. Unified Pachner move workflow API.

prelude

A prelude module that re-exports commonly used types and macros. This makes it easier to import the most commonly used items from the crate.

query

Public traversal, adjacency, barycenter, convex-hull, set-comparison, and query support APIs.

repair

Repair policies and outcomes for Delaunay triangulations. Repair policies and outcomes for Delaunay triangulations.

spherical

Prototype spherical Delaunay construction via the spherical topology backend. Prototype spherical Delaunay construction via ambient convex-hull duality.

tds

Public low-level topology data structures and TDS helpers.

topology

Topology analysis and validation for triangulated spaces.

validation

Delaunay-level validation APIs, reports, and construction diagnostics. Delaunay-level validation APIs, proofs, and construction diagnostics.

Macros

assert_jaccard_gte

Assert that the Jaccard index between two sets meets or exceeds a threshold.

vertex

Creates a Vertex through the existing fallible smart constructors.

Structs

DelaunayTriangulation

Delaunay triangulation with incremental insertion support.

DelaunayViolationDetail

Details for the first simplex in a DelaunayViolationReport.

DelaunayViolationReport

Structured summary of Delaunay empty-circumsphere violations.

DuplicateDetectionMetrics

Telemetry counters for duplicate-coordinate detection.

InsertionStatistics

Statistics about a vertex insertion operation.

OrientationWitness

A coherent intrinsic orientation of a pure simplicial complex.

PlManifoldRepairStats

Statistics and artifacts collected during PL-manifold repair.

SuspicionFlags

Adaptive error-checking on suspicious operations.

Triangulation

Generic triangulation combining kernel and data structure.

TriangulationRealizationIntersectionDetail

Detailed witness for an illegal realized-simplex intersection.

TriangulationRealizationSimplexDetail

Key- and UUID-based snapshot of one realized simplex.

TriangulationRealizationSimplexPairDetail

Key- and UUID-based snapshot of one realized simplex pair.

TriangulationRealizationValidationReport

Structured Level 4 realization validation report.

Enums

CavityFillingError

Structured reason why cavity filling failed.

CavityRepairStage

Stage where cavity repair detected invalid facet sharing.

DeduplicationError

Errors returned by fallible vertex deduplication helpers.

DelaunayRepairErrorKind

Flip-repair failure category used by compact error summaries.

DelaunayRepairFailureContext

Insertion-stage context for flip-based Delaunay repair failures.

DelaunayValidationError

Errors that can occur during Delaunay property validation.

DeleteVertexError

Errors returned by DelaunayTriangulation::delete_vertex.

FinalDelaunayValidationContext

Classifies the construction phase that failed final Level 5 Delaunay validation.

FinalTopologyValidationContext

Classifies the construction phase that failed final Levels 1–3 validation.

HullExtensionReason

Reason for hull extension failure.

InitialSimplexConstructionError

Structured reason why initial-simplex construction failed during insertion.

InitialSimplexUnexpectedInsertionStage

Typed insertion-stage failure that should not occur while bootstrapping an initial simplex.

InsertionError

Error during incremental insertion.

InsertionErrorKind

Insertion failure category used by typed diagnostics.

InsertionErrorSourceKind

Nested discriminant for insertion errors that wrap another validation layer.

InsertionOutcome

Outcome of a single-vertex insertion attempt.

InsertionResult

Result of an insertion attempt.

InsertionTopologyValidationContext

Fixed context for a Level 3 topology validation failure during insertion.

NeighborRebuildError

Structured reason why neighbor repair failed after cavity repair.

NeighborWiringError

Structured reason why neighbor wiring failed.

PeriodicDomainPeriodError

Invalid periodic-domain period observed during Level 4 realization validation.

PlManifoldRepairError

Errors that can occur during PL-manifold repair.

PlManifoldRepairStage

Targeted PL-manifold repair stage that produced a topology-repair diagnostic.

RepairDecision

Decision outcome for a flip-based Delaunay repair attempt.

RepairSkipReason

Reason why flip-based repair was skipped.

SimplexBarycenterError

Error returned when computing a simplex barycenter.

SimplexDataFillError

Error returned when filling simplex payloads from a secondary map.

SpatialIndexConstructionFailure

Typed reason a spatial insertion index could not be constructed.

TdsConstructionFailure

Compact, typed summary of a TdsConstructionError.

TdsValidationFailure

Compact, typed summary of a TdsError used inside insertion-stage errors.

TopologicalOperation

Semantic classification of topological modifications to a triangulation.

TopologyGuarantee

Selects which topological invariants are checked by Level 3 validation.

TriangulationConstructionError

Errors that can occur during triangulation construction.

TriangulationRealizationValidationError

Errors returned by realized-geometry validation (Level 4).

TriangulationRealizationValidationErrorKind

Discriminant for compact Level 4 realized-geometry validation summaries.

TriangulationValidationError

Errors that can occur during Level 3 Intrinsic PL Topology validation.

ValidationConfigurationError

Errors returned when validation scheduling and topology guarantees are incoherent.

ValidationPolicy

Policy controlling when the triangulation runs global validation passes.

Functions

debug_print_first_delaunay_violationdiagnostics

Debug helper: print detailed information about the first detected Delaunay violation (or all vertices if none are found) to aid in debugging.

delaunay_violation_report

Build a structured Delaunay violation report.

find_delaunay_violations

Find simplices that violate the Delaunay property.

is_normal

The function is_normal checks that structs implement auto traits. Traits are checked at compile time, so this function is only used for testing.

try_vertices_from_points

Creates vertices from points by re-validating coordinates at the public boundary.