rstar/primitives/
cached_envelope.rs

1use crate::object::PointDistance;
2use crate::object::RTreeObject;
3use crate::{envelope::Envelope, object::Distance};
4use core::ops::Deref;
5
6/// An [RTreeObject] with an inner geometry whose envelope is cached to improve efficiency.
7///
8/// For complex geometry like polygons, computing the envelope can become a bottleneck during
9/// tree construction and querying. Hence this combinator computes it once during creation,
10/// stores it and then returns a copy.
11///
12/// **Note:** the container itself implements [RTreeObject] and inner geometry `T` can be
13/// accessed via an implementation of `Deref<Target=T>`.
14#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Default)]
15#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
16pub struct CachedEnvelope<T: RTreeObject> {
17    inner: T,
18    cached_env: T::Envelope,
19}
20
21impl<T: RTreeObject> RTreeObject for CachedEnvelope<T>
22where
23    T::Envelope: Clone,
24{
25    type Envelope = T::Envelope;
26
27    fn envelope(&self) -> Self::Envelope {
28        self.cached_env.clone()
29    }
30}
31
32impl<T: PointDistance> PointDistance for CachedEnvelope<T> {
33    fn distance_2(&self, point: &<Self::Envelope as Envelope>::Point) -> Distance<Self> {
34        self.inner.distance_2(point)
35    }
36
37    fn contains_point(&self, p: &<Self::Envelope as Envelope>::Point) -> bool {
38        self.inner.contains_point(p)
39    }
40
41    fn distance_2_if_less_or_equal(
42        &self,
43        point: &<Self::Envelope as Envelope>::Point,
44        max_distance_2: Distance<Self>,
45    ) -> Option<Distance<Self>> {
46        self.inner
47            .distance_2_if_less_or_equal(point, max_distance_2)
48    }
49}
50
51impl<T: RTreeObject> CachedEnvelope<T> {
52    /// Create a new [CachedEnvelope] struct using the provided geometry.
53    pub fn new(inner: T) -> Self {
54        let cached_env = inner.envelope();
55
56        Self { inner, cached_env }
57    }
58}
59
60impl<T: RTreeObject> Deref for CachedEnvelope<T> {
61    type Target = T;
62
63    fn deref(&self) -> &Self::Target {
64        &self.inner
65    }
66}
67
68#[cfg(test)]
69mod test {
70    use super::CachedEnvelope;
71    use crate::object::PointDistance;
72    use crate::primitives::GeomWithData;
73
74    use approx::*;
75
76    use crate::{primitives::Line, RTree};
77
78    #[test]
79    fn container_in_rtree() {
80        let line_1 = CachedEnvelope::new(Line::new([0.0, 0.0], [1.0, 1.0]));
81        let line_2 = CachedEnvelope::new(Line::new([0.0, 0.0], [-1.0, 1.0]));
82        let tree = RTree::bulk_load(vec![line_1, line_2]);
83
84        assert!(tree.contains(&line_1));
85    }
86
87    #[test]
88    fn container_edge_distance() {
89        let edge = CachedEnvelope::new(Line::new([0.5, 0.5], [0.5, 2.0]));
90
91        assert_abs_diff_eq!(edge.distance_2(&[0.5, 0.5]), 0.0);
92        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.5]), 0.5 * 0.5);
93        assert_abs_diff_eq!(edge.distance_2(&[0.5, 1.0]), 0.0);
94        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.0]), 0.5);
95        assert_abs_diff_eq!(edge.distance_2(&[0.0, 1.0]), 0.5 * 0.5);
96        assert_abs_diff_eq!(edge.distance_2(&[1.0, 1.0]), 0.5 * 0.5);
97        assert_abs_diff_eq!(edge.distance_2(&[1.0, 3.0]), 0.5 * 0.5 + 1.0);
98    }
99
100    #[test]
101    fn container_length_2() {
102        let line = CachedEnvelope::new(Line::new([1, -1], [5, 5]));
103
104        assert_eq!(line.length_2(), 16 + 36);
105    }
106
107    #[test]
108    fn container_nearest_neighbour() {
109        let mut lines = RTree::new();
110        lines.insert(GeomWithData::new(
111            CachedEnvelope::new(Line::new([0.0, 0.0], [1.0, 1.0])),
112            "Line A",
113        ));
114        lines.insert(GeomWithData::new(
115            CachedEnvelope::new(Line::new([0.0, 0.0], [-1.0, 1.0])),
116            "Line B",
117        ));
118        let my_location = [0.0, 0.0];
119        // Now find the closest line
120        let place = lines.nearest_neighbor(my_location).unwrap();
121
122        assert_eq!(place.data, "Line A");
123    }
124}
rstar/primitives/cached_envelope.rs

rstar/primitives/
cached_envelope.rs
