delaunay

D-dimensional Delaunay triangulations in Rust, inspired by CGAL.

📐 Introduction

This library implements d-dimensional Delaunay triangulations in Rust. It is inspired by CGAL, which is a C++ library for computational geometry, and Spade, a Rust library that implements 2D Delaunay triangulations, Constrained Delaunay triangulations, and Voronoi diagrams. The goal of this library is to provide a lightweight alternative to CGAL for the Rust ecosystem.

✨ Features

• Copy-able data types associated with vertices and cells (integers, floats, chars, custom enums)
• d-dimensional Delaunay triangulations
• d-dimensional Convex hulls
• Geometry quality metrics for simplices: radius ratio and normalized volume (dimension-agnostic)
• Serialization/Deserialization of all data structures to/from JSON
• Tested for 2-, 3-, 4-, and 5-dimensional triangulations

See CHANGELOG.md for details.

⚠️ Known Limitations

Delaunay Property

The incremental Bowyer-Watson algorithm produces structurally valid triangulations but may contain local violations of the Delaunay empty circumsphere property in rare cases. These violations typically occur with:

• Near-degenerate point configurations
• Specific geometric arrangements of input points

Most triangulations satisfy the Delaunay property, and all structural invariants (TDS validity) are maintained. Full Delaunay property guarantees will require a future bistellar flip implementation, currently planned for v0.7.0+.

For details, see: Issue #120 Investigation

Validation: You can verify your triangulation meets your requirements using the library's 4-level validation hierarchy:

• Level 2 (dt.is_valid()) - Structural correctness (expected to pass when using public APIs; not affected by Issue #120)
• Level 3 (dt.triangulation().validate_manifold()) - Manifold topology + Euler characteristic
• Level 4 (dt.validate_delaunay()) - Delaunay property (may fail in rare cases per Issue #120)

For applications requiring strict Delaunay guarantees:

• Use validate_delaunay() to check your specific triangulation
• Use smaller point sets (violations are rarer)
• Filter degenerate configurations when possible
• Monitor for updates in future releases

🚧 Project History

This crate was originally maintained at 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, which hosts a completely rewritten d-dimensional implementation focused on computational geometry research applications.

• 📚 Docs for old versions (≤ 0.1.0): https://docs.rs/delaunay/0.1.0/delaunay/
• 📚 Docs for current version (≥ 0.3.4): https://docs.rs/delaunay

🤝 How to Contribute

We welcome contributions! Here's a 30-second quickstart:

# 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 ci               # Fast iteration (linting + lib/doc tests + bench compile)
just commit-check     # Pre-commit validation (linting + all tests + examples)
just commit-check-slow # Comprehensive with slow tests (100+ vertices)
just --list           # See all available commands
just help-workflows   # Show common workflow patterns

Try the examples:

just examples         # Run all examples
# Or run specific examples:
cargo run --release --example triangulation_3d_20_points
cargo run --release --example convex_hull_3d_20_points

📋 Examples

The examples/ directory contains several demonstrations:

• triangulation_3d_20_points: 3D Delaunay triangulation with a stable 20-point random configuration
• convex_hull_3d_20_points: 3D convex hull extraction and analysis on the same 20-point configuration
• into_from_conversions: Demonstrates Into/From trait conversions and utilities
• point_comparison_and_hashing: Demonstrates point comparison and hashing behavior
• memory_analysis: Memory usage analysis for triangulations across dimensions with allocation tracking
• 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.

For comprehensive guidelines on development environment setup, testing, benchmarking, performance analysis, and development workflow, please see 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

• Validation Guide - Comprehensive 4-level validation hierarchy guide (element → structural → manifold → Delaunay)
• Code Organization - Project structure and module patterns
• Topology Guide - Topological concepts and Euler characteristic
• Issue #120 Investigation - Known Delaunay property limitations

📚 References

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

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.