rstared

rstared::RTreed is a simple Rust decorator that adds a passively listening R-tree, rstar::RTree, to a large number of common standard library and third-party collection types.

Supported collections

Standard library

• HashMap, gated by the std feature (enabled by default);
• HashSet, gated by the std feature (enabled by default);
• BTreeMap, not feature-gated;
• BTreeSet, not feature-gated;
• Vec, not feature-gated;
• VecDeque, not feature-gated.

Third-party types

• bidimap::BiBTreeMap, gated by the bidimap feature, and bidimap::BiHashMap, which is additionally gated by the std feature;
• indexmap::IndexMap and indexmap::IndexSet, gated by the indexmap feature;
• rstar::RTree, not feature-gated;
• stable_vec::StableVec, gated by the stable-vec feature;
• thunderdome::Arena, gated by the thunderdome feature;
• arrayvec::ArrayVec, gated by the arrayvec feature;
• smallvec::SmallVec, gated by the smallvec feature;
• tinyvec::ArrayVec and tinyvec::TinyVec, gated by the tinyvec feature;
• geometry types from geo/geo-types: LineString, MultiPoint, MultiLineString, MultiPolygon, and GeometryCollection gated by the geo feature;

This library is no_std-compatible and has no mandatory third-party dependencies except for alloc.

Usage

Adding dependency

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.14.1", features = [
    "arrayvec",
    "bidimap",
    "geo",
    "indexmap",
    "smallvec",
    "stable-vec",
    "thunderdome",
    "tinyvec",
] }

For the sake of demonstration, all feature flags are enabled in that snippet. Remove those you don't need.

Usage examples

Vec example

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:

use rstar::{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)))
    );
}

HashMap example

Because Vec invalidates indices upon removal, there is no .remove() method available for RTreed<Vec<...>. If you want to dynamically remove elements, you can use a type with stable keys, such as Rust standard library's HashMap and BTreeMap, like this:

let rect_vec: HashMap<Rectangle<(i32, i32)>> = Vec::new();
let mut rtreed = RTreed::new(rect_vec);

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.

MultiPolygon example

Following is a usage example on geo's MultiPolygon (examples/multipolygon.rs). To wrap RTreed over MultiPolygon, you need to enable the rstar_0_13 feature on geo-types, so that its element type, Polygon, implements RTreeObject:

use geo_types::{MultiPolygon, Point, Polygon, line_string};
use rstar::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![],
        ))
    );
}

Contributing

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.

Licence

Outbound licence

rstared is dual-licensed as under either of

• MIT license,
• Apache License, Version 2.0,

at your option.

Inbound licence

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.