Struct kd_tree::KdTreeN

pub struct KdTreeN<T, N: Unsigned>(_, _);

An owned kd-tree. This type implements std::ops::Deref to KdSlice.

Implementations

impl<T, N: Unsigned> KdTreeN<T, N>

pub fn into_vec(self) -> Vec<T>

pub fn build_by<F>(items: Vec<T>, compare: F) -> Self where
    F: Fn(&T, &T, usize) -> Ordering + Copy, 

Example

struct Item {
    point: [i32; 3],
    id: usize,
}
let kdtree = kd_tree::KdTree3::build_by(
    vec![
        Item { point: [1, 2, 3], id: 111 },
        Item { point: [3, 1, 2], id: 222 },
        Item { point: [2, 3, 1], id: 333 },
    ],
    |item1, item2, k| item1.point[k].cmp(&item2.point[k])
);
assert_eq!(kdtree.nearest_by(&[3, 1, 2], |item, k| item.point[k]).unwrap().item.id, 222);

pub fn build_by_key<Key, F>(items: Vec<T>, kd_key: F) -> Self where
    Key: Ord,
    F: Fn(&T, usize) -> Key + Copy, 

Example

struct Item {
    point: [f64; 3],
    id: usize,
}
let kdtree = kd_tree::KdTree3::build_by_key(
    vec![
        Item { point: [1.0, 2.0, 3.0], id: 111 },
        Item { point: [3.0, 1.0, 2.0], id: 222 },
        Item { point: [2.0, 3.0, 1.0], id: 333 },
    ],
    |item, k| ordered_float::OrderedFloat(item.point[k])
);
assert_eq!(kdtree.nearest_by(&[3.1, 0.9, 2.1], |item, k| item.point[k]).unwrap().item.id, 222);

pub fn build_by_ordered_float(points: Vec<T>) -> Self where
    T: KdPoint<Dim = N>,
    T::Scalar: Float, 

Example

use kd_tree::KdTree;
let kdtree: KdTree<[f64; 3]> = KdTree::build_by_ordered_float(vec![
    [1.0, 2.0, 3.0], [3.0, 1.0, 2.0], [2.0, 3.0, 1.0]
]);
assert_eq!(kdtree.nearest(&[3.1, 0.9, 2.1]).unwrap().item, &[3.0, 1.0, 2.0]);

pub fn build(points: Vec<T>) -> Self where
    T: KdPoint<Dim = N>,
    T::Scalar: Ord, 

Example

use kd_tree::KdTree;
let kdtree: KdTree<[i32; 3]> = KdTree::build(vec![[1, 2, 3], [3, 1, 2], [2, 3, 1]]);
assert_eq!(kdtree.nearest(&[3, 1, 2]).unwrap().item, &[3, 1, 2]);

Methods from Deref<Target = KdSliceN<T, N>>

pub fn items(&self) -> &[T]

pub fn nearest_by<Q: KdPoint<Dim = N>>(
    &self,
    query: &Q,
    coord: impl Fn(&T, usize) -> Q::Scalar + Copy
) -> Option<ItemAndDistance<'_, T, Q::Scalar>>

Returns the nearest item from the input point. Returns None if self.is_empty().

Example

struct Item {
    point: [f64; 3],
    id: usize,
}
let mut items: Vec<Item> = vec![
    Item { point: [1.0, 2.0, 3.0], id: 111 },
    Item { point: [3.0, 1.0, 2.0], id: 222 },
    Item { point: [2.0, 3.0, 1.0], id: 333 },
];
use ordered_float::OrderedFloat;
let kdtree = kd_tree::KdSlice3::sort_by_key(&mut items, |item, k| OrderedFloat(item.point[k]));
assert_eq!(kdtree.nearest_by(&[3.1, 0.9, 2.1], |item, k| item.point[k]).unwrap().item.id, 222);

pub fn nearest(
    &self,
    query: &impl KdPoint<Scalar = T::Scalar, Dim = N>
) -> Option<ItemAndDistance<'_, T, T::Scalar>> where
    T: KdPoint<Dim = N>, 

Returns the nearest item from the input point. Returns None if self.is_empty().

Example

let mut items: Vec<[i32; 3]> = vec![[1, 2, 3], [3, 1, 2], [2, 3, 1]];
let kdtree = kd_tree::KdSlice::sort(&mut items);
assert_eq!(kdtree.nearest(&[3, 1, 2]).unwrap().item, &[3, 1, 2]);

pub fn nearests_by<Q: KdPoint<Dim = N>>(
    &self,
    query: &Q,
    num: usize,
    coord: impl Fn(&T, usize) -> Q::Scalar + Copy
) -> Vec<ItemAndDistance<'_, T, Q::Scalar>>

