rstared::RTreed is a simple Rust
decorator that adds a
passively listening R-tree,
rstar::RTree, to a
considerable number of common standard library and third-party collection types.
This is useful because it allows to avoid writing glue code to keep R-tree and collection elements in sync. You get spatial indexing for arbitrary collection with very little change to how you store or access your data -- no need to write your own spatial access wrapper anymore.
Naturally, since this library's R-tree comes from the
rstar crate, the
elements stored in the decorated collection must still implement
RTreeObject.
This library is no_std-compatible, is compatible with
undoredo, has no unsafe
code, and has no mandatory third-party dependencies except for
alloc.
rstared is capable of decorating (wrapping) collection types thanks to
maplike, another crate of ours.
Because of that, rstared supports the same set of collections as maplike,
which we list below.
HashMap, gated by thestdfeature (enabled by default);HashSet, gated by thestdfeature (enabled by default);BTreeMap, not feature-gated;BTreeSet, not feature-gated;Vec, not feature-gated;VecDeque, not feature-gated;
bidimap::BiBTreeMap, gated by thebidimapfeature, andbidimap::BiHashMap, which is additionally gated by thestdfeature;indexmap::IndexMapandindexmap::IndexSet, gated by theindexmapfeature;rstar::RTree, not feature-gated;stable_vec::StableVec, gated by thestable-vecfeature;thunderdome::Arena, gated by thethunderdomefeature;arrayvec::ArrayVec, gated by thearrayvecfeature;smallvec::SmallVec, gated by thesmallvecfeature;tinyvec::ArrayVecandtinyvec::TinyVec, gated by thetinyvecfeature;- geometry types from
geo/geo-types:LineString,MultiPoint,MultiLineString,MultiPolygon, andGeometryCollection, gated by thegeofeature;
Add rstared as a dependency to your Cargo.toml together with the features
that gate the collections you are going to use:
[dependencies]
rstared = { version = "0.16.1", features = [
"arrayvec",
"bidimap",
"geo",
"indexmap",
"serde",
"smallvec",
"stable-vec",
"thunderdome",
"tinyvec",
] }For the sake of demonstration, all feature flags are enabled in that snippet. Remove those you don't need.
Following is a basic usage example on Vec
(examples/vec.rs).
Vec is pushable, so values are added with .push() and keyed by their index.
Existing elements can be removed with .swap_remove().
use rstared::{AABB, primitives::Rectangle};
use rstared::RTreed;
fn main() {
// A vec of 2D rectangles will be the underlying collection.
let rect_vec: Vec<Rectangle<(i32, i32)>> = Vec::new();
// Wrap `RTreed` around the vec.
let mut rtreed = RTreed::new(rect_vec);
// Push two rectangles, recording them in the R-tree.
rtreed.push(Rectangle::from_corners((0, 0), (1, 1)));
rtreed.push(Rectangle::from_corners((1, 1), (2, 2)));
// Locate the two rectangles in the R-tree.
assert_eq!(
rtreed
.rtree()
.locate_in_envelope(AABB::from_corners((0, 0), (2, 2)))
.count(),
2
);
// Access a rectangle by its index in the vec.
assert_eq!(
rtreed.get(&0),
Some(&Rectangle::from_corners((0, 0), (1, 1)))
);
// Push one more rectangle.
rtreed.push(Rectangle::from_corners((2, 2), (3, 3)));
// Swap-remove the first rectangle.
assert_eq!(
rtreed.swap_remove(&0),
Rectangle::from_corners((0, 0), (1, 1))
);
// Now the latest-pushed rectangle occupies the place of the first
// rectangle. The second rectangle is as it was previously.
assert_eq!(
rtreed.get(&0),
Some(&Rectangle::from_corners((2, 2), (3, 3)))
);
assert_eq!(
rtreed.get(&1),
Some(&Rectangle::from_corners((1, 1), (2, 2)))
);
assert_eq!(
rtreed
.rtree()
.locate_in_envelope(AABB::from_corners((0, 0), (3, 3)))
.count(),
2
);
}Every call to .swap_remove() invalidates the last index. If you want to
dynamically remove elements without key invalidation, you can use a type with
stable keys, such as Rust standard library's HashMap and BTreeMap, like
this:
let rect_hashmap: HashMap<Rectangle<(i32, i32)>> = HashMap::new();
let mut rtreed = RTreed::new(rect_hashmap);See
examples/hashmap.rs
for a full usage example on HashMap.
Of course, map types are not as fast as Vecs. If you want to retain most
of Vecs performance while still being able to stably remove elements,
consider using third-party collections such as indexmap::IndexMap,
stable_vec::StableVec, thunderdome::Arena. RTreed can decorate them just
as well.
See
examples/thunderdome.rs
for a usage example involving two polygons stored in thunderdome::Arena, a
generational arena.
Following is a usage example on geo's
MultiPolygon
(examples/multipolygon.rs).
Enable the geo feature so that geo-types
Polygon implements RTreeObject via the vendored rstared::rstar:
#[cfg(feature = "geo")]
{
use geo_types::{MultiPolygon, Point, Polygon, line_string};
use rstared::AABB;
use rstared::RTreed;
fn main() {
let multipolygon: MultiPolygon<f64> = MultiPolygon::new(vec![]);
let mut rtreed = RTreed::new(multipolygon);
// Push two polygons, recording them in the R-tree.
rtreed.push(Polygon::new(
line_string![
(x: 0.0, y: 0.0),
(x: 1.0, y: 0.0),
(x: 1.0, y: 1.0),
(x: 0.0, y: 0.0),
],
vec![],
));
rtreed.push(Polygon::new(
line_string![
(x: 1.0, y: 1.0),
(x: 2.0, y: 1.0),
(x: 2.0, y: 2.0),
(x: 1.0, y: 1.0),
],
vec![],
));
// Locate the two polygons in the R-tree.
assert_eq!(
rtreed
.rtree()
.locate_in_envelope(AABB::from_corners(
Point::new(0.0, 0.0),
Point::new(2.0, 2.0),
))
.count(),
2
);
// Access a polygon by its index in the MultiPolygon.
assert_eq!(
rtreed.get(&0),
Some(&Polygon::new(
line_string![
(x: 0.0, y: 0.0),
(x: 1.0, y: 0.0),
(x: 1.0, y: 1.0),
(x: 0.0, y: 0.0),
],
vec![],
))
);
}
}We welcome issues and pull requests from anyone both to our repository on GitHub.
If you would like rstared to work with a new collection type, please make
a contribution to maplike, which
provides and implements the traits rstared relies on.
rstared is dual-licensed as under either of
at your option.
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in this work by you will be dual-licensed as described above, without any additional terms or conditions.