Struct kiddo::immutable::float::kdtree::ImmutableKdTree

pub struct ImmutableKdTree<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize> { /* private fields */ }

Immutable floating point k-d tree

Offers less memory utilisation, smaller size when serialized, and faster more consistent query performance. This comes at the expense of not being able to modify the contents of the tree after its initial construction, and longer construction times. As with the vanilla tree, f64 or f32 are supported currently for co-ordinate values, or f16 if the f16 feature is enabled

A convenient type alias exists for ImmutableKdTree with some sensible defaults set: kiddo::ImmutableKdTree.

Implementations

impl<A, T, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

where A: Axis + BestFromDists<T, B>, T: Content, usize: Cast<T>,

pub fn new_from_slice(source: &[[A; K]]) -> Self

where usize: Cast<T>,

Creates an ImmutableKdTree, balanced and optimized, populated with items from source.

ImmutableKdTree instances are optimally balanced and tuned, but are not modifiable after construction.

Examples

use kiddo::immutable::float::kdtree::ImmutableKdTree;

let points: Vec<[f64; 3]> = vec!([1.0f64, 2.0f64, 3.0f64]);
let tree: ImmutableKdTree<f64, u32, 3, 32> = ImmutableKdTree::new_from_slice(&points);

assert_eq!(tree.size(), 1);

pub fn size(&self) -> usize

Returns the current number of elements stored in the tree

Examples

use kiddo::immutable::float::kdtree::ImmutableKdTree;

let points: Vec<[f64; 3]> = vec!([1.0f64, 2.0f64, 3.0f64]);
let tree: ImmutableKdTree<f64, u32, 3, 32> = ImmutableKdTree::new_from_slice(&points);

assert_eq!(tree.size(), 1);

pub fn capacity(&self) -> usize

Returns the theoretical max capacity of this tree

pub fn generate_stats(&self) -> TreeStats

Generates a TreeStats object, describing some statistics of a particular instance of an ImmutableTree

pub fn iter(&self) -> impl Iterator<Item = (T, [A; K])> + '_

Iterate over all (index, point) tuples in arbitrary order.

use kiddo::immutable::float::kdtree::ImmutableKdTree;

let points: Vec<[f64; 3]> = vec!([1.0f64, 2.0f64, 3.0f64]);
let tree: ImmutableKdTree<f64, u32, 3, 32> = ImmutableKdTree::new_from_slice(&points);

let mut pairs: Vec<_> = tree.iter().collect();
assert_eq!(pairs.pop().unwrap(), (0, [1.0, 2.0, 3.0]));

impl<A: Axis, T: Content, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

pub fn approx_nearest_one<D>(&self, query: &[A; K]) -> NearestNeighbour<A, T>

where A: BestFromDists<T, B>, D: DistanceMetric<A, K>, usize: Cast<T>,

Queries the tree to find the approximate nearest element to query, using the specified distance metric function.

Faster than querying for nearest_one(point) due to not recursing up the tree to find potentially closer points in other branches.

Examples

    use kiddo::ImmutableKdTree;
    use kiddo::SquaredEuclidean;

    let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

    let nearest = tree.approx_nearest_one::<SquaredEuclidean>(&[1.0, 2.0, 5.1]);

    assert!((nearest.distance - 0.01f64).abs() < f64::EPSILON);
    assert_eq!(nearest.item, 0);

impl<A: Axis, T: Content, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

pub fn best_n_within<D>( &self, query: &[A; K], dist: A, max_qty: usize ) -> impl Iterator<Item = BestNeighbour<A, T>>

where A: BestFromDists<T, B>, usize: Cast<T>, D: DistanceMetric<A, K>,

Finds the “best” n elements within dist of query.

Results are returned in arbitrary order. ‘Best’ is determined by performing a comparison of the elements using < (ie, std::cmp::Ordering::is_lt). Returns an iterator.

