Struct spade::rtree::RTree

pub struct RTree<T>where
    T: SpatialObject,{ /* private fields */ }

A rust implementation of n dimensional r*-trees

R-trees provide efficient nearest-neighbor searches for many objects. R*-trees ("R-Star-Trees") are a common variant of r-trees and use more advanced heuristics to improve query performance. Instead of linear time complexity, r-trees yield logarithmic complexity for look-up operations and nearest neighbor queries. Inserting into an r-tree runs in O(log(n)) time on average. Also, a bulk loading algorithm is implemented for faster and higher quality tree creation. Some simple geometric primitives that can be inserted into an r-tree can be found in the primitives module. If your object is not among those, consider implementing the SpatialObject trait.

use nalgebra::{Point4};
use spade::rtree::RTree;

  let mut tree = RTree::new();
  tree.insert(Point4::new(13i32, 10, 10, 37));

Basic Example

extern crate cgmath; // Alternatively: use nalgebra or [f32; 2]
extern crate spade;

use spade::rtree::RTree;
use cgmath::Point2;

fn main() {
let mut rtree = RTree::new();
// Insert two points
rtree.insert(Point2::new(0.5, 0.5f32));
rtree.insert(Point2::new(1.0, 1.0f32));

if rtree.lookup(&Point2::new(0.5, 0.5)).is_some() {
  println!("Found point at [0.5, 0.5]/");
}
 
let nearest = rtree.nearest_neighbor(&Point2::new(1.5, 1.5)).unwrap();
println!("nearest neighbor at [1.5, 1.5]: {:?}", nearest);

// Iterate over all elements
for point in rtree.iter() {
  println!("Found point: {:?}", point);
}
}

Implementations

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

pub fn new() -> RTree<T>

Creates an empty r*-tree.

pub fn mbr(&self) -> Option<BoundingRect<T::Point>>

Returns the trees minimal bounding box.

pub fn size(&self) -> usize

Returns the number of elements contained in this r-tree.

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

Returns an iterator over all contained elements.

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

Returns the nearest neighbor.

Returns None if the tree is empty.

pub fn close_neighbor(&self, point: &T::Point) -> Option<&T>

Returns an object close to a given point. This operation is faster than nearest_neighbor but will not neccessarily yield the real nearest neighbor.

pub fn nearest_neighbors(&self, query_point: &T::Point) -> Vec<&T>

Returns the nearest neighbors of a given point.

All returned values will have the exact same distance from the given query point. Returns an empty Vec if the tree is empty.

pub fn nearest_n_neighbors(&self, query_point: &T::Point, n: usize) -> Vec<&T>

Returns the nearest n neighbors.

pub fn nearest_neighbor_iterator(
    &self,
    query_point: &T::Point
) -> NearestNeighborIterator<'_, T>

Returns an iterator over the nearest neighbors of a point.

pub fn lookup_in_rectangle(&self, query_rect: &BoundingRect<T::Point>) -> Vec<&T>

Returns all objects (partially) contained in a rectangle

pub fn lookup_in_circle(
    &self,
    circle_origin: &T::Point,
    radius2: &<T::Point as PointN>::Scalar
) -> Vec<&T>

Returns all objects (partially) contained in a circle.

Note that radius2 is the circle’s squared radius, not the actual radius. An object is contained if a part of it lies within the circle.

impl<T> RTree<T>where
    T: SpatialObject + Clone,
    T::Point: TwoDimensional,

pub fn bulk_load(elements: Vec<T>) -> RTree<T>

Creates a new rtree with some initial elements.

This method should run faster than inserting all elements sequentially. Also, the resulting rtree should have better quality in terms of query performance. This is an implementation of the OMT algorithm.

The current implementation only works for two dimensional data.

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

pub fn lookup(&self, query_point: &T::Point) -> Option<&T>

Searches for an element at a given position.

If query_point is contained by one object in the tree, this object will be returned. If multiple objects contain the point, only one of them will be returned.

pub fn lookup_mut(&mut self, query_point: &T::Point) -> Option<&mut T>

Searches for an element at a given position and returns a mutable reference. If query_point is contained by multiple objects in the tree, one of them will be returned. Do not change the object’s minimal bounding box.

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

Inserts a new element into the tree.

This will require O(log(n)) operations on average, where n is the number of elements contained in the tree.

pub fn lookup_and_remove(&mut self, query_point: &T::Point) -> Option<T>

Searches for an element and removes it.

If the given point is contained by one object in the tree, this object is being removed and returned. If the point is contained by multiple objects, only one of them is removed and returned.

impl<T> RTree<T>where
    T: SpatialObject + PartialEq,

pub fn remove(&mut self, obj: &T) -> bool

Removes an object from the tree.

Locates and removes an object from the tree, returning true if the element could be removed. If multiple object’s are equal to to_remove, only one will be deleted.

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

Returns true if a given object is contained in this tree.

Trait Implementations

impl<T: Clone> Clone for RTree<T>where
    T: SpatialObject,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T> Debug for RTree<T>where
    T: SpatialObject + Debug,

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

Formats the value using the given formatter.

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

fn default() -> RTree<T>

Returns the “default value” for a type.

impl<T: PointN> DelaunayLocateStructure<T> for RTree<VertexEntry<T>>

fn insert_vertex_entry(&mut self, entry: VertexEntry<T>)

This method is called when a new vertex entry has been inserted.

fn update_vertex_entry(&mut self, new_entry: VertexEntry<T>)

This method is called when a vertex has been updated.

fn remove_vertex_entry(&mut self, to_remove: &VertexEntry<T>)

This method is callend when a vertex has been removed.

fn find_close_handle(&self, point: &T) -> FixedVertexHandle

Returns, if possible, a vertex handle that is close to the given point.

fn new_query_result(&self, _: FixedVertexHandle)

Notifies the locate structure about the result of a query.