Skip to content
/ spade Public

Delaunay Triangulations for the Rust Ecosystem

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

Stoeoef/spade

Repository files navigation

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.