30 stable releases

2.12.1 Sep 9, 2024
2.10.0 Jul 25, 2024
2.6.0 Jan 14, 2024
2.5.1 Dec 28, 2023
0.2.1 Oct 11, 2016

#78 in Data structures

Download history 55164/week @ 2024-09-20 52179/week @ 2024-09-27 45278/week @ 2024-10-04 46296/week @ 2024-10-11 50473/week @ 2024-10-18 51307/week @ 2024-10-25 53435/week @ 2024-11-01 52248/week @ 2024-11-08 55470/week @ 2024-11-15 50539/week @ 2024-11-22 52202/week @ 2024-11-29 54164/week @ 2024-12-06 47800/week @ 2024-12-13 25631/week @ 2024-12-20 21171/week @ 2024-12-27 43181/week @ 2025-01-03

147,069 downloads per month
Used in 233 crates (21 directly)

MIT/Apache

585KB
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

~2.5MB
~34K SLoC