spade
Delaunay triangulations and Voronoi diagrams for the Rust ecosystem
Repository Health
Technical Analysis
spade is a Rust library for computational geometry centered on 2D Delaunay triangulations. It supports plain and constrained Delaunay triangulations (CDTs), Voronoi diagram extraction, and can be backed by a hierarchy structure for fast nearest-neighbor queries and insertions.
The crate supports both incremental and bulk-loading construction, natural-neighbor interpolation, and a rich navigation API over vertices, edges, and faces, making it a foundation for meshing, spatial analysis, and graphics work in Rust.
What You Get
- 2D Delaunay triangulation with optional hierarchy acceleration
- Constrained Delaunay triangulations (CDT) with edge constraints
- Voronoi diagram extraction as the triangulation dual
- Incremental and bulk-loading construction paths
- Natural-neighbor interpolation and robust geometric predicates
Common Use Cases
- Generating meshes from point clouds for graphics and simulation
- Nearest-neighbor and spatial-proximity queries over 2D points
- Building Voronoi diagrams for spatial partitioning
- Interpolating scattered data with natural-neighbor methods
Under The Hood
Architecture — spade represents triangulations with a half-edge (doubly-connected edge list) core under src/delaunay_core, exposed through DelaunayTriangulation and CDT types in delaunay_triangulation.rs, cdt.rs, and triangulation.rs, with iterator modules (flood_fill_iterator.rs, intersection_iterator.rs) for mesh traversal and queries. Tech Stack — Rust edition 2021 depending on smallvec, robust (for exact geometric predicates), num-traits, and hashbrown, with optional serde and mint integration and a no_std path. Code Quality — The crate is mature and documented with an mdbook user guide, ships test_utilities.rs plus a test suite and benches, and uses the robust crate to avoid floating-point robustness bugs common to geometry code. API Design — Access is through handle-based navigation (vertex/edge/face handles) and builder-style insertion, which is expressive but carries a moderate learning curve for developers new to half-edge meshes.
