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 classes are purely written in rust, the package currently supports vectors from the nalgebra and cgmath crates.
We're not a crate yet, so add this to your Cargo.toml:
[dependencies]
spade = { git = "https://github.com/Stoeoef/spade.git" }
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.
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).
The following measurements were taken on an Intel Core i7-3517u.
Insertion performance for various delaunay kernels:
