32 stable releases

2.13.1 Mar 4, 2025
2.12.1 Sep 9, 2024
2.10.0 Jul 25, 2024
2.6.0 Jan 14, 2024
0.2.1 Oct 11, 2016

#53 in Data structures

Download history 53884/week @ 2024-12-08 48233/week @ 2024-12-15 19995/week @ 2024-12-22 24532/week @ 2024-12-29 46188/week @ 2025-01-05 47916/week @ 2025-01-12 49735/week @ 2025-01-19 48030/week @ 2025-01-26 63176/week @ 2025-02-02 149557/week @ 2025-02-09 145431/week @ 2025-02-16 166636/week @ 2025-02-23 182804/week @ 2025-03-02 172272/week @ 2025-03-09 146320/week @ 2025-03-16 141418/week @ 2025-03-23

656,831 downloads per month
Used in 267 crates (21 directly)

MIT/Apache

595KB
11K SLoC

Docs Crates.io License GitHub Workflow Status (branch) dependency status

spade

Delaunay triangulations for the rust ecosystem.

  • 2D Delaunay triangulation, optionally backed by a hierarchy structure for improved nearest neighbor and insertion performance.
  • Allows both incremental and bulk loading creation of triangulations
  • Support for vertex removal
  • 2D constrained Delaunay triangulation (CDT)
  • Delaunay refinement
  • Uses precise geometric predicates to prevent incorrect geometries due to rounding issues
  • Supports extracting the Voronoi diagram
  • Natural neighbor interpolation

A Delaunay triangulation and the dual Voronoi Graph

Project goals

Project goals, in the order of their importance:

  1. Robustness - all data structures should behave correctly. An incorrect result, even if triggered only under rare circumstances, is not acceptable. This is why Spade uses a precise calculation kernel by default.
  2. Easy to use - favor an easy-to-use API over an API that exposes all bells and whistles.
  3. Performance - Delaunay triangulations are often a low level component of an application. Optimization in this area pays off greatly.
  4. Small footprint - Spade should be a sensible library to include in your project that doesn't require too many dependencies. Bigger dependencies will be feature gated when possible.

Roadmap

For Spade 3:

  • Possibly API simplification by un-supporting non-f64 outputs.

Performance and comparison to other crates

Refer to the delaunay_compare readme for some benchmarks and a comparison with other crates.

License

Licensed under either of

at your option.

Dependencies

~1.5MB
~22K SLoC