pub struct RTree<T, Params = DefaultParams> where
Params: RTreeParams,
T: RTreeObject, { /* private fields */ }Expand description
An n-dimensional r-tree data structure.
R-Trees
R-Trees are data structures containing multi-dimensional objects like points, rectangles or polygons. They are optimized for retrieving the nearest neighbor at any point.
R-trees can efficiently find answers to queries like “Find the nearest point of a polygon”,
“Find all police stations within a rectangle” or “Find the 10 nearest restaurants, sorted
by their distances”. Compared to a naive implementation for these scenarios that runs
in O(n) for n inserted elements, r-trees reduce this time to O(log(n)).
However, creating an r-tree is time consuming
and runs in O(n * log(n)). Thus, r-trees are suited best if many queries and only few
insertions are made. rstar also supports bulk loading,
which cuts down the constant factors when creating an r-tree significantly compared to
sequential insertions.
R-trees are also dynamic: points can be inserted and removed from an existing tree.
Partitioning heuristics
The inserted objects are internally partitioned into several boxes which should have small
overlap and volume. This is done heuristically. While the originally proposed heuristic focused
on fast insertion operations, the resulting r-trees were often suboptimally structured. Another
heuristic, called R*-tree (r-star-tree), was proposed to improve the tree structure at the cost of
longer insertion operations and is currently the crate’s only implemented
[insertion strategy].
Further reading
For more information refer to the wikipedia article.
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
crate::primitivesx module. Several primitives in the geo-types crate also
implement these traits.
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);
// &RTree implements IntoIterator!
for point in &tree {
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-tree’s internal layout. Refer to the RTreeParams trait for more information.
Defining methods generic over r-trees
If a library defines a method that should be generic over the r-tree type signature, make sure to include both type parameters like this:
pub fn generic_rtree_function<T, Params>(tree: &mut RTree<T, Params>)
where
T: RTreeObject,
Params: RTreeParams
{
// ...
}Otherwise, any user of generic_rtree_function would be forced to use
a tree with default parameters.
Runtime and Performance
The runtime of query operations (e.g. nearest neighbor or 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 carried out once for many points. In this case,
RTree::bulk_load will be considerably faster. Its 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 is as small as possible.
For the edge case that all elements are overlapping (e.g, one and the same element
is contained n times), the performance of most operations usually degrades to O(n).
(De)Serialization
Enable the serde feature for Serde support.
Implementations
sourceimpl<T> RTree<T> where
T: RTreeObject,
impl<T> RTree<T> where
T: RTreeObject,
sourcepub fn new() -> Self
pub fn new() -> Self
Creates a new, empty r-tree.
The created r-tree is configured with default parameters.
sourcepub fn bulk_load(elements: Vec<T>) -> Self
pub fn bulk_load(elements: Vec<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.
This method implements the overlap minimizing top-down bulk loading algorithm (OMT) as described in this paper by Lee and Lee (2003).
Runtime
Bulk loading runs in O(n * log(n)), where n is the number of loaded
elements.
sourceimpl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject,
impl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject,
sourcepub fn new_with_params() -> Self
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 and a usage example.
sourcepub fn bulk_load_with_params(elements: Vec<T>) -> Self
pub fn bulk_load_with_params(elements: Vec<T>) -> Self
Creates a new r-tree with some given elements and configurable parameters.
For more information refer to RTree::bulk_load and RTreeParams.
sourcepub fn size(&self) -> usize
pub fn size(&self) -> usize
Returns the number of objects in an r-tree.
Example
use rstar::RTree;
let mut tree = RTree::new();
assert_eq!(tree.size(), 0);
tree.insert([0.0, 1.0, 2.0]);
assert_eq!(tree.size(), 1);
tree.remove(&[0.0, 1.0, 2.0]);
assert_eq!(tree.size(), 0);sourcepub fn iter(&self) -> RTreeIterator<'_, T>
pub fn iter(&self) -> RTreeIterator<'_, T>
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(vec![(0.0, 0.1), (0.3, 0.2), (0.4, 0.2)]);
for point in tree.iter() {
println!("This tree contains point {:?}", point);
}sourcepub fn iter_mut(&mut self) -> RTreeIteratorMut<'_, T>
pub fn iter_mut(&mut self) -> RTreeIteratorMut<'_, T>
Returns an iterator over all mutable elements contained in the tree.
The order in which the elements are returned is not specified.
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 RTree::remove and reinsert it.
sourcepub fn locate_in_envelope(
&self,
envelope: &T::Envelope
) -> LocateInEnvelope<'_, T>
pub fn locate_in_envelope(
&self,
envelope: &T::Envelope
) -> LocateInEnvelope<'_, T>
Returns all elements contained in an Envelope.
Usually, an envelope is an axis aligned bounding box. This method can be used to retrieve all elements that are fully contained within an envelope.
Example
use rstar::{RTree, AABB};
let mut tree = RTree::bulk_load(vec![
[0.0, 0.0],
[0.0, 1.0],
[1.0, 1.0]
]);
let half_unit_square = AABB::from_corners([0.0, 0.0], [0.5, 1.0]);
let unit_square = AABB::from_corners([0.0, 0.0], [1.0, 1.0]);
let elements_in_half_unit_square = tree.locate_in_envelope(&half_unit_square);
let elements_in_unit_square = tree.locate_in_envelope(&unit_square);
assert_eq!(elements_in_half_unit_square.count(), 2);
assert_eq!(elements_in_unit_square.count(), 3);sourcepub fn locate_in_envelope_mut(
&mut self,
envelope: &T::Envelope
) -> LocateInEnvelopeMut<'_, T>
pub fn locate_in_envelope_mut(
&mut self,
envelope: &T::Envelope
) -> LocateInEnvelopeMut<'_, T>
Mutable variant of locate_in_envelope.
sourcepub fn drain_in_envelope(
&mut self,
envelope: T::Envelope
) -> DrainIterator<'_, T, SelectInEnvelopeFunction<T>, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
pub fn drain_in_envelope(
&mut self,
envelope: T::Envelope
) -> DrainIterator<'_, T, SelectInEnvelopeFunction<T>, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
Draining variant of locate_in_envelope.
sourcepub fn locate_in_envelope_intersecting(
&self,
envelope: &T::Envelope
) -> LocateInEnvelopeIntersecting<'_, T>
pub fn locate_in_envelope_intersecting(
&self,
envelope: &T::Envelope
) -> LocateInEnvelopeIntersecting<'_, T>
Returns all elements whose envelope intersects a given envelope.
Any element fully contained within an envelope is also returned by this method. Two envelopes that “touch” each other (e.g. by sharing only a common corner) are also considered to intersect. 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.
Example
use rstar::{RTree, AABB};
use rstar::primitives::Rectangle;
let left_piece = AABB::from_corners([0.0, 0.0], [0.4, 1.0]);
let right_piece = AABB::from_corners([0.6, 0.0], [1.0, 1.0]);
let middle_piece = AABB::from_corners([0.25, 0.0], [0.75, 1.0]);
let mut tree = RTree::<Rectangle<_>>::bulk_load(vec![
left_piece.into(),
right_piece.into(),
middle_piece.into(),
]);
let elements_intersecting_left_piece = tree.locate_in_envelope_intersecting(&left_piece);
// The left piece should not intersect the right piece!
assert_eq!(elements_intersecting_left_piece.count(), 2);
let elements_intersecting_middle = tree.locate_in_envelope_intersecting(&middle_piece);
// Only the middle piece intersects all pieces within the tree
assert_eq!(elements_intersecting_middle.count(), 3);
let large_piece = AABB::from_corners([-100., -100.], [100., 100.]);
let elements_intersecting_large_piece = tree.locate_in_envelope_intersecting(&large_piece);
// Any element that is fully contained should also be returned:
assert_eq!(elements_intersecting_large_piece.count(), 3);sourcepub fn locate_in_envelope_intersecting_mut(
&mut self,
envelope: &T::Envelope
) -> LocateInEnvelopeIntersectingMut<'_, T>
pub fn locate_in_envelope_intersecting_mut(
&mut self,
envelope: &T::Envelope
) -> LocateInEnvelopeIntersectingMut<'_, T>
Mutable variant of locate_in_envelope_intersecting
sourcepub fn locate_with_selection_function<S: SelectionFunction<T>>(
&self,
selection_function: S
) -> SelectionIterator<'_, T, S>ⓘNotable traits for SelectionIterator<'a, T, Func>impl<'a, T, Func> Iterator for SelectionIterator<'a, T, Func> where
T: RTreeObject,
Func: SelectionFunction<T>, type Item = &'a T;
pub fn locate_with_selection_function<S: SelectionFunction<T>>(
&self,
selection_function: S
) -> SelectionIterator<'_, T, S>ⓘNotable traits for SelectionIterator<'a, T, Func>impl<'a, T, Func> Iterator for SelectionIterator<'a, T, Func> where
T: RTreeObject,
Func: SelectionFunction<T>, type Item = &'a T;
T: RTreeObject,
Func: SelectionFunction<T>, type Item = &'a T;
Locates elements in the r-tree defined by a selection function.
Refer to the documentation of SelectionFunction for
more information.
Usually, other locate methods should cover most common use cases. This method is only required
in more specific situations.
sourcepub fn locate_with_selection_function_mut<S: SelectionFunction<T>>(
&mut self,
selection_function: S
) -> SelectionIteratorMut<'_, T, S>ⓘNotable traits for SelectionIteratorMut<'a, T, Func>impl<'a, T, Func> Iterator for SelectionIteratorMut<'a, T, Func> where
T: RTreeObject,
Func: SelectionFunction<T>, type Item = &'a mut T;
pub fn locate_with_selection_function_mut<S: SelectionFunction<T>>(
&mut self,
selection_function: S
) -> SelectionIteratorMut<'_, T, S>ⓘNotable traits for SelectionIteratorMut<'a, T, Func>impl<'a, T, Func> Iterator for SelectionIteratorMut<'a, T, Func> where
T: RTreeObject,
Func: SelectionFunction<T>, type Item = &'a mut T;
T: RTreeObject,
Func: SelectionFunction<T>, type Item = &'a mut T;
Mutable variant of locate_with_selection_function.
sourcepub fn intersection_candidates_with_other_tree<'a, U>(
&'a self,
other: &'a RTree<U>
) -> IntersectionIterator<'_, T, U>ⓘNotable traits for IntersectionIterator<'a, T, U>impl<'a, T, U> Iterator for IntersectionIterator<'a, T, U> where
T: RTreeObject,
U: RTreeObject<Envelope = T::Envelope>, type Item = (&'a T, &'a U); where
U: RTreeObject<Envelope = T::Envelope>,
pub fn intersection_candidates_with_other_tree<'a, U>(
&'a self,
other: &'a RTree<U>
) -> IntersectionIterator<'_, T, U>ⓘNotable traits for IntersectionIterator<'a, T, U>impl<'a, T, U> Iterator for IntersectionIterator<'a, T, U> where
T: RTreeObject,
U: RTreeObject<Envelope = T::Envelope>, type Item = (&'a T, &'a U); where
U: RTreeObject<Envelope = T::Envelope>,
T: RTreeObject,
U: RTreeObject<Envelope = T::Envelope>, type Item = (&'a T, &'a U);
Returns all possible intersecting objects of this and another tree.
This will return all objects whose envelopes intersect. No geometric intersection checking is performed.
sourcepub fn root(&self) -> &ParentNode<T>
pub fn root(&self) -> &ParentNode<T>
Returns the tree’s root node.
Usually, you will not need to call this method. However, for debugging purposes or for advanced algorithms, knowledge about the tree’s internal structure may be required. For these cases, this method serves as an entry point.
sourcepub fn remove_with_selection_function<F>(&mut self, function: F) -> Option<T> where
F: SelectionFunction<T>,
pub fn remove_with_selection_function<F>(&mut self, function: F) -> Option<T> where
F: SelectionFunction<T>,
Removes and returns a single element from the tree. The element to remove is specified
by a SelectionFunction.
See also: RTree::remove, RTree::remove_at_point
sourcepub fn drain_with_selection_function<F>(
&mut self,
function: F
) -> DrainIterator<'_, T, F, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T; where
F: SelectionFunction<T>,
pub fn drain_with_selection_function<F>(
&mut self,
function: F
) -> DrainIterator<'_, T, F, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T; where
F: SelectionFunction<T>,
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
Drain elements selected by a SelectionFunction. Returns an
iterator that successively removes selected elements and returns
them. This is the most generic drain API, see also:
RTree::drain_in_envelope_intersecting,
RTree::drain_within_distance.
Remarks
This API is similar to Vec::drain_filter, but stopping the
iteration would stop the removal. However, the returned iterator
must be properly dropped. Leaking this iterator leads to a leak
amplification, where all the elements in the tree are leaked.
sourcepub fn drain_in_envelope_intersecting(
&mut self,
envelope: T::Envelope
) -> DrainIterator<'_, T, SelectInEnvelopeFuncIntersecting<T>, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
pub fn drain_in_envelope_intersecting(
&mut self,
envelope: T::Envelope
) -> DrainIterator<'_, T, SelectInEnvelopeFuncIntersecting<T>, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
Drains elements intersecting the envelope. Similar to
locate_in_envelope_intersecting, except the elements are removed
and returned via an iterator.
sourceimpl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: PointDistance,
impl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: PointDistance,
sourcepub fn locate_at_point(
&self,
point: &<T::Envelope as Envelope>::Point
) -> Option<&T>
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.
sourcepub fn locate_at_point_mut(
&mut self,
point: &<T::Envelope as Envelope>::Point
) -> Option<&mut T>
pub fn locate_at_point_mut(
&mut self,
point: &<T::Envelope as Envelope>::Point
) -> Option<&mut T>
Mutable variant of RTree::locate_at_point.
sourcepub fn locate_all_at_point(
&self,
point: &<T::Envelope as Envelope>::Point
) -> LocateAllAtPoint<'_, T>
pub fn locate_all_at_point(
&self,
point: &<T::Envelope as Envelope>::Point
) -> LocateAllAtPoint<'_, T>
Locate all elements containing a given point.
Method PointDistance::contains_point is used to determine if a tree element contains the given point.
Example
use rstar::RTree;
use rstar::primitives::Rectangle;
let tree = RTree::bulk_load(vec![
Rectangle::from_corners([0.0, 0.0], [2.0, 2.0]),
Rectangle::from_corners([1.0, 1.0], [3.0, 3.0])
]);
assert_eq!(tree.locate_all_at_point(&[1.5, 1.5]).count(), 2);
assert_eq!(tree.locate_all_at_point(&[0.0, 0.0]).count(), 1);
assert_eq!(tree.locate_all_at_point(&[-1., 0.0]).count(), 0);sourcepub fn locate_all_at_point_mut(
&mut self,
point: &<T::Envelope as Envelope>::Point
) -> LocateAllAtPointMut<'_, T>
pub fn locate_all_at_point_mut(
&mut self,
point: &<T::Envelope as Envelope>::Point
) -> LocateAllAtPointMut<'_, T>
Mutable variant of locate_all_at_point.
sourcepub fn remove_at_point(
&mut self,
point: &<T::Envelope as Envelope>::Point
) -> Option<T>
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.
Example
use rstar::RTree;
use rstar::primitives::Rectangle;
let mut tree = RTree::bulk_load(vec![
Rectangle::from_corners([0.0, 0.0], [2.0, 2.0]),
Rectangle::from_corners([1.0, 1.0], [3.0, 3.0])
]);
assert!(tree.remove_at_point(&[1.5, 1.5]).is_some());
assert!(tree.remove_at_point(&[1.5, 1.5]).is_some());
assert!(tree.remove_at_point(&[1.5, 1.5]).is_none());sourceimpl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject + PartialEq,
impl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject + PartialEq,
sourcepub fn contains(&self, t: &T) -> bool
pub fn contains(&self, t: &T) -> bool
Returns true if a given element is equal (==) to an element in the
r-tree.
This method will only work correctly if two equal elements also have the same envelope.
Example
use rstar::RTree;
let mut tree = RTree::new();
assert!(!tree.contains(&[0.0, 2.0]));
tree.insert([0.0, 2.0]);
assert!(tree.contains(&[0.0, 2.0]));sourcepub fn remove(&mut self, t: &T) -> Option<T>
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.
This method will only work correctly if two equal elements also have the same envelope.
Example
use rstar::RTree;
let mut tree = RTree::new();
tree.insert([0.0, 2.0]);
// The element can be inserted twice just fine
tree.insert([0.0, 2.0]);
assert!(tree.remove(&[0.0, 2.0]).is_some());
assert!(tree.remove(&[0.0, 2.0]).is_some());
assert!(tree.remove(&[0.0, 2.0]).is_none());sourceimpl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: PointDistance,
impl<T, Params> RTree<T, Params> where
Params: RTreeParams,
T: PointDistance,
sourcepub fn nearest_neighbor(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> Option<&T>
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
Example
use rstar::RTree;
let tree = RTree::bulk_load(vec![
[0.0, 0.0],
[0.0, 1.0],
]);
assert_eq!(tree.nearest_neighbor(&[-1., 0.0]), Some(&[0.0, 0.0]));
assert_eq!(tree.nearest_neighbor(&[0.0, 2.0]), Some(&[0.0, 1.0]));sourcepub fn nearest_neighbors(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> Vec<&T>
pub fn nearest_neighbors(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> Vec<&T>
Returns the nearest neighbors for a given point.
The distance is calculated by calling PointDistance::distance_2
All returned values will have the exact same distance from the given query point.
Returns an empty Vec if the tree is empty.
Example
use rstar::RTree;
let tree = RTree::bulk_load(vec![
[0.0, 0.0],
[0.0, 1.0],
[1.0, 0.0],
]);
assert_eq!(tree.nearest_neighbors(&[1.0, 1.0]), &[&[0.0, 1.0], &[1.0, 0.0]]);
assert_eq!(tree.nearest_neighbors(&[0.01, 0.01]), &[&[0.0, 0.0]]);sourcepub fn locate_within_distance(
&self,
query_point: <T::Envelope as Envelope>::Point,
max_squared_radius: <<T::Envelope as Envelope>::Point as Point>::Scalar
) -> LocateWithinDistanceIterator<'_, T>
pub fn locate_within_distance(
&self,
query_point: <T::Envelope as Envelope>::Point,
max_squared_radius: <<T::Envelope as Envelope>::Point as Point>::Scalar
) -> LocateWithinDistanceIterator<'_, T>
Returns all elements of the tree within a certain distance.
The elements may be returned in any order. Each returned element will have a squared distance less or equal to the given squared distance.
This method makes use of PointDistance::distance_2_if_less_or_equal. If performance is critical and the distance calculation to the object is fast, overwriting this function may be beneficial.
sourcepub fn drain_within_distance(
&mut self,
query_point: <T::Envelope as Envelope>::Point,
max_squared_radius: <<T::Envelope as Envelope>::Point as Point>::Scalar
) -> DrainIterator<'_, T, SelectWithinDistanceFunction<T>, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
pub fn drain_within_distance(
&mut self,
query_point: <T::Envelope as Envelope>::Point,
max_squared_radius: <<T::Envelope as Envelope>::Point as Point>::Scalar
) -> DrainIterator<'_, T, SelectWithinDistanceFunction<T>, Params>ⓘNotable traits for DrainIterator<'a, T, R, Params>impl<'a, T, R, Params> Iterator for DrainIterator<'a, T, R, Params> where
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
T: RTreeObject,
Params: RTreeParams,
R: SelectionFunction<T>, type Item = T;
Drain all elements of the tree within a certain distance.
Similar to RTree::locate_within_distance, but removes and
returns the elements via an iterator.
sourcepub fn nearest_neighbor_iter(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> NearestNeighborIterator<'_, T>
pub fn nearest_neighbor_iter(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> NearestNeighborIterator<'_, 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.
Example
use rstar::RTree;
let tree = RTree::bulk_load(vec![
[0.0, 0.0],
[0.0, 1.0],
]);
let nearest_neighbors = tree.nearest_neighbor_iter(&[0.5, 0.0]).collect::<Vec<_>>();
assert_eq!(nearest_neighbors, vec![&[0.0, 0.0], &[0.0, 1.0]]);sourcepub fn nearest_neighbor_iter_with_distance(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> NearestNeighborDistance2Iterator<'_, T>
👎 Deprecated: Please use nearest_neighbor_iter_with_distance_2 instead
pub fn nearest_neighbor_iter_with_distance(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> NearestNeighborDistance2Iterator<'_, T>
Please use nearest_neighbor_iter_with_distance_2 instead
Returns (element, distance^2) tuples of the tree sorted by their distance to a given point.
The distance is calculated by calling PointDistance::distance_2.
sourcepub fn nearest_neighbor_iter_with_distance_2(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> NearestNeighborDistance2Iterator<'_, T>
pub fn nearest_neighbor_iter_with_distance_2(
&self,
query_point: &<T::Envelope as Envelope>::Point
) -> NearestNeighborDistance2Iterator<'_, T>
Returns (element, distance^2) tuples of the tree sorted by their distance to a given point.
The distance is calculated by calling PointDistance::distance_2.
sourcepub fn pop_nearest_neighbor(
&mut self,
query_point: &<T::Envelope as Envelope>::Point
) -> Option<T>
pub fn pop_nearest_neighbor(
&mut self,
query_point: &<T::Envelope as Envelope>::Point
) -> Option<T>
Removes the nearest neighbor for a given point and returns it.
The distance is calculated by calling PointDistance::distance_2.
Example
use rstar::RTree;
let mut tree = RTree::bulk_load(vec![
[0.0, 0.0],
[0.0, 1.0],
]);
assert_eq!(tree.pop_nearest_neighbor(&[0.0, 0.0]), Some([0.0, 0.0]));
assert_eq!(tree.pop_nearest_neighbor(&[0.0, 0.0]), Some([0.0, 1.0]));
assert_eq!(tree.pop_nearest_neighbor(&[0.0, 0.0]), None);sourceimpl<T, Params> RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
impl<T, Params> RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
sourcepub fn insert(&mut self, t: T)
pub fn insert(&mut self, t: T)
Inserts a new element into the r-tree.
If the element is already 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.
Trait Implementations
sourceimpl<T: Clone, Params: Clone> Clone for RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject,
impl<T: Clone, Params: Clone> Clone for RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject,
sourceimpl<T, Params> Debug for RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject + Debug,
impl<T, Params> Debug for RTree<T, Params> where
Params: RTreeParams,
T: RTreeObject + Debug,
sourceimpl<T, Params> Default for RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
impl<T, Params> Default for RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
sourceimpl<'a, T, Params> IntoIterator for &'a RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
impl<'a, T, Params> IntoIterator for &'a RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
sourceimpl<'a, T, Params> IntoIterator for &'a mut RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
impl<'a, T, Params> IntoIterator for &'a mut RTree<T, Params> where
T: RTreeObject,
Params: RTreeParams,
Auto Trait Implementations
impl<T, Params> RefUnwindSafe for RTree<T, Params> where
Params: RefUnwindSafe,
T: RefUnwindSafe,
<T as RTreeObject>::Envelope: RefUnwindSafe,
impl<T, Params> Send for RTree<T, Params> where
T: Send,
<T as RTreeObject>::Envelope: Send,
impl<T, Params> Sync for RTree<T, Params> where
T: Sync,
<T as RTreeObject>::Envelope: Sync,
impl<T, Params> Unpin for RTree<T, Params> where
Params: Unpin,
T: Unpin,
<T as RTreeObject>::Envelope: Unpin,
impl<T, Params> UnwindSafe for RTree<T, Params> where
Params: UnwindSafe,
T: UnwindSafe,
<T as RTreeObject>::Envelope: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for T where
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Mutably borrows from an owned value. Read more
sourceimpl<T> ToOwned for T where
T: Clone,
impl<T> ToOwned for T where
T: Clone,
type Owned = T
type Owned = T
The resulting type after obtaining ownership.
sourcefn clone_into(&self, target: &mut T)
fn clone_into(&self, target: &mut T)
toowned_clone_into)Uses borrowed data to replace owned data, usually by cloning. Read more