Crate kd_tree

Expand description

k-dimensional tree.

Usage

// construct kd-tree
let kdtree = kd_tree::KdTree::build_by_ordered_float(vec![
    [1.0, 2.0, 3.0],
    [3.0, 1.0, 2.0],
    [2.0, 3.0, 1.0],
]);

// search the nearest neighbor
let found = kdtree.nearest(&[3.1, 0.9, 2.1]).unwrap();
assert_eq!(found.item, &[3.0, 1.0, 2.0]);

// search k-nearest neighbors
let found = kdtree.nearests(&[1.5, 2.5, 1.8], 2);
assert_eq!(found[0].item, &[2.0, 3.0, 1.0]);
assert_eq!(found[1].item, &[1.0, 2.0, 3.0]);

// search points within a sphere
let found = kdtree.within_radius(&[2.0, 1.5, 2.5], 1.5);
assert_eq!(found.len(), 2);
assert!(found.iter().any(|&&p| p == [1.0, 2.0, 3.0]));
assert!(found.iter().any(|&&p| p == [3.0, 1.0, 2.0]));

Structs

ItemAndDistance

KdIndexTreeN

This type refers a slice of items, [T], and contains kd-tree of indices to the items, KdTree<usize, N>. Unlike KdSliceN::sort, KdIndexTreeN::build doesn’t sort input items.

KdSliceN

A slice of kd-tree. This type implements std::ops::Deref to [T]. This is an unsized type, meaning that it must always be used as a reference. For an owned version of this type, see KdTree.

KdTreeN

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