Struct crater::kdtree::KdTree

pub struct KdTree<R: KdRegion, V = ()> {
    pub bounds: Option<R>,
    /* private fields */
}

A KD tree represents a collection of points in space, with the ability to answer distance related queries, mainly:

• What are the k closest points to a given point? (The first k points in the tree, ordered by increasing squared distance from the given point, including the given point if it is in the tree). (Sometimes called a nearest neighbors query)
• What are all the points within a distance d of a given point? (All points whose squared distance from a given point is at most d^2). (Sometimes called a ball query)
• What are all the points within a given region? (Sometimes called a cuboid query) This implementation uses an implicit tree, meaning all points are stored in one contiguous buffer and no dereferences are needed to traverse the tree. This is good for lookup performance, but unfortunately it means that adding/removing points can’t be done currently without rebuilding the tree. Besides the three basic distance related queries, KD trees can be used to some extent to help with more complicated distance related queries, like finding the closest pairs of points.

Fields

bounds: Option<R>

Implementations

impl<R: KdRegion, V> KdTree<R, V>

pub fn len(&self) -> usize

Get the number of points in the kdtree

pub fn walk<'a>( &'a self, visitor: &mut impl FnMut(&R, &'a R::Point, &'a V) -> WalkDecision )

Iterate over all point, value pairs in the tree in depth first order, calling a visitor function on each. The visitor function gets a const reference to the point, the value, and the bounds of the subtree corresponding to the point, and may return a WalkDecision to instruct the traversal to skip the subtree or to stop the traversal entirely.

pub fn walk_mut<'a>( &'a mut self, visitor: &mut impl FnMut(&R, &'a R::Point, &mut V) -> WalkDecision )

Iterate over all point, value pairs in the tree in depth first order, calling a visitor function on each. The visitor function gets a mutable reference to the value, but a const reference to the point and the bounds of the subtree corresponding to the point, and may return a WalkDecision to instruct the traversal to skip the subtree or to stop the traversal entirely.

pub fn k_closest<'a>( &'a self, point: &R::Point, k: usize, cfg: QueryOptions<'a, R> ) -> MmHeap<(&'a R::Point, &'a V)>

Return the k points in the tree which are the closest to a given point. Behavior can be fine-tuned using cfg:

• Can restrict the result set to only include points within a certain sqdist of the query point or withn a certain region, as well as to exclude points within another smaller sqdist or subregion.
• Can specify how any points tied for kth closest should be handled (keep all or keep one arbitrarily). If there are fewer than k points in the tree, returns all the points. If k is 0, returns an empty minmax heap without looking at the tree

pub fn iter_points(&self) -> impl Iterator<Item = &R::Point> + '_

Borrowing iterator over only references to points. The order of the result is arbitrary, but all points will be visited exactly once.

pub fn into_points(self) -> impl Iterator<Item = R::Point>

Consuming iterator over only points, which are moved out of self. The order of the result is arbitrarily, but all points will be visited exactly once.

pub fn iter_values(&self) -> impl Iterator<Item = &V> + '_

Borrowing iterator over only references to values. The order of the result is arbitrary, but the value for each point will be visited exactly once.

pub fn mut_values(&mut self) -> impl Iterator<Item = &mut V> + '_

Mutable borrowing iterator over only references to values. The order of the result is arbitrary, but the value for each point will be visited exactly once. This is a splitting borrow, so it is safe to store a reference to some value and mutate it even after subsequent values have been visited.

pub fn into_values(self) -> impl Iterator<Item = V>

Consuming iterator over only values, which are moved out of self. The order of the result is arbitrary, but the value for each point will be visited exactly once.

pub fn get(&self, point: &R::Point) -> Option<&V>

Return a reference to the value for some point in the tree, or None if the point is not found

pub fn get_point_value(&self, point: &R::Point) -> Option<(&R::Point, &V)>

Return a reference to a point in the tree and the corresponding value, or None if the point is not found

pub fn contains_point(&self, point: &R::Point) -> bool

Return true if the tree contains some point or false otherwise

pub fn get_mut(&mut self, point: &R::Point) -> Option<&mut V>

Return a mutable reference to the value for some point in the tree, or None if the point is not found

pub unsafe fn launder_point_ref(&self, ent: &R::Point) -> usize

Convert a const reference to a point in the tree into an internal index. This function is unsafe because it can’t be used productively without Self::launder_idx_mut. ent MUST be a reference to one of the points actually stored in the tree, NOT an identical point elsewhere, or this function invokes undefined behavior.

pub unsafe fn launder_value_ref(&self, ent: &V) -> usize

Convert a const reference to a value in the tree into an internal index. This function is unsafe because it can’t be used productively without Self::launder_idx_point. ent MUST be a reference to one of the values actually stored in the tree, NOT an identical point elsewhere, or this function invokes undefined behavior.

pub unsafe fn launder_idx_point(&self, idx: usize) -> &R::Point

Convert an internal index into a reference to a point in the tree. The internal index must have come from Self::launder_point_ref or Self::launder_value_ref called on the same tree. The intent of this function is to allow finding the points corresponding to values given a value reference, like for example if some of the values are made into an intrusive linked data structure.

pub unsafe fn launder_idx_mut(&mut self, idx: usize) -> &mut V

Convert an internal index into a mutable reference to a value in the tree. The internal index must have come from Self::launder_point_ref or Self::launder_value_ref called on the same tree. The intent of this function is to allow mutating the values of the points in the result set of k_closest etc.

Trait Implementations

impl<R: Debug + KdRegion, V: Debug> Debug for KdTree<R, V>

where R::Point: Debug,

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

Formats the value using the given formatter.

impl<R: KdRegion, V, const N: usize> From<[(<R as KdRegion>::Point, V); N]> for KdTree<R, V>

fn from(ents: [(R::Point, V); N]) -> Self

Converts to this type from the input type.

impl<R: KdRegion, V> FromIterator<(<R as KdRegion>::Point, V)> for KdTree<R, V>

fn from_iter<T: IntoIterator<Item = (R::Point, V)>>(iter: T) -> Self

Creates a value from an iterator.

impl<R: KdRegion, V> Index<&<R as KdRegion>::Point> for KdTree<R, V>

type Output = V

The returned type after indexing.

fn index(&self, point: &R::Point) -> &V

Performs the indexing (container[index]) operation.

impl<R: KdRegion, V> IndexMut<&<R as KdRegion>::Point> for KdTree<R, V>

fn index_mut(&mut self, point: &R::Point) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, R: KdRegion, V> IntoIterator for &'a KdTree<R, V>

type Item = (&'a <R as KdRegion>::Point, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, <R as KdRegion>::Point, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, R: KdRegion, V> IntoIterator for &'a mut KdTree<R, V>

type Item = (&'a <R as KdRegion>::Point, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, <R as KdRegion>::Point, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<R: KdRegion, V> IntoIterator for KdTree<R, V>

type Item = (<R as KdRegion>::Point, V)

The type of the elements being iterated over.

type IntoIter = <Vec<(<R as KdRegion>::Point, V)> as IntoIterator>::IntoIter

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.