kdtree 0.8.0

K-dimensional tree in Rust for fast geospatial indexing and nearest neighbors lookup
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

extern crate kdtree;

use kdtree::KdTree;
use kdtree::distance::squared_euclidean;
use std::sync::atomic::{AtomicUsize, Ordering};

static POINT_A: ([f64; 2], usize) = ([0f64, 0f64], 0);
static POINT_B: ([f64; 2], usize) = ([1f64, 1f64], 1);
static POINT_C: ([f64; 2], usize) = ([2f64, 2f64], 2);
static POINT_D: ([f64; 2], usize) = ([3f64, 3f64], 3);

#[test]
fn it_works() {
    let dimensions = 2;
    let capacity_per_node = 2;
    let mut kdtree = KdTree::with_capacity(dimensions, capacity_per_node);

    let count = AtomicUsize::new(0);
    let new_dist = |a: &[f64], b: &[f64]| {
        count.fetch_add(1, Ordering::SeqCst);
        squared_euclidean(a, b)
    };

    kdtree.add(&POINT_A.0, POINT_A.1).unwrap();
    kdtree.add(&POINT_B.0, POINT_B.1).unwrap();
    kdtree.add(&POINT_C.0, POINT_C.1).unwrap();
    kdtree.add(&POINT_D.0, POINT_D.1).unwrap();

    kdtree.nearest(&POINT_A.0, 0, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 0);

    kdtree.nearest(&POINT_A.0, 1, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 2);

    kdtree.nearest(&POINT_A.0, 2, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 4);

    kdtree.nearest(&POINT_A.0, 3, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 6);

    kdtree.nearest(&POINT_A.0, 4, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 6);

    kdtree.nearest(&POINT_A.0, 5, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 6);

    kdtree.nearest(&POINT_B.0, 4, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 6);

    kdtree.within(&POINT_A.0, 0.0, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 2);

    kdtree.within(&POINT_B.0, 1.0, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 3);

    kdtree.within(&POINT_B.0, 2.0, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 6);

    let mut iter = kdtree.iter_nearest(&POINT_A.0, &new_dist).unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 0);

    iter.next().unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 2);

    iter.next().unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 2);

    iter.next().unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 2);

    iter.next().unwrap();
    assert_eq!(count.swap(0, Ordering::SeqCst), 0);
}