Examples

    use kiddo::ImmutableKdTree;
    use kiddo::best_neighbour::BestNeighbour;
    use kiddo::SquaredEuclidean;

    let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

    let mut best_n_within = tree.best_n_within::<SquaredEuclidean>(&[1.0, 2.0, 5.0], 10f64, 1);
    let first = best_n_within.next().unwrap();

    assert_eq!(first, BestNeighbour { distance: 0.0, item: 0 });

impl<A: Axis, T: Content, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

pub fn nearest_n<D>( &self, query: &[A; K], qty: usize ) -> Vec<NearestNeighbour<A, T>>

where A: BestFromDists<T, B>, D: DistanceMetric<A, K>, usize: Cast<T>,

Finds the nearest qty elements to query, according the specified distance metric function.

Examples

    use kiddo::ImmutableKdTree;
    use kiddo::SquaredEuclidean;

    let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

    let nearest: Vec<_> = tree.nearest_n::<SquaredEuclidean>(&[1.0, 2.0, 5.1], 1);

    assert_eq!(nearest.len(), 1);
    assert!((nearest[0].distance - 0.01f64).abs() < f64::EPSILON);
    assert_eq!(nearest[0].item, 0);

impl<A, T, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

where A: Axis + BestFromDists<T, B>, T: Content, usize: Cast<T>,

pub fn nearest_n_within<D>( &self, query: &[A; K], dist: A, max_items: usize, sorted: bool ) -> Vec<NearestNeighbour<A, T>>

where D: DistanceMetric<A, K>,

Finds up to n elements within dist of query, using the specified distance metric function.

Examples

    use kiddo::ImmutableKdTree;
    use kiddo::SquaredEuclidean;
    let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

    let within = tree.nearest_n_within::<SquaredEuclidean>(&[1.0, 2.0, 5.0], 10f64, 2, true);

    assert_eq!(within.len(), 2);

impl<A, T, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

where A: Axis + BestFromDists<T, B>, T: Content, usize: Cast<T>,

pub fn nearest_one<D>(&self, query: &[A; K]) -> NearestNeighbour<A, T>

where D: DistanceMetric<A, K>,

Queries the tree to find the nearest item to the query point.

Faster than querying for nearest_n(point, 1, …) due to not needing to allocate memory or maintain sorted results.

Examples

    use kiddo::ImmutableKdTree;
    use kiddo::SquaredEuclidean;

    let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

    let nearest = tree.nearest_one::<SquaredEuclidean>(&[1.0, 2.0, 5.1]);

    assert!((nearest.distance - 0.01f64).abs() < f64::EPSILON);
    assert_eq!(nearest.item, 0);

impl<A: Axis, T: Content, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

pub fn within<D>(&self, query: &[A; K], dist: A) -> Vec<NearestNeighbour<A, T>>

where A: BestFromDists<T, B>, D: DistanceMetric<A, K>, usize: Cast<T>,

Finds all elements within dist of query, using the specified distance metric function.

Results are returned sorted nearest-first

Examples

    use kiddo::ImmutableKdTree;
    use kiddo::SquaredEuclidean;
    let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

    let within = tree.within::<SquaredEuclidean>(&[1.0, 2.0, 5.0], 10f64);

    assert_eq!(within.len(), 2);

impl<A: Axis, T: Content, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

pub fn within_unsorted<D>( &self, query: &[A; K], dist: A ) -> Vec<NearestNeighbour<A, T>>

where A: BestFromDists<T, B>, D: DistanceMetric<A, K>, usize: Cast<T>,

Finds all elements within dist of query, using the specified distance metric function.

Results are returned in arbitrary order. Faster than within.

Examples

use kiddo::ImmutableKdTree;
use kiddo::SquaredEuclidean;
let content: Vec<[f64; 3]> = vec!(
            [1.0, 2.0, 5.0],
            [2.0, 3.0, 6.0]
        );

        let tree: ImmutableKdTree<f64, 3> = ImmutableKdTree::new_from_slice(&content);

