# delaunay

[![DOI](https://zenodo.org/badge/729897852.svg)](https://doi.org/10.5281/zenodo.16931097)
[![Crates.io](https://img.shields.io/crates/v/delaunay.svg)](https://crates.io/crates/delaunay)
[![Downloads](https://img.shields.io/crates/d/delaunay.svg)](https://crates.io/crates/delaunay)
[![License](https://img.shields.io/crates/l/delaunay.svg)](https://github.com/acgetchell/delaunay/blob/main/LICENSE)
[![Docs.rs](https://docs.rs/delaunay/badge.svg)](https://docs.rs/delaunay)
[![CI](https://github.com/acgetchell/delaunay/actions/workflows/ci.yml/badge.svg)](https://github.com/acgetchell/delaunay/actions/workflows/ci.yml)
[![CodeQL](https://github.com/acgetchell/delaunay/actions/workflows/codeql.yml/badge.svg)](https://github.com/acgetchell/delaunay/actions/workflows/codeql.yml)
[![rust-clippy analyze](https://github.com/acgetchell/delaunay/actions/workflows/rust-clippy.yml/badge.svg)](https://github.com/acgetchell/delaunay/actions/workflows/rust-clippy.yml)
[![codecov](https://codecov.io/gh/acgetchell/delaunay/graph/badge.svg?token=WT7qZGT9bO)](https://codecov.io/gh/acgetchell/delaunay)
[![Audit dependencies](https://github.com/acgetchell/delaunay/actions/workflows/audit.yml/badge.svg)](https://github.com/acgetchell/delaunay/actions/workflows/audit.yml)
[![Codacy Badge](https://app.codacy.com/project/badge/Grade/3cad94f994f5434d877ae77f0daee692)](https://app.codacy.com/gh/acgetchell/delaunay/dashboard?utm_source=gh&utm_medium=referral&utm_content=&utm_campaign=Badge_grade)

D-dimensional Delaunay triangulations and convex hulls in [Rust] for finite
point sets in Euclidean and periodic domains, with exact predicates,
multi-level validation, and bistellar flips inspired by [CGAL].

## 📐 Introduction

This library implements dimension-generic [Delaunay triangulations] in [Rust]
for computational geometry and scientific workflows. It is inspired by [CGAL],
which is a [C++] library for computational geometry, and [Spade], a [Rust]
library focused on 2D triangulations. The goal is to provide a lightweight but
rigorous Rust-native option for workflows that need explicit topology settings,
validation levels, deterministic construction controls, and repair behavior.

Use this crate when you want:

- Delaunay triangulations or convex hulls in 2D through 5D.
- Exact predicates and deterministic handling of degenerate inputs.
- Validation reports that separate element, structure, topology, and Delaunay
  failures.
- Release-mode 3D construction at 10,000 vertices with final Levels 1–4
  validation in the current large-scale acceptance harness.
- PL-manifold-aware editing via bistellar flips.

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

## 🧪 Scientific Basis

This crate models triangulations of finite point sets in `R^d` as oriented simplicial complexes with explicit
combinatorial and geometric checks.

- Core operational invariant for editing/repair: coherent orientation + PL-manifold validity
- Local move system: bistellar flips (`k = 1, 2, 3` and inverses), providing the supported [Pachner moves] set in dimensions ≤ 5
- Geometric convergence basis in finite-point workflows: Herbert Edelsbrunner and Nina R. Shah,
  *Incremental Topological Flipping Works for Regular Triangulations*, **Discrete & Computational Geometry (1996)**,
  <https://doi.org/10.1007/BF01975867>
- Scope of claims: guarantees apply to supported library workflows (construction, flip-based repair, and validation APIs),
  not arbitrary external mutation of internal structures

## ✨ Features

- [x]  Copyable data types associated with vertices and cells (integers, floats, chars, custom enums)
- [x]  d-dimensional [Delaunay triangulations]
- [x]  d-dimensional [Convex hulls]
- [x]  Toroidal (periodic) triangulations via [`DelaunayTriangulationBuilder`] with Phase 1 (canonicalization) and Phase 2 (image-point method) support
- [x]  Geometry quality metrics for simplices: radius ratio and normalized volume (dimension-agnostic)
- [x]  Serialization/deserialization of all data structures to/from [JSON]
- [x]  Tested for 2-, 3-, 4-, and 5-dimensional triangulations
- [x]  Configurable predicate kernels: `AdaptiveKernel` (default; exact arithmetic + SoS),
  `RobustKernel` (exact, preserves degeneracy signals), `FastKernel` (raw f64 for
  well-conditioned exploratory work; not accepted by explicit repair APIs)
- [x]  Bulk insertion ordering (`InsertionOrderStrategy`): [Hilbert curve] (default) or input order
- [x]  Batch construction options (`ConstructionOptions`): optional deduplication and deterministic retries
- [x]  Incremental construction APIs: insertion plus transactional vertex removal (`remove_vertex`)
- [x]  4-level validation hierarchy (element validity → TDS structural validity → manifold topology → Delaunay property), including full diagnostics via `validation_report`
- [x]  Local topology validation ([PL-manifold] default, [Pseudomanifold] opt-out)
- [x]  Coherent combinatorial orientation validation/normalization for cells, maintaining oriented simplicial complexes
- [x]  The complete set of [Pachner moves] up to 5D implemented as bistellar k-flips for k = 1, 2, 3 plus inverse moves
- [x]  [Delaunay repair] using bistellar flips for k=2/k=3 with inverse edge/triangle queues in 4D/5D
- [x]  10,000-vertex 3D large-scale acceptance run: zero skipped vertices,
  final flip repair clean, and `validation_report` OK for Levels 1–4 in roughly
  100 seconds on maintainer Apple M4 Max hardware
- [x]  Safe Rust: `#![forbid(unsafe_code)]`

See [CHANGELOG.md](CHANGELOG.md) for details. Older releases are archived under
[docs/archive/changelog/](docs/archive/changelog/).

## 🟢 Minimal Construction Example

The construction API has two entry points:

- `DelaunayTriangulation::new(&vertices)` - simple constructor for the common case
- [`DelaunayTriangulationBuilder`] - Advanced configuration (custom options, toroidal topology)

Add the library to your crate:

```bash
cargo add delaunay
```

Choose the smallest prelude that matches the task:

| Task | Import |
|---|---|
| Construct/configure a Delaunay triangulation | `use delaunay::prelude::triangulation::construction::*` |
| Read-only traversal, adjacency, convex hulls, and comparison helpers | `use delaunay::prelude::query::*` |
| Points, kernels, predicates, and geometric measures | `use delaunay::prelude::geometry::*` |
| Random points or triangulations for examples, tests, and benchmarks | `use delaunay::prelude::generators::*` |
| Low-level incremental insertion building blocks | `use delaunay::prelude::triangulation::insertion::*` |
| Bistellar flips / Edit API | `use delaunay::prelude::triangulation::flips::*` |
| Delaunay repair diagnostics and policies | `use delaunay::prelude::triangulation::repair::*` |
| Delaunayize workflow | `use delaunay::prelude::triangulation::delaunayize::*` |
| Construction telemetry diagnostics | `use delaunay::prelude::triangulation::diagnostics::*` |
| Construction validation cadence/policy | `use delaunay::prelude::triangulation::validation::*` |
| Hilbert ordering and quantization utilities | `use delaunay::prelude::ordering::*` |
| Low-level TDS cells, facets, keys, and validation reports | `use delaunay::prelude::tds::*` |
| Collection aliases and small buffers | `use delaunay::prelude::collections::*` |
| Topology validation and Euler characteristic helpers | `use delaunay::prelude::topology::validation::*` |
| Topological spaces and topology traits | `use delaunay::prelude::topology::spaces::*` |

`use delaunay::prelude::*` remains available for quick experiments, but examples
and benchmarks in this repository prefer focused preludes so imports document intent.
The broad `delaunay::prelude::triangulation::*` import is retained for compatibility,
but new docs and tests should prefer the narrow workflow preludes above.

```rust
use delaunay::prelude::triangulation::construction::{DelaunayTriangulation, vertex};

// Create a 4D Delaunay triangulation from a set of vertices (uses AdaptiveKernel by default).
let vertices = vec![
    vertex!([0.0, 0.0, 0.0, 0.0]),
    vertex!([1.0, 0.0, 0.0, 0.0]),
    vertex!([0.0, 1.0, 0.0, 0.0]),
    vertex!([0.0, 0.0, 1.0, 0.0]),
    vertex!([0.0, 0.0, 0.0, 1.0]), // 5 vertices (D+1) creates first 4-simplex
    vertex!([0.2, 0.2, 0.2, 0.2]), // Adding this vertex creates new simplices via flips
];

let dt = DelaunayTriangulation::new(&vertices).unwrap();

assert_eq!(dt.dim(), 4);
assert_eq!(dt.number_of_vertices(), 6);
assert_eq!(dt.number_of_cells(), 5); // 1 simplex from first 5 vertices + 4 new simplices from last vertex

// Optional verification:
// - `dt.is_valid()` checks Level 4 only (Delaunay property).
// - `dt.validate()` checks Levels 1–4 (elements + structure + topology + Delaunay).
assert!(dt.is_valid().is_ok());
```

### Toroidal (Periodic) Triangulations

For periodic boundary conditions, use `DelaunayTriangulationBuilder`:

```rust
use delaunay::prelude::triangulation::construction::{
    DelaunayTriangulationBuilder, TopologyKind, vertex,
};

// Phase 1: Canonicalization (wraps coordinates into [0, 1)²)
let vertices = vec![
    vertex!([0.1, 0.2]),
    vertex!([0.8, 0.3]),
    vertex!([0.5, 0.7]),
    vertex!([1.2, 0.4]),  // Wraps to [0.2, 0.4]
];

let dt = DelaunayTriangulationBuilder::new(&vertices)
    .toroidal([1.0, 1.0])  // Fundamental domain periods
    .build::<()>()
    .unwrap();

assert_eq!(dt.topology_kind(), TopologyKind::Toroidal);
```

For the full periodic image-point method (Phase 2), see the [`DelaunayTriangulationBuilder`] documentation.

### Need more control?

- **Editing with flips (Edit API)**:
  see [`docs/workflows.md`](docs/workflows.md) for a minimal example and [`docs/api_design.md`](docs/api_design.md) for details.
- **Flip-based Delaunay repair**, including the heuristic rebuild fallback (`repair_delaunay_with_flips*`):
  see [`docs/workflows.md`](docs/workflows.md).
- **Repair diagnostics and mutating-operation rollback**:
  `remove_vertex` rolls back if post-removal repair or orientation canonicalization fails, and repair failures preserve typed source errors for debugging.
- **Insertion outcomes and statistics** (`insert_with_statistics`, `InsertionOutcome`, `InsertionStatistics`):
  see [`docs/workflows.md`](docs/workflows.md) and [`docs/numerical_robustness_guide.md`](docs/numerical_robustness_guide.md).
- **Topology guarantees** (`TopologyGuarantee`) and **automatic topology validation** (`ValidationPolicy`):
  see [`docs/validation.md`](docs/validation.md) and [`docs/topology.md`](docs/topology.md).

## ✅ Validation and Guarantees

| Level | What is validated | Primary API |
|---|---|---|
| 1 | Element validity (vertex/cell primitives) | `dt.validate()` / `dt.validation_report()` |
| 2 | TDS structural validity (keys, incidences, neighbors) | `dt.tds().is_valid()` |
| 3 | Manifold topology (link checks, Euler/topological consistency) | `dt.as_triangulation().is_valid()` |
| 4 | Delaunay property (empty-circumsphere via local predicates) | `dt.is_valid()` |
| 1-4 | Cumulative checks with diagnostics | `dt.validate()` or `dt.validation_report()` |

`TopologyGuarantee` controls which Level 3 manifold constraints are enforced, and `ValidationPolicy`
controls when Level 3 checks run automatically during incremental insertion.

## 🔬 Reproducibility

The construction pipeline exposes deterministic controls for experiments and regression testing:

- Deterministic insertion ordering via `InsertionOrderStrategy`:
  `Hilbert` (default) or `Input`
  (use `Input` to preserve caller-provided order exactly)
- Deterministic preprocessing via `DedupPolicy`
- Deterministic retry behavior via `RetryPolicy` (including seeded shuffled retries) or `RetryPolicy::Disabled`
- Explicit topology/validation configuration via `TopologyGuarantee` and `ValidationPolicy`

```rust
use delaunay::prelude::triangulation::construction::{
    ConstructionOptions, DedupPolicy, DelaunayTriangulationBuilder, InsertionOrderStrategy,
    RetryPolicy, TopologyGuarantee, vertex,
};
use delaunay::prelude::triangulation::validation::ValidationPolicy;

let vertices = vec![
    vertex!([0.0, 0.0]),
    vertex!([1.0, 0.0]),
    vertex!([0.0, 1.0]),
];

let options = ConstructionOptions::default()
    .with_insertion_order(InsertionOrderStrategy::Input)
    .with_dedup_policy(DedupPolicy::Exact)
    .with_retry_policy(RetryPolicy::Disabled);

let mut dt = DelaunayTriangulationBuilder::new(&vertices)
    .topology_guarantee(TopologyGuarantee::PLManifold)
    .construction_options(options)
    .build::<()>()
    .unwrap();

dt.set_validation_policy(ValidationPolicy::Always);
assert!(dt.validate().is_ok());
```

For reproducible checks in CI/local runs, use `just check`, `just test`, `just doc-check`, or `just ci`.

## ⚠️ Limitations

- **Dimension coverage:** CI and property-test coverage targets 2D–5D.
- **Exact predicate limits:** exact orientation is available through D=6; exact
  insphere is available through D=5. For D≥6, insphere classification relies on
  symbolic perturbation and deterministic tie-breaking because the `(D+2)×(D+2)`
  determinant exceeds the stack matrix limit.
- **Large 4D+ batches:** thousands of 4D points can be expensive to investigate.
  Use release mode and the large-scale debug harness for characterization.
- **3D scale:** the default 10,000-vertex 3D release-mode harness is now an
  acceptance case for full Levels 1–4 validity. Its wall time is hardware- and
  load-sensitive; use `just debug-large-scale-3d 10000 1` for local numbers.
- **Feature gaps:** [Constrained Delaunay triangulations], [Voronoi diagrams],
  built-in visualization, GPU/parallel meshing, and out-of-core construction are
  out of scope today.
- **Validation/repair guarantees** assume the library-managed construction/editing pipeline.

See [Limitations and Scope](docs/limitations.md) for details and
[Roadmap](docs/roadmap.md) for active follow-up work.

## 🚧 Project History

This crate was originally maintained at [https://github.com/oovm/shape-rs](https://github.com/oovm/shape-rs) through version `0.1.0`.
The original implementation provided basic Delaunay triangulation functionality.

Starting with version `0.3.4`, maintenance transferred to [this repository](https://github.com/acgetchell/delaunay), which hosts a completely
rewritten d-dimensional implementation focused on computational geometry research applications.

- 📚 Docs for the original implementation (`0.1.0`): <https://docs.rs/delaunay/0.1.0/delaunay/>
- 📚 Docs for the rewritten implementation (`0.3.4+`): <https://docs.rs/delaunay>

## 🤝 How to Contribute

We welcome contributions! Here's a quickstart:

```bash
# Clone and setup
git clone https://github.com/acgetchell/delaunay.git
cd delaunay

# Setup development environment (installs tools, builds project)
cargo install just
just setup            # Installs all development tools and dependencies

# Development workflow
just fix              # Apply formatters/auto-fixes (mutating)
just check            # All non-mutating lints/validators
just test             # Tests + benchmark/release compile smoke
just ci               # Comprehensive checks + tests + examples
just --list           # See all available commands
just help-workflows   # Show common workflow patterns
```

Benchmark commands that produce performance data use the `perf` Cargo profile
for consistent ThinLTO settings. `just ci` remains the comprehensive validation
path: it runs checks, the test workflow, and examples, but it does not pay the
`perf` profile cost unless measuring performance.

**Try the examples:**

```bash
just examples         # Run all examples
# Or run specific examples:
cargo run --release --example triangulation_3d_100_points
cargo run --release --example convex_hull_3d_100_points
```

## 📋 Examples

The `examples/` directory contains several demonstrations:

- **`convex_hull_3d_100_points`**: 3D convex hull extraction and analysis on the same 100-point configuration
- **`delaunayize_repair`**: Demonstrates the `delaunayize_by_flips` workflow (bounded topology repair + flip-based Delaunay repair + optional fallback)
- **`into_from_conversions`**: Demonstrates Into/From trait conversions and utilities
- **`memory_analysis`**: Memory usage analysis for triangulations across dimensions with allocation tracking
- **`pachner_roundtrip_4d`**: 4D Pachner move (k=1,2,3) roundtrip checks (flip + inverse preserves the triangulation)
- **`point_comparison_and_hashing`**: Demonstrates point comparison and hashing behavior
- **`topology_editing_2d_3d`**: Builder API vs Edit API in 2D/3D (bistellar flips and Delaunay preservation)
- **`triangulation_3d_100_points`**: 3D Delaunay triangulation with a stable 100-point random configuration
- **`zero_allocation_iterator_demo`**: Performance comparison between allocation and zero-allocation iterators

For detailed documentation, sample output, and usage instructions for each example, see [examples/README.md](examples/README.md).

For comprehensive guidelines on development environment setup,
testing, benchmarking, performance analysis, and development workflow, please see [CONTRIBUTING.md](CONTRIBUTING.md).

This includes information about:

- Building and testing the library
- Running benchmarks and performance analysis
- Code style and standards
- Submitting changes and pull requests
- Project structure and development tools

## 📖 Documentation

- **[API Design](docs/api_design.md)** - Builder vs Edit API design (explicit bistellar flips)
- **[Code Organization](docs/code_organization.md)** - Project structure and module patterns
- **[Diagnostics](docs/diagnostics.md)** - Opt-in diagnostic helpers, structured reports, and debug switches
- **[Invariants](docs/invariants.md)** - Theoretical background and rationale for the topological and geometric invariants
- **[Numerical Robustness Guide](docs/numerical_robustness_guide.md)** - Robustness strategies, kernels, and retry/repair behavior
- **[Property Testing Summary](docs/property_testing_summary.md)** - Property-based testing with proptest (where tests live, how to run)
- **[Limitations and Scope](docs/limitations.md)** - Supported dimensions, predicate limits, and feature gaps
- **[Releasing](docs/RELEASING.md)** - Release workflow (changelog + benchmarks + publish)
- **[Roadmap](docs/roadmap.md)** - Current follow-up work and deferred features
- **[Topology](docs/topology.md)** - Level 3 topology validation (manifoldness + Euler characteristic) and module overview
- **[Validation Guide](docs/validation.md)** - Comprehensive 4-level validation hierarchy guide (element → structural → manifold → Delaunay)
- **[Workflows](docs/workflows.md)** - Happy-path construction plus practical Builder/Edit recipes (stats, repairs, and minimal flips)

## 📎 How to Cite

If you use this software in academic work, 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 (version, release date, ORCID), prefer `CITATION.cff`.

## 📚 References

For a comprehensive list of academic references and bibliographic citations used throughout the library, see [REFERENCES.md](REFERENCES.md).

## 🤖 AI Agents

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

AI tools (including ChatGPT, Claude, GitHub Copilot, Cursor, Warp, and CI repair agents) are
expected to read and follow `AGENTS.md` when proposing or applying changes.

Portions of this library were developed with the assistance of these AI tools:

- [ChatGPT]
- [Claude]
- [CodeRabbit]
- [GitHub Copilot]
- [KiloCode]
- [WARP]
>
> All code was written and/or reviewed and validated by the author.

[Rust]: https://rust-lang.org
[CGAL]: https://www.cgal.org/
[C++]: https://isocpp.org
[Spade]: https://crates.io/crates/spade
[JSON]: https://www.json.org/json-en.html
[Delaunay triangulations]: https://en.wikipedia.org/wiki/Delaunay_triangulation
[Constrained Delaunay triangulations]: https://en.wikipedia.org/wiki/Constrained_Delaunay_triangulation
[Voronoi diagrams]: https://en.wikipedia.org/wiki/Voronoi_diagram
[Convex hulls]: https://en.wikipedia.org/wiki/Convex_hull
[Hilbert curve]: https://en.wikipedia.org/wiki/Hilbert_curve
[ChatGPT]: https://openai.com/chatgpt
[Claude]: https://www.anthropic.com/claude
[CodeRabbit]: https://coderabbit.ai/
[GitHub Copilot]: https://github.com/features/copilot
[KiloCode]: https://kilocode.ai/
[WARP]: https://www.warp.dev
[Pseudomanifold]: https://en.wikipedia.org/wiki/Pseudomanifold
[PL-manifold]: https://en.wikipedia.org/wiki/Piecewise_linear_manifold
[Delaunay repair]: https://link.springer.com/article/10.1007/BF01975867
[Pachner moves]: https://en.wikipedia.org/wiki/Pachner_move
[`DelaunayTriangulationBuilder`]: https://docs.rs/delaunay/latest/delaunay/triangulation/builder/struct.DelaunayTriangulationBuilder.html
