Crate kdtree 

kdtree

K-dimensional tree for Rust (bucket point-region implementation)

Usage

use kdtree::KdTree;
use kdtree::ErrorKind;
use kdtree::distance::squared_euclidean;

let a: ([f64; 2], usize) = ([0f64, 0f64], 0);
let b: ([f64; 2], usize) = ([1f64, 1f64], 1);
let c: ([f64; 2], usize) = ([2f64, 2f64], 2);
let d: ([f64; 2], usize) = ([3f64, 3f64], 3);

let dimensions = 2;
let mut kdtree = KdTree::new(dimensions);

kdtree.add(&a.0, a.1).unwrap();
kdtree.add(&b.0, b.1).unwrap();
kdtree.add(&c.0, c.1).unwrap();
kdtree.add(&d.0, d.1).unwrap();

assert_eq!(kdtree.size(), 4);
assert_eq!(
    kdtree.nearest(&a.0, 0, &squared_euclidean).unwrap(),
    vec![]
);
assert_eq!(
    kdtree.nearest(&a.0, 1, &squared_euclidean).unwrap(),
    vec![(0f64, &0)]
);
assert_eq!(
    kdtree.nearest(&a.0, 2, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1)]
);
assert_eq!(
    kdtree.nearest(&a.0, 3, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1), (8f64, &2)]
);
assert_eq!(
    kdtree.nearest(&a.0, 4, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1), (8f64, &2), (18f64, &3)]
);
assert_eq!(
    kdtree.nearest(&a.0, 5, &squared_euclidean).unwrap(),
    vec![(0f64, &0), (2f64, &1), (8f64, &2), (18f64, &3)]
);
assert_eq!(
    kdtree.nearest(&b.0, 4, &squared_euclidean).unwrap(),
    vec![(0f64, &1), (2f64, &0), (2f64, &2), (8f64, &3)]
);
assert_eq!(
    kdtree
        .nearest_within_radius(&a.0, 4, Some(5f64), &squared_euclidean)
        .unwrap(),
    vec![(0f64, &0), (2f64, &1)]
);

nearest_within_radius keeps the exact ordering guarantees of nearest; it still truncates by k and only filters out items whose distance exceeds the optional radius. Mutating results remains an iterator-only operation (e.g. iter_nearest_within_radius_mut) so the tree never hands out overlapping mutable borrows.

within (and within_count) produce unordered batches that include every point inside the requested radius—sort the returned vector manually if you need a deterministic order. Use bounding_box for axis-aligned range queries when you only need raw &T references without ordering guarantees.

Re-exports

pub use crate::kdtree::ErrorKind;

pub use crate::kdtree::KdTree;

Modules

distance

Defines different distance metrics, in simplest case it defines the euclidean distance which is no more than the square root of the sum of the squares of the distances in each dimension.

kdtree