kdtree

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

• Crate
• Documentation
• Usage
• Benchmark
• License

Usage

Add kdtree to Cargo.toml toml [dependencies] kdtree = "~0.1.0" or toml [dependencies.kdtree] git = "https://github.com/mrhooray/kdtree-rs"

```rust use kdtree::KdTree; use kdtree::ErrorKind; use kdtree::distance::square_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 kd_tree = 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();

asserteq!(kdtree.size(), 4); asserteq!( kdtree.nearest(&a.0, 0, &squareeuclidean).unwrap(), vec![] ); asserteq!( kdtree.nearest(&a.0, 1, &squareeuclidean).unwrap(), vec![(0f64, &0)] ); asserteq!( kdtree.nearest(&a.0, 2, &squareeuclidean).unwrap(), vec![(0f64, &0), (2f64, &1)] ); asserteq!( kdtree.nearest(&a.0, 3, &squareeuclidean).unwrap(), vec![(0f64, &0), (2f64, &1), (8f64, &2)] ); asserteq!( kdtree.nearest(&a.0, 4, &squareeuclidean).unwrap(), vec![(0f64, &0), (2f64, &1), (8f64, &2), (18f64, &3)] ); asserteq!( kdtree.nearest(&a.0, 5, &squareeuclidean).unwrap(), vec![(0f64, &0), (2f64, &1), (8f64, &2), (18f64, &3)] ); asserteq!( kdtree.nearest(&b.0, 4, &square_euclidean).unwrap(), vec![(0f64, &1), (2f64, &0), (2f64, &2), (8f64, &3)] ); ```

Benchmark

cargo bench with 2.3 GHz Intel Core i7: ``` cargo bench Running target/release/bench-a26a346635ebfc8f

running 2 tests test benchaddat1k3dpoints ... bench: 116 ns/iter (+/- 24) test benchnearestat1k3dpoints ... bench: 2,661 ns/iter (+/- 1,769)

test result: ok. 0 passed; 0 failed; 0 ignored; 2 measured ```

License

MIT