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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

use num_traits::Float;

pub fn distance_to_space<F, T>(p1: &[T], min_bounds: &[T], max_bounds: &[T], distance: &F) -> T
where
    F: Fn(&[T], &[T]) -> T,
    T: Float,
{
    let mut p2 = vec![T::nan(); p1.len()];
    for i in 0..p1.len() {
        if p1[i] > max_bounds[i] {
            p2[i] = max_bounds[i];
        } else if p1[i] < min_bounds[i] {
            p2[i] = min_bounds[i];
        } else {
            p2[i] = p1[i];
        }
    }
    distance(p1, &p2[..])
}

pub fn within_bounding_box<T>(p: &[T], min_bounds: &[T], max_bounds: &[T]) -> bool
where
    T: Float,
{
    for ((l, h), v) in min_bounds.iter().zip(max_bounds.iter()).zip(p) {
        if v < l || v > h {
            return false;
        }
    }
    true
}

#[cfg(test)]
mod tests {
    use super::distance_to_space;
    use super::within_bounding_box;
    use crate::distance::squared_euclidean;

    #[test]
    fn test_normal_distance_to_space() {
        let dis = distance_to_space(&[0.0, 0.0], &[1.0, 1.0], &[2.0, 2.0], &squared_euclidean);
        assert_eq!(dis, 2.0);
    }

    #[test]
    fn test_distance_outside_inf() {
        let dis = distance_to_space(
            &[0.0, 0.0],
            &[1.0, 1.0],
            &[f64::INFINITY, f64::INFINITY],
            &squared_euclidean,
        );
        assert_eq!(dis, 2.0);
    }

    #[test]
    fn test_distance_inside_inf() {
        let dis = distance_to_space(
            &[2.0, 2.0],
            &[f64::NEG_INFINITY, f64::NEG_INFINITY],
            &[f64::INFINITY, f64::INFINITY],
            &squared_euclidean,
        );
        assert_eq!(dis, 0.0);
    }

    #[test]
    fn test_distance_inside_normal() {
        let dis = distance_to_space(&[2.0, 2.0], &[0.0, 0.0], &[3.0, 3.0], &squared_euclidean);
        assert_eq!(dis, 0.0);
    }

    #[test]
    fn distance_to_half_space() {
        let dis = distance_to_space(
            &[-2.0, 0.0],
            &[0.0, f64::NEG_INFINITY],
            &[f64::INFINITY, f64::INFINITY],
            &squared_euclidean,
        );
        assert_eq!(dis, 4.0);
    }

    #[test]
    fn test_within_bounding_box() {
        assert!(within_bounding_box(&[1.0, 1.0], &[0.0, 0.0], &[2.0, 2.0]));
        assert!(within_bounding_box(&[1.0, 1.0], &[1.0, 1.0], &[2.0, 2.0]));
        assert!(within_bounding_box(&[1.0, 1.0], &[0.0, 0.0], &[1.0, 1.0]));
        assert!(!within_bounding_box(&[2.0, 2.0], &[0.0, 0.0], &[1.0, 1.0]));
        assert!(!within_bounding_box(&[0.0, 0.0], &[1.0, 1.0], &[2.0, 2.0]));
    }
}