spart 0.5.1

A collection of space partitioning tree data structures for Rust
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

#[path = "shared.rs"]
mod shared;
use shared::*;

use spart::geometry::EuclideanDistance;
use spart::quadtree::Quadtree;
use tracing::{debug, info};

fn run_quadtree_2d_test() {
    info!("Starting Quadtree 2D test");

    let boundary = BOUNDARY_RECT;
    let mut tree = Quadtree::new(&boundary, CAPACITY).unwrap();
    info!("Created quadtree with boundary: {:?}", boundary);

    let points = common_points_2d();
    for pt in &points {
        tree.insert(pt.clone());
        debug!("Inserted point: {:?}", pt);
    }
    info!("Finished inserting {} points", points.len());

    // kNN search test
    let target = target_point_2d();
    info!("Performing kNN search for target: {:?}", target);
    let knn_results = tree.knn_search::<EuclideanDistance>(&target, KNN_COUNT);
    info!("kNN search returned {} results", knn_results.len());
    assert_eq!(
        knn_results.len(),
        KNN_COUNT,
        "Expected {} nearest neighbors, got {}",
        KNN_COUNT,
        knn_results.len()
    );
    let mut prev_dist = 0.0;
    for pt in &knn_results {
        let d = distance_2d(&target, pt);
        debug!("kNN: Point {:?} at distance {}", pt, d);
        assert!(
            d >= prev_dist,
            "kNN results not sorted by increasing distance"
        );
        prev_dist = d;
    }

    // Range search test
    let range_query = range_query_point_2d();
    info!(
        "Performing range search for query point {:?} with radius {}",
        range_query, RADIUS
    );
    let range_results = tree.range_search::<EuclideanDistance>(&range_query, RADIUS);
    info!("Range search returned {} points", range_results.len());
    for pt in &range_results {
        let d = distance_2d(&range_query, pt);
        debug!("Range: Point {:?} at distance {}", pt, d);
        assert!(
            d <= RADIUS,
            "Point {:?} is at distance {} which exceeds radius {}",
            pt,
            d,
            RADIUS
        );
    }
    assert!(
        range_results.len() >= 5,
        "Expected at least 5 points in range, got {}",
        range_results.len()
    );

    info!("Quadtree 2D test completed successfully");
}

#[test]
fn test_quadtree_2d() {
    run_quadtree_2d_test();
}

#[test]
fn test_quadtree_insert_bulk() {
    let boundary = BOUNDARY_RECT;
    let mut tree = Quadtree::new(&boundary, CAPACITY).unwrap();
    let points = common_points_2d();
    tree.insert_bulk(&points);

    let target = target_point_2d();
    let knn_results = tree.knn_search::<EuclideanDistance>(&target, KNN_COUNT);
    assert_eq!(
        knn_results.len(),
        KNN_COUNT,
        "Expected {} nearest neighbors, got {}",
        KNN_COUNT,
        knn_results.len()
    );
}