Struct kiddo::kiddo::KdTree

pub struct KdTree<A, T: PartialEq, const K: usize> { /* fields omitted */ }

Implementations

impl<A: Float + Zero + One, T: PartialEq, const K: usize> KdTree<A, T, K>

pub fn new() -> Self

Creates a new KdTree with default capacity per node of 16.

Examples

use kiddo::KdTree;

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

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

pub fn with_per_node_capacity(capacity: usize) -> Result<Self, ErrorKind>

Creates a new KdTree with a specific capacity per node. You may wish to experiment by tuning this value to best suit your workload via benchmarking: values between 10 and 40 often work best.

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, usize, 3> = KdTree::with_per_node_capacity(30)?;

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

pub fn with_capacity(capacity: usize) -> Result<Self, ErrorKind>

👎 Deprecated since 0.1.8:

with_capacity has a misleading name. Users should instead use with_per_node_capacity. with_capacity will be removed in a future release

Creates a new KdTree with a specific capacity per node.

pub fn size(&self) -> usize

Returns the current number of elements stored in the tree

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, usize, 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);

pub fn is_leaf(&self) -> bool

Returns true if the node is a leaf node

Examples

use kiddo::KdTree;

let mut tree_1: KdTree<f64, usize, 3> = KdTree::with_capacity(2)?;

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

assert_eq!(tree_1.is_leaf(), true);

let mut tree_2: KdTree<f64, usize, 3> = KdTree::with_capacity(1)?;

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

assert_eq!(tree_2.is_leaf(), false);

pub fn nearest<F>(
    &self,
    point: &[A; K],
    num: usize,
    distance: &F
) -> Result<Vec<(A, &T)>, ErrorKind> where
    F: Fn(&[A; K], &[A; K]) -> A, 

Queries the tree to find the nearest num elements to point, using the specified distance metric function.

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

let mut tree: KdTree<f64, usize, 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(&[1.0, 2.0, 5.1], 1, &squared_euclidean)?;

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

pub fn nearest_one<F>(
    &self,
    point: &[A; K],
    distance: &F
) -> Result<(A, &T), ErrorKind> where
    F: Fn(&[A; K], &[A; K]) -> A, 

Queries the tree to find the nearest element to point, using the specified distance metric function. Faster than querying for nearest(point, 1, …) due to not needing to allocate a Vec for the result

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

let mut tree: KdTree<f64, usize, 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(&[1.0, 2.0, 5.1], &squared_euclidean)?;

assert!((nearest.0 - 0.01f64).abs() < f64::EPSILON);
assert_eq!(*nearest.1, 100);

pub fn within<F>(
    &self,
    point: &[A; K],
    radius: A,
    distance: &F
) -> Result<Vec<(A, &T)>, ErrorKind> where
    F: Fn(&[A; K], &[A; K]) -> A, 

Queries the tree to find all elements within radius of point, using the specified distance metric function. Results are returned sorted nearest-first

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

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

tree.add(&[1.0, 2.0, 5.0], 100)?;
tree.add(&[2.0, 3.0, 6.0], 101)?;
tree.add(&[200.0, 300.0, 600.0], 102)?;

let within = tree.within(&[1.0, 2.0, 5.0], 10f64, &squared_euclidean)?;

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

pub fn within_unsorted<F>(
    &self,
    point: &[A; K],
    radius: A,
    distance: &F
) -> Result<Vec<(A, &T)>, ErrorKind> where
    F: Fn(&[A; K], &[A; K]) -> A, 

Queries the tree to find all elements within radius of point, using the specified distance metric function. Results are returned in arbitrary order. Faster than within()

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

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

tree.add(&[1.0, 2.0, 5.0], 100)?;
tree.add(&[2.0, 3.0, 6.0], 101)?;
tree.add(&[200.0, 300.0, 600.0], 102)?;

let within = tree.within(&[1.0, 2.0, 5.0], 10f64, &squared_euclidean)?;

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

pub fn best_n_within<F>(
    &self,
    point: &[A; K],
    radius: A,
    max_qty: usize,
    distance: &F
) -> Result<Vec<T>, ErrorKind> where
    F: Fn(&[A; K], &[A; K]) -> A,
    T: Copy + Ord, 

Queries the tree to find the best n elements within radius of point, using the specified distance metric function. Results are returned in arbitrary order. ‘Best’ is determined by performing a comparison of the elements using < (ie, std::ord::lt)

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

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

tree.add(&[1.0, 2.0, 5.0], 100)?;
tree.add(&[2.0, 3.0, 6.0], 1)?;
tree.add(&[200.0, 300.0, 600.0], 102)?;

let best_n_within = tree.best_n_within(&[1.0, 2.0, 5.0], 10f64, 1, &squared_euclidean)?;

assert_eq!(best_n_within[0], 1);

pub fn best_n_within_into_iter<F>(
    &self,
    point: &[A; K],
    radius: A,
    max_qty: usize,
    distance: &F
) -> impl Iterator<Item = T> where
    F: Fn(&[A; K], &[A; K]) -> A,
    T: Copy + Ord, 

Queries the tree to find the best n elements within radius of point, using the specified distance metric function. Results are returned in arbitrary order. ‘Best’ is determined by performing a comparison of the elements using < (ie, std::ord::lt). Returns an iterator.

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

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

tree.add(&[1.0, 2.0, 5.0], 100)?;
tree.add(&[2.0, 3.0, 6.0], 1)?;
tree.add(&[200.0, 300.0, 600.0], 102)?;

let mut best_n_within_iter = tree.best_n_within_into_iter(&[1.0, 2.0, 5.0], 10f64, 1, &squared_euclidean);
let first = best_n_within_iter.next().unwrap();

assert_eq!(first, 1);

pub fn iter_nearest<'a, 'b, F>(
    &'b self,
    point: &'a [A; K],
    distance: &'a F
) -> Result<NearestIter<'a, 'b, A, T, F, K>, ErrorKind> where
    F: Fn(&[A; K], &[A; K]) -> A, 

Returns an iterator over all elements in the tree, sorted nearest-first to the query point.

Examples

use kiddo::KdTree;
use kiddo::distance::squared_euclidean;

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

tree.add(&[1.0, 2.0, 5.0], 100)?;
tree.add(&[2.0, 3.0, 6.0], 101)?;

let mut nearest_iter = tree.iter_nearest(&[1.0, 2.0, 5.1], &squared_euclidean)?;

let nearest_first = nearest_iter.next().unwrap();

assert!((nearest_first.0 - 0.01f64).abs() < f64::EPSILON);
assert_eq!(*nearest_first.1, 100);

pub fn add(&mut self, point: &[A; K], data: T) -> Result<(), ErrorKind>

Add an element to the tree. The first argument specifies the location in kd space at which the element is located. The second argument is the data associated with that point in space.

Examples

use kiddo::KdTree;

let mut tree: KdTree<f64, usize, 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);

pub fn remove(&mut self, point: &[A; K], data: &T) -> Result<usize, ErrorKind>

Trait Implementations

impl<A: Clone, T: Clone + PartialEq, const K: usize> Clone for KdTree<A, T, K>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<A: Debug, T: Debug + PartialEq, const K: usize> Debug for KdTree<A, T, K>

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

Formats the value using the given formatter.

impl<'de, A, T: PartialEq, const K: usize> Deserialize<'de> for KdTree<A, T, K> where
    A: Deserialize<'de>,
    T: Deserialize<'de>, 

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl<A, T: PartialEq, const K: usize> Serialize for KdTree<A, T, K> where
    A: Serialize,
    T: Serialize, 

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

Serialize this value into the given Serde serializer.