kdtree implementation for rust.
Implementation uses sliding midpoint variation of the tree. More Info here
Implementation uses single Vec<Node> to store all its contents, allowing for quick access, and no memory fragmentation.
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 #2.
Examplary implementation would be:
```
pub struct Point3WithId {
dims: [f64; 3],
pub id: i32,
}
impl KdtreePointTrait for Point3WithId {
#[inline] // the inline on this method is important! as without it there is ~25% speed loss on the tree when cross-crate usage.
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, It does support adding the nodes with method 'insert_node' and there is indeed a code to rebuild the tree if depths grows substantially. 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 );
}
``
Although not recommended for the kd-tree you can use theinsertnodeandinsertnodesandrebuildfunctions to add nodes to the tree.insertnodedoes silly check to check whether the tree should be rebuilt.insertnodesandrebuild` Automatically rebuilds the tree.
for now the removal of the nodes is not supported.
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_adding_same_node_to_1000_tree ... bench: 42 ns/iter (+/- 11)
test bench_creating_1000_node_tree ... bench: 120,310 ns/iter (+/- 4,746)
test bench_single_lookup_times_for_1000_node_tree ... bench: 164 ns/iter (+/- 139)
test result: ok. 0 passed; 0 failed; 0 ignored; 4 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