Struct KdTree

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

Floating point k-d tree

For use when the co-ordinates of the points being stored in the tree on the float KdTree. This will be f64 or f32, or f16 if the f16 or f16_rkyv_08 features are enabled

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

Implementations

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

pub fn add(&mut self, query: &[A; K], item: T)

Adds an item to the tree.

The first argument specifies co-ordinates of the point where the item is located. The second argument is an integer identifier / index for the item being stored.

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, 3> = KdTree::new();

tree.add(&[1.0, 2.0, 5.0], 100);

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

pub fn remove(&mut self, query: &[A; K], item: T) -> usize

Removes an item from the tree.

The first argument specifies co-ordinates of the point where the item is located. The second argument is the integer identifier / index for the stored item.

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, 3> = KdTree::new();

tree.add(&[1.0, 2.0, 5.0], 100);
tree.add(&[1.0, 2.0, 5.0], 200);
assert_eq!(tree.size(), 2);

tree.remove(&[1.0, 2.0, 5.0], 100);
assert_eq!(tree.size(), 1);

tree.remove(&[1.0, 2.0, 5.0], 200);
assert_eq!(tree.size(), 0);

impl<A, T, const K: usize, const B: usize, IDX> KdTree<A, T, K, B, IDX>

where A: Axis, T: Content, IDX: Index<T = IDX>, usize: Cast<IDX>,

pub fn new() -> Self

Creates a new float KdTree.

Capacity is set by default to 10x the bucket size (32 in this case).

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, 3> = KdTree::new();

tree.add(&[1.0, 2.0, 5.0], 100);

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

pub fn with_capacity(capacity: usize) -> Self

Creates a new float KdTree and reserve capacity for a specific number of items.

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, 3> = KdTree::with_capacity(1_000_000);

tree.add(&[1.0, 2.0, 5.0], 100);

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

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

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

use kiddo::KdTree;

let mut tree: KdTree<f64, 3> = KdTree::new();
tree.add(&[1.0f64, 2.0f64, 3.0f64], 10);
tree.add(&[11.0f64, 12.0f64, 13.0f64], 20);
tree.add(&[21.0f64, 22.0f64, 23.0f64], 30);

let mut pairs: Vec<_> = tree.iter().collect();
assert_eq!(pairs.pop().unwrap(), (10, [1.0f64, 2.0f64, 3.0f64]));
assert_eq!(pairs.pop().unwrap(), (20, [11.0f64, 12.0f64, 13.0f64]));
assert_eq!(pairs.pop().unwrap(), (30, [21.0f64, 22.0f64, 23.0f64]));

impl<A, T, const K: usize, const B: usize, IDX> KdTree<A, T, K, B, IDX>

where A: Axis, T: Content, IDX: Index<T = IDX>, usize: Cast<IDX>,

pub fn size(&self) -> T

Returns the current number of elements stored in the tree

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, 3> = KdTree::new();

tree.add(&[1.0, 2.0, 5.0], 100);
tree.add(&[1.1, 2.1, 5.1], 101);

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

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

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

where 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. Returns an iterator.

Examples

    use kiddo::KdTree;
    use kiddo::best_neighbour::BestNeighbour;
    use kiddo::SquaredEuclidean;

    let mut tree: KdTree<f64, 3> = KdTree::new();
    tree.add(&[1.0, 2.0, 5.0], 100);
    tree.add(&[2.0, 3.0, 6.0], 101);

    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: 100 });

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

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

where D: DistanceMetric<A, K>,

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

Examples

    use kiddo::KdTree;
    use kiddo::SquaredEuclidean;

    let mut tree: KdTree<f64, 3> = KdTree::new();
    tree.add(&[1.0, 2.0, 5.0], 100);
    tree.add(&[2.0, 3.0, 6.0], 101);

    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, 100);

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

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.

Results are returned in as a ResultCollection, which can return a sorted or unsorted Vec.

Examples

use std::num::NonZero;
use kiddo::KdTree;
use kiddo::SquaredEuclidean;

let mut tree: KdTree<f64, 3> = KdTree::new();
tree.add(&[1.0, 2.0, 5.0], 100);
tree.add(&[2.0, 3.0, 6.0], 101);
let max_qty = NonZero::new(1).unwrap();
let within = tree.nearest_n_within::<SquaredEuclidean>(&[1.0, 2.0, 5.0], 10f64, max_qty, true);

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

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

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

where D: DistanceMetric<A, K>,

Finds the nearest element to query, using the specified distance metric function.

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

Examples

    use kiddo::KdTree;
    use kiddo::SquaredEuclidean;

    let mut tree: KdTree<f64, 3> = KdTree::new();
    tree.add(&[1.0, 2.0, 5.0], 100);
    tree.add(&[2.0, 3.0, 6.0], 101);

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

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

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

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

