Struct acap::kd::FlatKdTree

pub struct FlatKdTree<T> { /* fields omitted */ }

A k-d tree stored as a flat array.

A FlatKdTree is always balanced and usually more efficient than a KdTree, but doesn’t support dynamic updates.

Implementations

impl<T: Coordinates> FlatKdTree<T>

pub fn balanced<I: IntoIterator<Item = T>>(items: I) -> Self

Create a balanced tree out of a sequence of items.

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

Iterate over the items stored in this tree.

Trait Implementations

impl<T: Debug> Debug for FlatKdTree<T>

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

Formats the value using the given formatter.

impl<T: Coordinates> FromIterator<T> for FlatKdTree<T>

fn from_iter<I: IntoIterator<Item = T>>(items: I) -> Self

Creates a value from an iterator.

impl<T> IntoIterator for FlatKdTree<T>

type Item = T

The type of the elements being iterated over.

type IntoIter = FlatIntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, T> IntoIterator for &'a FlatKdTree<T>

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = FlatIter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V> NearestNeighbors<K, V> for FlatKdTree<V> where
    K: KdProximity<V>,
    K::Value: PartialOrd<K::Distance>,
    V: Coordinates, 

fn search<'k, 'v, N>(&'v self, neighborhood: N) -> N where
    K: 'k,
    V: 'v,
    N: Neighborhood<&'k K, &'v V>, 

Search for nearest neighbors and add them to a neighborhood.

fn nearest(&self, target: &K) -> Option<Neighbor<&V, K::Distance>>

Returns the nearest neighbor to target (or None if this index is empty).

fn nearest_within<D>(
    &self,
    target: &K,
    threshold: D
) -> Option<Neighbor<&V, K::Distance>> where
    D: TryInto<K::Distance>, 

Returns the nearest neighbor to target within the distance threshold, if one exists.

fn k_nearest(&self, target: &K, k: usize) -> Vec<Neighbor<&V, K::Distance>>

Returns the up to k nearest neighbors to target.

fn k_nearest_within<D>(
    &self,
    target: &K,
    k: usize,
    threshold: D
) -> Vec<Neighbor<&V, K::Distance>> where
    D: TryInto<K::Distance>, 

Returns the up to k nearest neighbors to target within the distance threshold.

fn merge_k_nearest<'v>(
    &'v self,
    target: &K,
    k: usize,
    neighbors: &mut Vec<Neighbor<&'v V, K::Distance>>
)

Merges up to k nearest neighbors into an existing sorted vector.

fn merge_k_nearest_within<'v, D>(
    &'v self,
    target: &K,
    k: usize,
    threshold: D,
    neighbors: &mut Vec<Neighbor<&'v V, K::Distance>>
) where
    D: TryInto<K::Distance>, 

Merges up to k nearest neighbors within the threshold into an existing sorted vector.

impl<K, V> ExactNeighbors<K, V> for FlatKdTree<V> where
    K: KdProximity<V> + Minkowski<V>,
    K::Value: PartialOrd<K::Distance>,
    V: Coordinates, 

k-d trees are exact for Minkowski distances.