23 stable releases

2.6.0 Jan 14, 2024
2.5.1 Dec 28, 2023
2.4.0 Nov 19, 2023
2.2.0 Apr 18, 2023
0.2.1 Oct 11, 2016

#74 in Data structures

Download history 16166/week @ 2023-12-06 19912/week @ 2023-12-13 14183/week @ 2023-12-20 12559/week @ 2023-12-27 22500/week @ 2024-01-03 25002/week @ 2024-01-10 28781/week @ 2024-01-17 25001/week @ 2024-01-24 23743/week @ 2024-01-31 36838/week @ 2024-02-07 44149/week @ 2024-02-14 43804/week @ 2024-02-21 42076/week @ 2024-02-28 40786/week @ 2024-03-06 42825/week @ 2024-03-13 29023/week @ 2024-03-20

162,441 downloads per month
Used in 132 crates (18 directly)

MIT/Apache

520KB
10K SLoC

Docs Crates.io GitHub Workflow Status (branch)

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


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
~33K SLoC