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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

use crate::envelope::Envelope;
use crate::object::PointDistance;
use crate::{object::RTreeObject, point::Point};
use core::ops::Deref;

/// An [RTreeObject] with an inner geometry whose envelope is cached to improve efficiency.
///
/// For complex geometry like polygons, computing the envelope can become a bottleneck during
/// tree construction and querying. Hence this combinator computes it once during creation,
/// stores it and then returns a copy.
///
/// **Note:** the container itself implements [RTreeObject] and inner geometry `T` can be
/// accessed via an implementation of `Deref<Target=T>`.
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct CachedEnvelope<T: RTreeObject> {
    inner: T,
    cached_env: T::Envelope,
}

impl<T: RTreeObject> RTreeObject for CachedEnvelope<T>
where
    T::Envelope: Clone,
{
    type Envelope = T::Envelope;

    fn envelope(&self) -> Self::Envelope {
        self.cached_env.clone()
    }
}

impl<T: PointDistance> PointDistance for CachedEnvelope<T> {
    fn distance_2(
        &self,
        point: &<Self::Envelope as Envelope>::Point,
    ) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar {
        self.inner.distance_2(point)
    }

    fn contains_point(&self, p: &<Self::Envelope as Envelope>::Point) -> bool {
        self.inner.contains_point(p)
    }

    fn distance_2_if_less_or_equal(
        &self,
        point: &<Self::Envelope as Envelope>::Point,
        max_distance_2: <<Self::Envelope as Envelope>::Point as Point>::Scalar,
    ) -> Option<<<Self::Envelope as Envelope>::Point as Point>::Scalar> {
        self.inner
            .distance_2_if_less_or_equal(point, max_distance_2)
    }
}

impl<T: RTreeObject> CachedEnvelope<T> {
    /// Create a new [CachedEnvelope] struct using the provided geometry.
    pub fn new(inner: T) -> Self {
        let cached_env = inner.envelope();

        Self { inner, cached_env }
    }
}

impl<T: RTreeObject> Deref for CachedEnvelope<T> {
    type Target = T;

    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}

#[cfg(test)]
mod test {
    use super::CachedEnvelope;
    use crate::object::PointDistance;
    use crate::primitives::GeomWithData;

    use approx::*;

    use crate::{primitives::Line, RTree};

    #[test]
    fn container_in_rtree() {
        let line_1 = CachedEnvelope::new(Line::new([0.0, 0.0], [1.0, 1.0]));
        let line_2 = CachedEnvelope::new(Line::new([0.0, 0.0], [-1.0, 1.0]));
        let tree = RTree::bulk_load(vec![line_1, line_2]);

        assert!(tree.contains(&line_1));
    }

    #[test]
    fn container_edge_distance() {
        let edge = CachedEnvelope::new(Line::new([0.5, 0.5], [0.5, 2.0]));

        assert_abs_diff_eq!(edge.distance_2(&[0.5, 0.5]), 0.0);
        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.5]), 0.5 * 0.5);
        assert_abs_diff_eq!(edge.distance_2(&[0.5, 1.0]), 0.0);
        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.0]), 0.5);
        assert_abs_diff_eq!(edge.distance_2(&[0.0, 1.0]), 0.5 * 0.5);
        assert_abs_diff_eq!(edge.distance_2(&[1.0, 1.0]), 0.5 * 0.5);
        assert_abs_diff_eq!(edge.distance_2(&[1.0, 3.0]), 0.5 * 0.5 + 1.0);
    }

    #[test]
    fn container_length_2() {
        let line = CachedEnvelope::new(Line::new([1, -1], [5, 5]));

        assert_eq!(line.length_2(), 16 + 36);
    }

    #[test]
    fn container_nearest_neighbour() {
        let mut lines = RTree::new();
        lines.insert(GeomWithData::new(
            CachedEnvelope::new(Line::new([0.0, 0.0], [1.0, 1.0])),
            "Line A",
        ));
        lines.insert(GeomWithData::new(
            CachedEnvelope::new(Line::new([0.0, 0.0], [-1.0, 1.0])),
            "Line B",
        ));
        let my_location = [0.0, 0.0];
        // Now find the closest line
        let place = lines.nearest_neighbor(&my_location).unwrap();

        assert_eq!(place.data, "Line A");
    }
}