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 rust, the package currently supports vectors from the nalgebra and cgmath crates.
Spade has just reached its 1.0 version! New feature requests are welcome.
The documentation can be found under docs.rs. There is also a (yet unfinished) user guide available.
Do you miss a feature? Many features may be easy to implement, I might just have missed that use case. Please do post an issue on GitHub. If you think there's a feature missing and you are interested to implement it yourself, don't be shy to mention it - I'd be happy to help you getting started. Just post an appropriate issue on GitHub.
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/interactivedemo, run it with cargo run.
The user guide has a an own chapter about interpolation, along with some nice images.
An example showcasing spade's interpolation features can be found in /examples/nninterpolation, run it with cargo run.
The user guide contains detailed graphs and information about the delaunay triangulation's performance.
Licensed under either of
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.