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.

🚧 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

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