Crate rstared

Expand description

§rstared

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.

§Supported collections

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.

§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;

§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.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.

§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. 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
    );
}

§`HashMap` example

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.

§Generational arena example

See examples/thunderdome.rs for a usage example involving two polygons stored in thunderdome::Arena, a generational arena.

§`MultiPolygon` example

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![],
        ))
    );
}
}

§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

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.

Re-exports§

pub use maplike;

Modules§

iterators: Iterator types
mintmint: mint is a library for interoperability between maths crates, for example, you may want to use nalgebra types for representing your points and also use the same points with the rstar library.
primitives: Contains primitives ready for insertion into an r-tree.

Structs§

AABB: An n-dimensional axis aligned bounding box (AABB).
DefaultParams: The default parameters used when creating an r-tree without specific parameters.
ParentNode: Represents an internal parent node.
RTree: An n-dimensional r-tree data structure.
RTreed

Enums§

RStarInsertionStrategy: Inserts points according to the r-star heuristic.
RTreeNode: An internal tree node.

Traits§

Envelope: An envelope type that encompasses some child nodes.
InsertionStrategy: Defines how points are inserted into an r-tree.
Point: Defines a point type that is compatible with rstar.
PointDistance: Defines objects which can calculate their minimal distance to a point.
RTreeNum: Defines a number type that is compatible with rstar.
RTreeObject: An object that can be inserted into an r-tree.
RTreeParams: Defines static parameters for an r-tree.
SelectionFunction: Advanced trait to iterate through an r-tree. Usually it should not be required to be implemented.

Type Aliases§

RTreeDeltaundoredo: Delta for RTree<K>. Alias for Delta<RTreeHalfDelta<K>>.
RTreeHalfDeltaundoredo: Half-delta for RTree<K>. Alias for BTreeMap<K, ()>.
RTreedDeltaundoredo: Delta for RTreed<C>. Alias for Delta<RTreedHalfDelta<K, V>>.
RTreedHalfDeltaundoredo: Half-delta for RTreed<C>. Alias for BTreeMap<K, V>.

Crate rstared

Crate rstared Copy item path

§rstared

§Supported collections

§Standard library

§Third-party types

§Usage

§Adding dependency

§Usage examples

§Vec example

§HashMap example

§Generational arena example

§MultiPolygon example

§Contributing

§Licence

§Outbound licence

§Inbound licence

Re-exports§

Modules§

Structs§

Enums§

Traits§

Type Aliases§

Crate rstared

§`Vec` example

§`HashMap` example

§`MultiPolygon` example