Struct 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 vs non-immutable tree when serialised, 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.

Compared to non-dynamic ImmutableKdTree, this can handle data like point clouds that may have many occurrences of multiple points have the exact same value on a given axis. This comes at the expense of slower performance. Memory usage should still be very efficient, more so than the standard and non-dynamic immutable tree types.

As with the vanilla tree, f64 or f32 are supported currently for co-ordinate values, or f16 if used with the half crate.

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 + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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

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: LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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, T, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

where A: Axis + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, T: Content, usize: Cast<T>,

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

where A: LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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 std::num::NonZero;
    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, NonZero::new(1).unwrap());
    let first = best_n_within.next().unwrap();

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

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

where A: Axis + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, T: Content, usize: Cast<T>,

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

where A: LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, D: DistanceMetric<A, K>, usize: Cast<T>,

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

Examples

    use std::num::NonZero;
    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], NonZero::new(1).unwrap());

    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 + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, T: Content, usize: Cast<T>,

pub fn nearest_n_within<D>( &self, query: &[A; K], dist: A, max_items: NonZero<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 std::num::NonZero;
    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, NonZero::new(2).unwrap(), true);

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

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

where A: Axis + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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, T, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

where A: Axis + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, T: Content, usize: Cast<T>,

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

where A: LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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, T, const K: usize, const B: usize> ImmutableKdTree<A, T, K, B>

where A: Axis + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, T: Content, usize: Cast<T>,

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

where A: LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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 EncodeAVec<A>: ArchiveWith<AVec<A>>, [Vec<A>; K]: Archive, Vec<T>: Archive, Vec<(u32, u32)>: Archive, i32: Archive,

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

The archived representation of this type.

type Resolver = ImmutableKdTreeR8Resolver<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.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

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

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

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 duplicate of the value.

const 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> + Deserialize<'de> + Copy + Default, T: Deserialize<'de> + Copy + Default + Deserialize<'de>,

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 EncodeAVec<A>: ArchiveWith<AVec<A>> + DeserializeWith<<EncodeAVec<A> as ArchiveWith<AVec<A>>>::Archived, AVec<A>, __D>, [Vec<A>; K]: Archive, <[Vec<A>; K] as Archive>::Archived: Deserialize<[Vec<A>; K], __D>, Vec<T>: Archive, <Vec<T> as Archive>::Archived: Deserialize<Vec<T>, __D>, Vec<(u32, u32)>: Archive, <Vec<(u32, u32)> as Archive>::Archived: Deserialize<Vec<(u32, u32)>, __D>, i32: Archive, <i32 as Archive>::Archived: Deserialize<i32, __D>,

fn deserialize( &self, deserializer: &mut __D, ) -> Result<ImmutableKdTree<A, T, K, B>, <__D as Fallible>::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 + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, 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, T, const K: usize, const B: usize> From<ImmutableKdTree<A, T, K, B>> for ImmutableKdTreeRK<A, T, K, B>

where A: Axis + LeafSliceFloat<T> + LeafSliceFloatChunk<T, K>, T: Content, usize: Cast<T>,

fn from(orig: ImmutableKdTree<A, T, K, B>) -> Self

Creates an ImmutableKdTreeRK from an ImmutableKdTree

ImmutableKdTreeRK implements rkyv::Archive, permitting it to be serialized to as close to a zero-copy form as possible. Zero-copy-deserialized ImmutableKdTreeRK instances can be converted to instances of AlignedArchivedImmutableKdTree, which involves a copy of the stems to ensure correct alignment, but re-use of the rest of the structure. AlignedArchivedImmutableKdTree instances can then be queried in the same way as the original ImmutableKdTree.

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

Tests for self and other values to be equal, and is used by ==.

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

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 EncodeAVec<A>: SerializeWith<AVec<A>, __S>, [Vec<A>; K]: Serialize<__S>, Vec<T>: Serialize<__S>, Vec<(u32, u32)>: Serialize<__S>, i32: Serialize<__S>,

fn serialize( &self, serializer: &mut __S, ) -> Result<<Self as Archive>::Resolver, <__S as Fallible>::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 + Serialize + Copy + Default, T: Serialize + 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>