Rust-Kdtree rs: kdtree-rs — K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup

kdtree Build Status

K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup

Usage

Add kdtree to Cargo.toml

[dependencies]
kdtree = "0.5.1"

Add points to kdtree and query nearest n points with distance function

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)]
);

Benchmark

cargo bench with 2.3 GHz Intel i5-7360U:

cargo bench
     Running target/release/deps/bench-9e622e6a4ed9b92a

running 2 tests
test bench_add_to_kdtree_with_1k_3d_points       ... bench:         106 ns/iter (+/- 25)
test bench_nearest_from_kdtree_with_1k_3d_points ... bench:       1,237 ns/iter (+/- 266)

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

Thanks Eh2406 for various fixes and perf improvements.

License

Licensed under either of

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

Comments

  • Stack overflow in add_to_bucket
    Stack overflow in add_to_bucket

    Sep 20, 2018

    I haven't minimised yet, but in some circumstances, add_to_bucket results in a stack overflow. Without looking too closely, I think there's an infinite (or exponential) loop where add_to_bucket calls split, which in turn calls add_to_bucket, etc.

    Edit: If I create a KdTree with sufficient capacity to begin with, the stack overflow doesn't occur, so the problem is with it dynamically resizing.

    Reply
  • remove points after add?
    remove points after add?

    Feb 3, 2020

    Hi,

    will it be possible to remove points as well in the future? Afaik no (kd|...)tree library for Rust does allow it. Would be nice to have.

    Thanks

    Reply
  • Use failure
    Use failure

    Nov 29, 2018

    New error management with failure crate.

    Reply
  • fixed clippy warnings
    fixed clippy warnings

    Mar 21, 2016

    Warning: This changes the algorithms in a few places (e.g. not to use NaNs in KdTree::extend(..)). See my line notes for further information.

    Reply
  • Some cleanups
    Some cleanups

    Nov 29, 2018

    • Run cargo fmt
    • Run cargo +nightly clippy and fixed warnings
    • Run cargo fix --edition
    • Fixed docs in src/distance.rs, and other cosmetic changes
    • Replaced assert!(x == y) with assert_eq!(x, y)
    Reply
  • Bug: distance_to_space on wrong thing. Massive performance wins.
    Bug: distance_to_space on wrong thing. Massive performance wins.

    Jul 12, 2016

    This is big! I stumbled on this experimenting with a refactoring.

    New bench:

    running 2 tests
    test bench_add_to_kdtree_with_1k_3d_points       ... bench:         156 ns/iter (+/- 44)
    test bench_nearest_from_kdtree_with_1k_3d_points ... bench:       3,603 ns/iter (+/- 3,217)
    

    Old bench:

    running 2 tests
    test bench_add_to_kdtree_with_1k_3d_points       ... bench:         139 ns/iter (+/- 61)
    test bench_nearest_from_kdtree_with_1k_3d_points ... bench:       6,677 ns/iter (+/- 6,613)
    

    Maby evan "0.3.1"?

    Reply
  • Rename `KdTree::new_with_capacity()` to `with_capcity()`
    Rename `KdTree::new_with_capacity()` to `with_capcity()`

    Nov 30, 2018

    Rename KdTree::new_with_capacity() to with_capcity(), which follows Rust naming convention.

    Reply
  • Add failure, derive fail for error kind
    Add failure, derive fail for error kind

    Nov 22, 2017

    This implements std::error::Error for ErrorKind as well.

    Reply