pub struct KdTree<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize, IDX> { /* private fields */ }Expand description
Implementations§
Source§impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub fn add(&mut self, query: &[A; K], item: T)
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 fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::with_capacity(1_000_000);
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
assert_eq!(tree.size(), 2);Sourcepub fn remove(&mut self, query: &[A; K], item: T) -> usize
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 fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::with_capacity(1_000_000);
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 101);
assert_eq!(tree.size(), 2);
tree.remove(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
assert_eq!(tree.size(), 1);
tree.remove(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 101);
assert_eq!(tree.size(), 0);Source§impl<A, T, const K: usize, const B: usize, IDX> KdTree<A, T, K, B, IDX>
impl<A, T, const K: usize, const B: usize, IDX> KdTree<A, T, K, B, IDX>
Sourcepub fn new() -> Self
pub fn new() -> Self
Creates a new fixed-point/int KdTree.
Capacity is set by default to 10x the bucket size (32 in this case).
§Examples
use fixed::FixedU16;
use fixed::types::extra::U14;
use kiddo::fixed::kdtree::KdTree;
let mut tree: KdTree<FixedU16<U14>, u32, 3, 32, u32> = KdTree::new();
assert_eq!(tree.size(), 0);Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Creates a new fixed-point/integer KdTree and reserves capacity for a specific number of items.
§Examples
use fixed::FixedU16;
use fixed::types::extra::U14;
use kiddo::fixed::kdtree::KdTree;
let mut tree: KdTree<FixedU16<U14>, u32, 3, 32, u32> = KdTree::with_capacity(1_000_000);
assert_eq!(tree.size(), 0);Sourcepub fn size(&self) -> T
pub fn size(&self) -> T
Returns the current number of elements stored in the tree
§Examples
use fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::with_capacity(1_000_000);
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
assert_eq!(tree.size(), 2);Sourcepub fn iter(&self) -> impl Iterator<Item = (T, [A; K])> + '_
pub fn iter(&self) -> impl Iterator<Item = (T, [A; K])> + '_
Iterate over all (index, point) tuples in arbitrary order.
use fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
type Fxd = FixedU16<U0>;
let point = [Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(3)];
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&point, 10);
let mut pairs: Vec<_> = tree.iter().collect();
assert_eq!(pairs.pop().unwrap(), (10, point));Source§impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub 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>,
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>,
Queries the tree to find the best n elements within dist of point, using the specified
distance metric.
Returns an iterator.
Results are returned in arbitrary order. ‘Best’ is determined by
performing a comparison of the elements using < (ie, std::cmp::Ordering::is_lt).
§Examples
use fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::best_neighbour::BestNeighbour;
use kiddo::fixed::kdtree::KdTree;
use kiddo::fixed::distance::SquaredEuclidean;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 1);
tree.add(&[Fxd::from_num(20), Fxd::from_num(30), Fxd::from_num(60)], 102);
let mut best_n_within_iter = tree.best_n_within::<SquaredEuclidean>(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], Fxd::from_num(10), 1);
let first = best_n_within_iter.next().unwrap();
assert_eq!(first, BestNeighbour { distance: Fxd::from_num(3), item: 1 });Source§impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub fn nearest_n<D>(
&self,
query: &[A; K],
qty: usize,
) -> Vec<NearestNeighbour<A, T>>where
D: DistanceMetric<A, K>,
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 fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
use kiddo::fixed::distance::SquaredEuclidean;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
let nearest: Vec<_> = tree.nearest_n::<SquaredEuclidean>(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 1);
assert_eq!(nearest.len(), 1);
assert_eq!(nearest[0].distance, Fxd::from_num(0));
assert_eq!(nearest[0].item, 100);Source§impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub fn nearest_one<D>(&self, query: &[A; K]) -> NearestNeighbour<A, T>where
D: DistanceMetric<A, K>,
pub fn nearest_one<D>(&self, query: &[A; K]) -> NearestNeighbour<A, T>where
D: DistanceMetric<A, K>,
Queries the tree to find 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 fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
use kiddo::fixed::distance::SquaredEuclidean;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
let nearest = tree.nearest_one::<SquaredEuclidean>(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)]);
assert_eq!(nearest.distance, Fxd::from_num(0));
assert_eq!(nearest.item, 100);Source§impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub fn within<D>(&self, query: &[A; K], dist: A) -> Vec<NearestNeighbour<A, T>>where
D: DistanceMetric<A, K>,
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 fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
use kiddo::fixed::distance::SquaredEuclidean;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
tree.add(&[Fxd::from_num(20), Fxd::from_num(30), Fxd::from_num(60)], 102);
let within = tree.within::<SquaredEuclidean>(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], Fxd::from_num(10));
assert_eq!(within.len(), 2);Source§impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub fn within_unsorted<D>(
&self,
query: &[A; K],
dist: A,
) -> Vec<NearestNeighbour<A, T>>where
D: DistanceMetric<A, K>,
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 fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
use kiddo::fixed::distance::SquaredEuclidean;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
tree.add(&[Fxd::from_num(20), Fxd::from_num(30), Fxd::from_num(60)], 102);
let within = tree.within::<SquaredEuclidean>(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], Fxd::from_num(10));
assert_eq!(within.len(), 2);Source§impl<'a, A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
impl<'a, A: Axis, T: Content, const K: usize, const B: usize, IDX: Index<T = IDX>> KdTree<A, T, K, B, IDX>
Sourcepub fn within_unsorted_iter<D>(
&'a self,
query: &'a [A; K],
dist: A,
) -> WithinUnsortedIter<'a, A, T> ⓘwhere
D: DistanceMetric<A, K>,
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.
Only available on x86_64 and aarch64 target architectures (this is due to a dependency
on the generator crate).
Returns an Iterator. Results are returned in arbitrary order. Faster than within.
§Examples
use fixed::FixedU16;
use fixed::types::extra::U0;
use kiddo::fixed::kdtree::KdTree;
use kiddo::fixed::distance::SquaredEuclidean;
type Fxd = FixedU16<U0>;
let mut tree: KdTree<Fxd, u32, 3, 32, u32> = KdTree::new();
tree.add(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], 100);
tree.add(&[Fxd::from_num(2), Fxd::from_num(3), Fxd::from_num(6)], 101);
tree.add(&[Fxd::from_num(20), Fxd::from_num(30), Fxd::from_num(60)], 102);
let within = tree.within_unsorted_iter::<SquaredEuclidean>(&[Fxd::from_num(1), Fxd::from_num(2), Fxd::from_num(5)], Fxd::from_num(10)).collect::<Vec<_>>();
assert_eq!(within.len(), 2);Trait Implementations§
Source§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>
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>
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>
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>
Source§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>,
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>,
Source§fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>where
__D: Deserializer<'de>,
Source§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>
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>
Source§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>
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>
Source§fn extend<I: IntoIterator<Item = ([A; K], T)>>(&mut self, iter: I)
fn extend<I: IntoIterator<Item = ([A; K], T)>>(&mut self, iter: I)
Source§fn extend_one(&mut self, item: A)
fn extend_one(&mut self, item: A)
extend_one #72631)Source§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>
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>
Source§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>
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>
Source§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>
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>
impl<A: Copy + Default, T: Copy + Default, const K: usize, const B: usize, IDX> StructuralPartialEq for KdTree<A, T, K, B, IDX>
Auto Trait Implementations§
impl<A, T, const K: usize, const B: usize, IDX> Freeze for KdTree<A, T, K, B, IDX>
impl<A, T, const K: usize, const B: usize, IDX> RefUnwindSafe for KdTree<A, T, K, B, IDX>
impl<A, T, const K: usize, const B: usize, IDX> Send for KdTree<A, T, K, B, IDX>
impl<A, T, const K: usize, const B: usize, IDX> Sync for KdTree<A, T, K, B, IDX>
impl<A, T, const K: usize, const B: usize, IDX> Unpin for KdTree<A, T, K, B, IDX>
impl<A, T, const K: usize, const B: usize, IDX> UnwindSafe for KdTree<A, T, K, B, IDX>
Blanket Implementations§
Source§impl<T> ArchivePointee for T
impl<T> ArchivePointee for T
Source§type ArchivedMetadata = ()
type ArchivedMetadata = ()
Source§fn pointer_metadata(
_: &<T as ArchivePointee>::ArchivedMetadata,
) -> <T as Pointee>::Metadata
fn pointer_metadata( _: &<T as ArchivePointee>::ArchivedMetadata, ) -> <T as Pointee>::Metadata
Source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
Source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
Source§impl<T> CheckedAs for T
impl<T> CheckedAs for T
Source§fn checked_as<Dst>(self) -> Option<Dst>where
T: CheckedCast<Dst>,
fn checked_as<Dst>(self) -> Option<Dst>where
T: CheckedCast<Dst>,
Source§impl<Src, Dst> CheckedCastFrom<Src> for Dstwhere
Src: CheckedCast<Dst>,
impl<Src, Dst> CheckedCastFrom<Src> for Dstwhere
Src: CheckedCast<Dst>,
Source§fn checked_cast_from(src: Src) -> Option<Dst>
fn checked_cast_from(src: Src) -> Option<Dst>
Source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
Source§impl<F, W, T, D> Deserialize<With<T, W>, D> for F
impl<F, W, T, D> Deserialize<With<T, W>, D> for F
Source§impl<T> IntoEither for T
impl<T> IntoEither for T
Source§fn into_either(self, into_left: bool) -> Either<Self, Self>
fn into_either(self, into_left: bool) -> Either<Self, Self>
self into a Left variant of Either<Self, Self>
if into_left is true.
Converts self into a Right variant of Either<Self, Self>
otherwise. Read moreSource§fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
fn into_either_with<F>(self, into_left: F) -> Either<Self, Self>
self into a Left variant of Either<Self, Self>
if into_left(&self) returns true.
Converts self into a Right variant of Either<Self, Self>
otherwise. Read more