Spade (SPAtial DatastructurEs, obviously!) implements a few nifty datastructures optimized for spatial access operations.
The first major datastructure is an n-dimensional r*-tree (wikipedia) for efficient nearest-neighbor and point lookup queries.
The second datastructures implements a 2D delaunay triangulation (wikipedia) backed by an r-tree for faster insertion times and nearest neighbor lookup. The triangulation also implements natural neighbor interpolation (wikipedia) which allows for a smooth interpolation on the resulting grid.
All structures are purely written in (safe) rust, the package currently supports vectors from the nalgebra and cgmath crates.
The documentation can be found under docs.rs
Add this to your Cargo.toml:
spade = "0.2.*"
Do you miss a feature? Many features may be easy to implement, the crate's main author might just have missed that use case. Please do post an issue on GitHub. Please do report bugs as well. If you're in for an adventure, pull requests of any kind are very welcome.
Note: If you have opened this on docs.rs, you won't see any images. Use the README.md on the GitHub page.
This image shows the structure of an r*-tree with some points inserted in a circular pattern.
Points are shown as blue dots, the tree's directory nodes are displayed as boxes of different colors (depending on their depth in the tree).
Note that the implementation tries prevent any boxes from overlapping, resulting in faster query performance. You can find this example in /examples/rtreevis, run it with cargo run.
The delaunay triangulation of a height field is shown with orange lines, the green grid shows the natural neighbor interpolated heights. In contrast to barycentric interpolation (the gray polygons), natural neighbor interpolation is smooth (C¹ differentiable, except for the data points themselves). You can find this example in /examples/nninterpolation, run it with cargo run.
The following measurements were taken on an Intel Core i7-3517u.
Insertion performance for various delaunay kernels:
