fux_kdtree 0.2.0

K-dimensional tree implemented in Rust for fast NN querying.
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
74
75
76
77

#[macro_use] extern crate bencher;
extern crate kdtree;
extern crate rand;

use bencher::Bencher;
use rand::Rng;

use kdtree::kdtree::test_common::*;

fn gen_random() -> f64 {
    rand::thread_rng().gen_range(0., 10000.)
}

fn generate_points(point_count: usize) -> Vec<Point3WithId> {
    let mut points: Vec<Point3WithId> = vec![];

    for i in 0..point_count {
        points.push(Point3WithId::new(i as i32, gen_random(), gen_random(), gen_random()));
    }

    points
}

fn bench_creating_1000_node_tree(b: &mut Bencher) {
    let len = 1000usize;
    let points = generate_points(len);

    b.iter(|| {
        kdtree::kdtree::Kdtree::new(&mut points.clone());
    });
}

fn bench_single_loop_times_for_1000_node_tree(b: &mut Bencher) {
    let len = 1000usize;
    let points = generate_points(len);

    let tree = kdtree::kdtree::Kdtree::new(&mut points.clone());


    b.iter(|| tree.nearest_search(&points[0]));
}

#[allow(dead_code)]
fn bench_creating_1000_000_node_tree(b: &mut Bencher) {
    let len = 1000_000usize;
    let points = generate_points(len);

    b.iter(|| {
        kdtree::kdtree::Kdtree::new(&mut points.clone());
    });
}

fn bench_adding_same_node_to_1000_tree(b: &mut Bencher) {
    let len = 1000usize;
    let mut points = generate_points(len);
    let mut tree = kdtree::kdtree::Kdtree::new(&mut points);

    let point = Point3WithId::new(-1 as i32, gen_random(), gen_random(), gen_random());
    b.iter(|| {
        tree.insert_node(point);
    });
}

fn bench_incrementally_building_the_1000_tree(b: &mut Bencher) {
    b.iter(|| {
        let len = 1usize;
        let mut points = generate_points(len);
        let mut tree = kdtree::kdtree::Kdtree::new(&mut points);
        for _ in 0 .. 1000 {
            let point = Point3WithId::new(-1 as i32, gen_random(), gen_random(), gen_random());
            tree.insert_node(point);
        }
    });
}

benchmark_group!(benches, bench_creating_1000_node_tree, bench_single_loop_times_for_1000_node_tree,bench_adding_same_node_to_1000_tree,bench_incrementally_building_the_1000_tree);
benchmark_main!(benches);