Returns the nearest item from the input point. Returns None if self.is_empty().

Example

struct Item {
    point: [f64; 3],
    id: usize,
}
let mut items: Vec<Item> = vec![
    Item { point: [1.0, 2.0, 3.0], id: 111 },
    Item { point: [3.0, 1.0, 2.0], id: 222 },
    Item { point: [2.0, 3.0, 1.0], id: 333 },
];
use ordered_float::OrderedFloat;
let kdtree = kd_tree::KdSlice3::sort_by_key(&mut items, |item, k| OrderedFloat(item.point[k]));
let nearests = kdtree.nearests_by(&[2.5, 2.0, 1.4], 2, |item, k| item.point[k]);
assert_eq!(nearests.len(), 2);
assert_eq!(nearests[0].item.id, 333);
assert_eq!(nearests[1].item.id, 222);

pub fn nearests(
    &self,
    query: &impl KdPoint<Scalar = T::Scalar, Dim = N>,
    num: usize
) -> Vec<ItemAndDistance<'_, T, T::Scalar>> where
    T: KdPoint<Dim = N>, 

Returns kNN(k nearest neighbors) from the input point.

Example

let mut items: Vec<[i32; 3]> = vec![[1, 2, 3], [3, 1, 2], [2, 3, 1], [3, 2, 2]];
let kdtree = kd_tree::KdSlice::sort(&mut items);
let nearests = kdtree.nearests(&[3, 1, 2], 2);
assert_eq!(nearests.len(), 2);
assert_eq!(nearests[0].item, &[3, 1, 2]);
assert_eq!(nearests[1].item, &[3, 2, 2]);

pub fn within_by_cmp(
    &self,
    compare: impl Fn(&T, usize) -> Ordering + Copy
) -> Vec<&T>

pub fn within_by<Q: KdPoint<Dim = N>>(
    &self,
    query: &[Q; 2],
    coord: impl Fn(&T, usize) -> Q::Scalar + Copy
) -> Vec<&T>

pub fn within(
    &self,
    query: &[impl KdPoint<Scalar = T::Scalar, Dim = N>; 2]
) -> Vec<&T> where
    T: KdPoint<Dim = N>, 

search points within a rectangular region

pub fn within_radius_by<Q: KdPoint<Dim = N>>(
    &self,
    query: &Q,
    radius: Q::Scalar,
    coord: impl Fn(&T, usize) -> Q::Scalar + Copy
) -> Vec<&T>

pub fn within_radius(
    &self,
    query: &impl KdPoint<Scalar = T::Scalar, Dim = N>,
    radius: T::Scalar
) -> Vec<&T> where
    T: KdPoint<Dim = N>, 

search points within k-dimensional sphere

Trait Implementations

impl<T, N: Unsigned> AsRef<KdSliceN<T, N>> for KdTreeN<T, N>

pub fn as_ref(&self) -> &KdSliceN<T, N>

Performs the conversion.

impl<T, N: Unsigned> Borrow<KdSliceN<T, N>> for KdTreeN<T, N>

pub fn borrow(&self) -> &KdSliceN<T, N>

Immutably borrows from an owned value.

impl<T: Clone, N: Clone + Unsigned> Clone for KdTreeN<T, N>

pub fn clone(&self) -> KdTreeN<T, N>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, N: Debug + Unsigned> Debug for KdTreeN<T, N>

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

Formats the value using the given formatter.

impl<T: Default, N: Default + Unsigned> Default for KdTreeN<T, N>

pub fn default() -> KdTreeN<T, N>

Returns the "default value" for a type.

impl<T, N: Unsigned> Deref for KdTreeN<T, N>

type Target = KdSliceN<T, N>

The resulting type after dereferencing.

pub fn deref(&self) -> &Self::Target

Dereferences the value.

impl<T: Eq, N: Eq + Unsigned> Eq for KdTreeN<T, N>

impl<T, N: Unsigned> Into<Vec<T, Global>> for KdTreeN<T, N>

pub fn into(self) -> Vec<T>

Performs the conversion.

impl<T: PartialEq, N: PartialEq + Unsigned> PartialEq<KdTreeN<T, N>> for KdTreeN<T, N>

pub fn eq(&self, other: &KdTreeN<T, N>) -> bool

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

pub fn ne(&self, other: &KdTreeN<T, N>) -> bool

This method tests for !=.

impl<T, N: Unsigned> StructuralEq for KdTreeN<T, N>

impl<T, N: Unsigned> StructuralPartialEq for KdTreeN<T, N>