kdtree implementation for rust.
Implementation uses sliding midpoint variation of the tree. More Info here
Tree can only be used with types implementing trait:
pub trait KdtreePointTrait : Copy {
fn dims(&self) -> &[f64];
}
Thanks to this trait you can use any dimension. Keep in mind that the tree currently only supports up to 3D.
Examplary implementation would be:
```
pub struct Point3WithId {
dims: [f64; 3],
pub id: i32,
}
impl KdtreePointTrait for Point3WithId {
fn dims(&self) -> &[f64] {
return &self.dims;
}
}
Where id is just a example of the way in which I carry the data.
With that trait implemented you are good to go to use the tree. Keep in mind that the kdtree is not a self balancing tree, so it should not support continous add. right now the tree just handles the build up from Vec. Basic usage can be found in the integration test, fragment copied below:
let tree = kdtree::kdtree::Kdtree::new(&mut points.clone());
//test points pushed into the tree, id should be equal. for i in 0 .. point_count { let p = &points[i];
assert_eq!(p.id, tree.nearest_search(p).id );
} ```
cargo bench using travis :)
running 3 tests
test bench_creating_1000_000_node_tree ... bench: 275,155,622 ns/iter (+/- 32,713,321)
test bench_creating_1000_node_tree ... bench: 121,314 ns/iter (+/- 1,977)
test bench_single_loop_times_for_1000_node_tree ... bench: 162 ns/iter (+/- 76)
test result: ok. 0 passed; 0 failed; 0 ignored; 3 measured
~275ms to create a 1000_000 node tree. << this bench is now disabled.
~120us to create a 1000 node tree.
160ns to query the tree.
Since raw values arent saying much I've created the benchmark comparing this implementation against CGAL. code of the benchmark is available here: https://github.com/fulara/kdtree-benchmarks ```
Cgaltreebuildup/10 2226 ns 2221 ns 313336
Cgaltreebuildup/100 18357 ns 18315 ns 37968
Cgaltreebuildup/1000 288135 ns 287345 ns 2369
Cgaltreebuildup/9.76562k 3296740 ns 3290815 ns 211
Cgaltreebuildup/97.6562k 42909150 ns 42813307 ns 12
Cgaltreebuildup/976.562k 734566227 ns 733267760 ns 1
Cgaltreelookup/10 72 ns 72 ns 9392612
Cgaltreelookup/100 95 ns 95 ns 7103628
Cgaltreelookup/1000 174 ns 174 ns 4010773
Cgaltreelookup/9.76562k 268 ns 267 ns 2759487
Cgaltreelookup/97.6562k 881 ns 876 ns 1262454
Cgaltreelookup/976.562k 993 ns 991 ns 713751
Rusttreebuildup/10 726 ns 724 ns 856791
Rusttreebuildup/100 7103 ns 7092 ns 96132
Rusttreebuildup/1000 84879 ns 84720 ns 7927
Rusttreebuildup/9.76562k 1012983 ns 1010856 ns 630
Rusttreebuildup/97.6562k 12406293 ns 12382399 ns 51
Rusttreebuildup/976.562k 197175067 ns 196763387 ns 3
Rusttreelookup/10 62 ns 62 ns 11541505
Rusttreelookup/100 139 ns 139 ns 4058837
Rusttreelookup/1000 220 ns 220 ns 2890813
Rusttreelookup/9.76562k 307 ns 307 ns 2508133
Rusttreelookup/97.6562k 362 ns 362 ns 2035671
Rusttreelookup/976.562k 442 ns 441 ns 1636130
```
Rusttreelookup has some overhead since the libraries are being invoked from C code into Rust, and there is minor overhead of that in between, my experience indicates around 50 ns overhead.
The Unlicense