where D: DistanceMetric<A, K>,

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

Results are returned sorted nearest-first

Examples

    use kiddo::KdTree;
    use kiddo::SquaredEuclidean;
    
let mut tree: KdTree<f64, 3> = KdTree::new();
tree.add(&[1.0, 2.0, 5.0], 100);
tree.add(&[2.0, 3.0, 6.0], 101);

    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, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

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

where D: DistanceMetric<A, K>,

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::KdTree;
use kiddo::SquaredEuclidean;

let mut tree: KdTree<f64, 3> = KdTree::new();
tree.add(&[1.0, 2.0, 5.0], 100);
tree.add(&[2.0, 3.0, 6.0], 101);

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

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

impl<'a, A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

pub fn within_unsorted_iter<D>( &'a self, query: &'a [A; K], dist: A, ) -> WithinUnsortedIter<'a, A, T>

where D: DistanceMetric<A, K>,

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

Returns an Iterator. Results are returned in arbitrary order.

Examples

use kiddo::KdTree;
use kiddo::SquaredEuclidean;

let mut tree: KdTree<f64, 3> = KdTree::new();
tree.add(&[1.0, 2.0, 5.0], 100);
tree.add(&[2.0, 3.0, 6.0], 101);

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

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

Trait Implementations

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

where Vec<LeafNode<A, T, K, B, IDX>>: Archive, Vec<StemNode<A, K, IDX>>: Archive, IDX: Archive, T: Archive + Copy + Default,

type Archived = ArchivedKdTree<A, T, K, B, IDX>

The archived representation of this type.

type Resolver = KdTreeResolver<A, T, K, B, IDX>

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, IDX: Clone> Clone for KdTree<A, T, K, B, IDX>

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

Returns a duplicate 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, IDX: Debug> Debug for KdTree<A, T, K, B, IDX>

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

Formats the value using the given formatter.

impl<A, T, const K: usize, const B: usize, IDX> Default for KdTree<A, T, K, B, IDX>

where A: Axis, T: Content, IDX: Index<T = IDX>, usize: Cast<IDX>,

fn default() -> Self

Returns the “default value” for a type.

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

where A: Deserialize<'de> + Copy + Default, T: Deserialize<'de> + Copy + Default, IDX: 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, const K: usize, const B: usize, IDX> Deserialize<KdTree<A, T, K, B, IDX>, __D> for Archived<KdTree<A, T, K, B, IDX>>

where Vec<LeafNode<A, T, K, B, IDX>>: Archive, Archived<Vec<LeafNode<A, T, K, B, IDX>>>: Deserialize<Vec<LeafNode<A, T, K, B, IDX>>, __D>, Vec<StemNode<A, K, IDX>>: Archive, Archived<Vec<StemNode<A, K, IDX>>>: Deserialize<Vec<StemNode<A, K, IDX>>, __D>, IDX: Archive, Archived<IDX>: Deserialize<IDX, __D>, T: Archive + Copy + Default, Archived<T>: Deserialize<T, __D>,

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

Deserializes using the given deserializer

impl<'a, 't, A: Axis + Copy, T: Content + Copy, const K: usize, const B: usize, IDX: Index<T = IDX>> Extend<(&'a [A; K], &'t T)> for KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

fn extend<I: IntoIterator<Item = (&'a [A; K], &'t T)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one #72631)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)

Reserves capacity in a collection for the given number of additional elements.

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> Extend<([A; K], T)> for KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

fn extend<I: IntoIterator<Item = ([A; K], T)>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one #72631)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one #72631)

Reserves capacity in a collection for the given number of additional elements.

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> From<&Vec<[A; K]>> for KdTree<A, T, K, B, IDX>

where usize: Cast<IDX> + Cast<T>,

fn from(vec: &Vec<[A; K]>) -> Self

Converts to this type from the input type.

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>, const N: usize> From<[([A; K], T); N]> for KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

fn from(value: [([A; K], T); N]) -> Self

Converts to this type from the input type.

impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> FromIterator<([A; K], T)> for KdTree<A, T, K, B, IDX>

where usize: Cast<IDX>,

fn from_iter<I: IntoIterator<Item = ([A; K], T)>>(iter: I) -> Self

Creates a value from an iterator.

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

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

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

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, const K: usize, const B: usize, IDX> Serialize<__S> for KdTree<A, T, K, B, IDX>

where Vec<LeafNode<A, T, K, B, IDX>>: Serialize<__S>, Vec<StemNode<A, K, IDX>>: Serialize<__S>, IDX: Serialize<__S>, T: Serialize<__S> + Copy + Default,

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, IDX> Serialize for KdTree<A, T, K, B, IDX>

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

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, IDX> StructuralPartialEq for KdTree<A, T, K, B, IDX>