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

#55 in Data structures

Download history 36332/week @ 2024-07-09 34494/week @ 2024-07-16 40496/week @ 2024-07-23 43906/week @ 2024-07-30 41739/week @ 2024-08-06 47334/week @ 2024-08-13 43055/week @ 2024-08-20 49861/week @ 2024-08-27 52342/week @ 2024-09-03 52006/week @ 2024-09-10 48188/week @ 2024-09-17 55100/week @ 2024-09-24 46559/week @ 2024-10-01 47299/week @ 2024-10-08 48254/week @ 2024-10-15 49662/week @ 2024-10-22

201,214 downloads per month
Used in 209 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
~35K SLoC