let within = tree.within_unsorted::<SquaredEuclidean>(&[1.0, 2.0, 5.0], 10f64);

assert_eq!(within.len(), 2);

Trait Implementations

impl<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize> Archive for ImmutableKdTree<A, T, K, B>

where Vec<LeafNode<A, T, K, B>>: Archive, Vec<A>: Archive, usize: Archive,

type Archived = ArchivedImmutableKdTree<A, T, K, B>

The archived representation of this type.

type Resolver = ImmutableKdTreeResolver<A, T, K, B>

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

unsafe fn resolve( &self, pos: usize, resolver: Self::Resolver, out: *mut Self::Archived )

Creates the archived version of this value at the given position and writes it to the given output.

impl<A: Clone + Copy + Default, T: Clone + Copy + Default, const K: usize, const B: usize> Clone for ImmutableKdTree<A, T, K, B>

fn clone(&self) -> ImmutableKdTree<A, T, K, B>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A: Debug + Copy + Default, T: Debug + Copy + Default, const K: usize, const B: usize> Debug for ImmutableKdTree<A, T, K, B>

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

Formats the value using the given formatter.

impl<'de, A, T, const K: usize, const B: usize> Deserialize<'de> for ImmutableKdTree<A, T, K, B>

where A: Deserialize<'de> + Copy + Default, T: Deserialize<'de> + Copy + Default,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<__D: Fallible + ?Sized, A: Copy + Default, T: Copy + Default, const K: usize, const B: usize> Deserialize<ImmutableKdTree<A, T, K, B>, __D> for Archived<ImmutableKdTree<A, T, K, B>>

where Vec<LeafNode<A, T, K, B>>: Archive, Archived<Vec<LeafNode<A, T, K, B>>>: Deserialize<Vec<LeafNode<A, T, K, B>>, __D>, Vec<A>: Archive, Archived<Vec<A>>: Deserialize<Vec<A>, __D>, usize: Archive, Archived<usize>: Deserialize<usize, __D>,

fn deserialize( &self, deserializer: &mut __D ) -> Result<ImmutableKdTree<A, T, K, B>, __D::Error>

Deserializes using the given deserializer

impl<A, T, const K: usize, const B: usize> From<&[[A; K]]> for ImmutableKdTree<A, T, K, B>

where A: Axis + BestFromDists<T, B>, T: Content, usize: Cast<T>,

fn from(slice: &[[A; K]]) -> Self

Creates an ImmutableKdTree, balanced and optimized, populated with items from source.

ImmutableKdTree instances are optimally balanced and tuned, but are not modifiable after construction.

Examples

use kiddo::immutable::float::kdtree::ImmutableKdTree;

let points: Vec<[f64; 3]> = vec!([1.0f64, 2.0f64, 3.0f64]);
let tree: ImmutableKdTree<f64, u32, 3, 32> = (&*points).into();

assert_eq!(tree.size(), 1);

impl<A: PartialEq + Copy + Default, T: PartialEq + Copy + Default, const K: usize, const B: usize> PartialEq for ImmutableKdTree<A, T, K, B>

fn eq(&self, other: &ImmutableKdTree<A, T, K, B>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<__S: Fallible + ?Sized, A: Copy + Default, T: Copy + Default, const K: usize, const B: usize> Serialize<__S> for ImmutableKdTree<A, T, K, B>

where Vec<LeafNode<A, T, K, B>>: Serialize<__S>, Vec<A>: Serialize<__S>, usize: Serialize<__S>,

fn serialize(&self, serializer: &mut __S) -> Result<Self::Resolver, __S::Error>

Writes the dependencies for the object and returns a resolver that can create the archived type.

impl<A, T, const K: usize, const B: usize> Serialize for ImmutableKdTree<A, T, K, B>

where A: Serialize + Copy + Default, T: Serialize + Copy + Default,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize> StructuralPartialEq for ImmutableKdTree<A, T, K, B>