spade
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.
Documentation
The documentation can be found under docs.rs
Using spade
Add this to your Cargo.toml:
spade = "0.2.*"
Feedback
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.
Examples
Note: If you have opened this on docs.rs, you won't see any images. Use the README.md on the GitHub page.
R-Tree
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.
Natural neighbor interpolation
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.
Performance
The following measurements were taken on an Intel Core i7-3517u.
Insertion performance for various delaunay kernels: