Struct rstar::RTree

pub struct RTree<T, Params = DefaultParams>where
    Params: RTreeParams,
    T: RTreeObject,{ /* private fields */ }

An n-dimensional r-tree data structure.

R-Trees

R-trees are tree data structures for multi dimensional data which support efficient insertion operations and nearest neighbor queries. Also, other types of queries, like retrieving all objects within a rectangle or a circle, can be implemented efficiently.

Usage

The items inserted into an r-tree must implement the RTreeObject trait. To support nearest neighbor queries, implement the PointDistance trait. Some useful geometric primitives that implement the above traits can be found in the primitives module.

Example

use rstar::RTree;

let mut tree = RTree::new();
tree.insert([0.1, 0.0f32]);
tree.insert([0.2, 0.1]);
tree.insert([0.3, 0.0]);

assert_eq!(tree.nearest_neighbor(&[0.4, -0.1]), Some(&[0.3, 0.0]));
tree.remove(&[0.3, 0.0]);
assert_eq!(tree.nearest_neighbor(&[0.4, 0.3]), Some(&[0.2, 0.1]));

assert_eq!(tree.size(), 2);
for point in tree.iter() {
    println!("Tree contains a point {:?}", point);
}

Supported point types

All types implementing the Point trait can be used as underlying point type. By default, fixed size arrays can be used as points.

Type Parameters

• T: The type of objects stored in the r-tree.
• Params: Compile time parameters that change the r-trees internal layout. Refer to the RTreeParams trait for more information.

Runtime and Performance

The runtime of query operations (nearest neighbor queries, contains) is usually O(log(n)), where n refers to the number of elements contained in the r-tree. A naive sequential algorithm would take O(n) time. However, r-trees incur higher build up times: inserting an element into an r-tree costs O(log(n)) time.

Bulk loading

In many scenarios, insertion is only done once for many points. In this case, bulk_load will be considerably faster. It’s total run time is still O(log(n)).

Element distribution

The tree’s performance heavily relies on the spatial distribution of its elements. Best performance is achieved if:

• No element is inserted more than once
• The overlapping area of elements should be as small a possible.

Implementations

impl<T> RTree<T>where
    T: RTreeObject,

pub fn new() -> Self

Creates a new, empty r-tree.

The created r-tree is configured with default parameters.

impl<T, Params> RTree<T, Params>where
    Params: RTreeParams,
    T: RTreeObject,

pub fn new_with_params() -> Self

Creates a new, empty r-tree.

The tree’s compile time parameters must be specified. Refer to the RTreeParams trait for more information.

pub fn size(&self) -> usize

Returns the number of objects in an r-tree.

pub fn iter(&self) -> SelectionIterator<'_, T, SelectAllFunc>

Returns an iterator over all elements contained in the tree.

The order in which the elements are returned is not specified.

Example

use rstar::RTree;
let tree = RTree::bulk_load(&mut[[0.0, 0.1], [0.3, 0.2], [0.4, 0.2]]);
for point in tree.iter() {
    println!("This tree contains point {:?}", point);
}

pub fn iter_mut(&mut self) -> SelectionIteratorMut<'_, T, SelectAllFunc>

Returns an iterator over all mutable elements contained in the tree.nearest_neighbor

The order in which the elements are returned is not specified.nearest_neighbor

Note: It is a logic error to change an inserted item’s position or dimensions. This method is primarily meant for own implementations of RTreeObject which can contain arbitrary additional data. If the position or location of an inserted object need to change, you will need to [remove] and reinsert it.

pub fn locate_in_envelope(
    &self,
    envelope: &T::Envelope
) -> SelectionIterator<'_, T, SelectInEnvelopeFunction<T>>

Returns all elements contained in an Envelope.

Usually, an envelope is an axis aligned bounding box. This method can be used to get all elements that are fully contained within an aabb.

pub fn locate_in_envelope_mut(
    &mut self,
    envelope: &T::Envelope
) -> SelectionIteratorMut<'_, T, SelectInEnvelopeFunction<T>>

Mutable variant of [locate_in_envelope_mut].

pub fn locate_in_envelope_intersecting(
    &self,
    envelope: &T::Envelope
) -> SelectionIterator<'_, T, SelectInEnvelopeFuncIntersecting<T>>

Returns all elements whose envelope intersects a given envelope.

Usually, an envelope is an axis aligned bounding box. This method will return all elements whose AABB has some common area with a given AABB.

pub fn locate_in_envelope_intersecting_mut(
    &mut self,
    envelope: &T::Envelope
) -> SelectionIteratorMut<'_, T, SelectInEnvelopeFuncIntersecting<T>>

Mutable variant of [#method.locate_in_envelope_intersecting]

impl<T, Params> RTree<T, Params>where
    Params: RTreeParams,
    T: PointDistance,

pub fn locate_at_point(
    &self,
    point: &<T::Envelope as Envelope>::Point
) -> Option<&T>

Returns a single object that covers a given point.

Method contains_point is used to determine if a tree element contains the given point.

If multiple elements contain the given point, any of them is returned.

pub fn locate_at_point_mut(
    &mut self,
    point: &<T::Envelope as Envelope>::Point
) -> Option<&mut T>

Mutable variant of locate_at_point.

pub fn locate_all_at_point(
    &self,
    point: &<T::Envelope as Envelope>::Point
) -> SelectionIterator<'_, T, SelectAtPointFunction<T>>

Locate all elements containing a given point.

Method contains_point is used to determine if a tree element contains the given point.

pub fn locate_all_at_point_mut(
    &mut self,
    point: &<T::Envelope as Envelope>::Point
) -> SelectionIteratorMut<'_, T, SelectAtPointFunction<T>>

Mutable variant of locate_at_point_mut.

pub fn remove_at_point(
    &mut self,
    point: &<T::Envelope as Envelope>::Point
) -> Option<T>

Removes an element containing a given point.

The removed element, if any, is returned. If multiple elements cover the given point, only one of them is removed and returned.

impl<T, Params> RTree<T, Params>where
    Params: RTreeParams,
    T: RTreeObject + PartialEq,

pub fn contains(&self, t: &T) -> bool

Returns true if a given element is equal (==) to an element in the r-tree.

pub fn remove(&mut self, t: &T) -> Option<T>

Removes and returns an element of the r-tree equal (==) to a given element.

If multiple elements equal to the given elements are contained in the tree, only one of them is removed and returned.

impl<T, Params> RTree<T, Params>where
    Params: RTreeParams,
    T: PointDistance,

pub fn nearest_neighbor(
    &self,
    query_point: &<T::Envelope as Envelope>::Point
) -> Option<&T>

Returns the nearest neighbor for a given point.

The distance is calculated by calling PointDistance::distance_2

pub fn nearest_neighbor_iter(
    &self,
    query_point: &<T::Envelope as Envelope>::Point
) -> impl Iterator<Item = &T>

Returns all elements of the tree sorted by their distance to a given point.

Runtime

Every next() call runs in O(log(n)). Creating the iterator runs in O(log(n)). The r-tree documentation contains more information about r-tree performance.

impl<T, Params> RTree<T, Params>where
    T: RTreeObject,
    Params: RTreeParams,

pub fn insert(&mut self, t: T)

Inserts a new element into the r-tree.

If the element has already been present in the tree, it will now be present twice.

Runtime

This method runs in O(log(n)). The r-tree documentation contains more information about r-tree performance.

impl<T, Params> RTree<T, Params>where
    T: RTreeObject + Clone,
    <T::Envelope as Envelope>::Point: Point,
    Params: RTreeParams,

pub fn bulk_load_with_params(elements: &mut [T]) -> Self

Creates a new r-tree with some given elements and configurable parameters.

For more information refer to bulk_load_with_params and RTreeParameters.

impl<T> RTree<T>where
    T: RTreeObject + Clone,
    <T::Envelope as Envelope>::Point: Point,

pub fn bulk_load(elements: &mut [T]) -> Self

Creates a new r-tree with some elements already inserted.

This method should be the preferred way for creating r-trees. It both runs faster and yields an r-tree with better internal structure that improves query performance.

Trait Implementations

impl<T: Clone, Params: Clone> Clone for RTree<T, Params>where
    Params: RTreeParams,
    T: RTreeObject,

fn clone(&self) -> RTree<T, Params>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T, Params> Debug for RTree<T, Params>where
    Params: RTreeParams,
    T: RTreeObject + Debug,

fn fmt(&self, formatter: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Default for RTree<T>where
    T: RTreeObject,

fn default() -> Self

Returns the “default value” for a type.