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

• Arbitrary data types associated with vertices and cells
• d-dimensional Delaunay triangulations
• d-dimensional Convex hulls
• Serialization/Deserialization of all data structures to/from JSON
• Tested for 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

# Build and test
cargo build
cargo test

# Format and lint
cargo fmt --all
cargo clippy --all-targets --all-features

# Run examples
./scripts/run_all_examples.sh

# Run a specific example
cargo run --example triangulation_3d_50_points
cargo run --example convex_hull_3d_50_points

📋 Examples

The examples/ directory contains several demonstrations:

• triangulation_3d_50_points: Complete 3D Delaunay triangulation with 50 random points
• convex_hull_3d_50_points: 3D convex hull extraction and analysis with performance benchmarks
• boundary_analysis_trait: Demonstrates boundary facet analysis using the trait system
• implicit_conversion: Shows coordinate conversion patterns and utilities
• test_circumsphere: Comprehensive geometric predicate testing suite

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

The library's geometric predicates and algorithms are based on established computational geometry literature:

Circumcenter and Circumradius Calculations

• Lévy, Bruno, and Yang Liu. "Lp Centroidal Voronoi Tessellation and Its Applications." ACM Transactions on Graphics 29, no. 4 (July 26, 2010): 119:1-119:11. DOI: 10.1145/1778765.1778856

Robust Geometric Predicates

• Shewchuk, J. R. "Adaptive Precision Floating-Point Arithmetic and Fast Robust Geometric Predicates." Discrete & Computational Geometry 18, no. 3 (1997): 305-363. DOI: 10.1007/PL00009321
• Shewchuk, J. R. "Robust Adaptive Floating-Point Geometric Predicates." Proceedings of the Twelfth Annual Symposium on Computational Geometry (1996): 141-150.

Lifted Paraboloid Method

• Preparata, Franco P., and Michael Ian Shamos. "Computational Geometry: An Introduction." Texts and Monographs in Computer Science. New York: Springer-Verlag, 1985.
• Edelsbrunner, Herbert. "Algorithms in Combinatorial Geometry." EATCS Monographs on Theoretical Computer Science. Berlin: Springer-Verlag, 1987.

Triangulation Data Structures and Algorithms

• CGAL Triangulation Documentation
• Bowyer, A. "Computing Dirichlet tessellations." The Computer Journal 24, no. 2 (1981): 162-166. DOI: 10.1093/comjnl/24.2.162
• Watson, D.F. "Computing the n-dimensional Delaunay tessellation with application to Voronoi polytopes." The Computer Journal 24, no. 2 (1981): 167-172. DOI: 10.1093/comjnl/24.2.167
• de Berg, M., et al. "Computational Geometry: Algorithms and Applications." 3rd ed. Berlin: Springer-Verlag, 2008. DOI: 10.1007/978-3-540-77974-2