kd-tree
k-dimensional tree in Rust.
Fast, simple, and easy to use.
Usage
// construct kd-tree
let kdtree = build_by_ordered_float;
// search the nearest neighbor
let found = kdtree.nearest.unwrap;
assert_eq!;
// search k-nearest neighbors
let found = kdtree.nearests;
assert_eq!;
assert_eq!;
// search points within a sphere
let found = kdtree.within_radius;
assert_eq!;
assert!;
assert!;
With or without KdPoint
KdPoint
trait represents k-dimensional point.
You can live with or without KdPoint
.
With KdPoint
explicitly
use ;
// define your own item type.
// implement `KdPoint` for your item type.
// construct kd-tree from `Vec<Item>`.
// Note: you need to use `build_by_ordered_float()` because f64 doesn't implement `Ord` trait.
let kdtree: = build_by_ordered_float;
// search nearest item from [1.9, 3.1]
assert_eq!;
With KdPoint
implicitly
KdPoint
trait is implemented for fixed-sized array of numerical types, such as [f64; 3]
or [i32, 2]
etc.
So you can build kd-trees of those types without custom implementation of KdPoint
.
let items: = vec!;
let kdtree = build;
assert_eq!;
KdPoint
trait is also implemented for tuple of a KdPoint
and an arbitrary type, like (P, T)
where P: KdPoint
.
And a type alias named KdMap<P, T>
is defined as KdTree<(P, T)>
.
So you can build a kd-tree from key-value pairs, as below:
let kdmap: KdMap = build;
assert_eq!;
Without KdPoint
use HashMap;
let items: = vec!.into_iter.collect;
let kdtree = build_by_key;
assert_eq!;
To own, or not to own
KdSliceN<T, N>
and KdTreeN<T, N>
are similar to str
and String
, or Path
and PathBuf
.
KdSliceN<T, N>
doesn't own its buffer, butKdTreeN<T, N>
.KdSliceN<T, N>
is notSized
, so it must be dealed in reference mannar.KdSliceN<T, N>
implementsDeref
to[T]
.KdTreeN<T, N>
implementsDeref
toKdSliceN<T, N>
.- Unlike
PathBuf
orString
, which are mutable,KdTreeN<T, N>
is immutable.
&KdSliceN<T, N>
can be constructed directly, not via KdTreeN
, as below:
let mut items: = vec!;
let kdtree = sort;
assert_eq!;
KdIndexTreeN
A KdIndexTreeN
refers a slice of items, [T]
, and contains kd-tree of indices to the items, KdTreeN<usize, N>
.
Unlike [KdSlice::sort
], [KdIndexTree::build
] doesn't sort input items.
let items = vec!;
let kdtree = build;
assert_eq!; // nearest() returns an index of found item.