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 rust, the package currently supports vectors from the nalgebra and cgmath crates.
Project state
Spade has just reached its 1.0 version! New feature requests are welcome.
Documentation
The documentation can be found under docs.rs. There is also a (yet unfinished) user guide available.
Feedback and contributing
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.
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/interactivedemo, run it with cargo run.
Interpolation
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.
Performance
The user guide contains detailed graphs and information about the delaunay triangulation's performance.
License
Licensed under either of
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
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.