rstar/primitives/
cached_envelope.rs

1use crate::envelope::Envelope;
2use crate::object::PointDistance;
3use crate::{object::RTreeObject, point::Point};
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(
34        &self,
35        point: &<Self::Envelope as Envelope>::Point,
36    ) -> <<Self::Envelope as Envelope>::Point as Point>::Scalar {
37        self.inner.distance_2(point)
38    }
39
40    fn contains_point(&self, p: &<Self::Envelope as Envelope>::Point) -> bool {
41        self.inner.contains_point(p)
42    }
43
44    fn distance_2_if_less_or_equal(
45        &self,
46        point: &<Self::Envelope as Envelope>::Point,
47        max_distance_2: <<Self::Envelope as Envelope>::Point as Point>::Scalar,
48    ) -> Option<<<Self::Envelope as Envelope>::Point as Point>::Scalar> {
49        self.inner
50            .distance_2_if_less_or_equal(point, max_distance_2)
51    }
52}
53
54impl<T: RTreeObject> CachedEnvelope<T> {
55    /// Create a new [CachedEnvelope] struct using the provided geometry.
56    pub fn new(inner: T) -> Self {
57        let cached_env = inner.envelope();
58
59        Self { inner, cached_env }
60    }
61}
62
63impl<T: RTreeObject> Deref for CachedEnvelope<T> {
64    type Target = T;
65
66    fn deref(&self) -> &Self::Target {
67        &self.inner
68    }
69}
70
71#[cfg(test)]
72mod test {
73    use super::CachedEnvelope;
74    use crate::object::PointDistance;
75    use crate::primitives::GeomWithData;
76
77    use approx::*;
78
79    use crate::{primitives::Line, RTree};
80
81    #[test]
82    fn container_in_rtree() {
83        let line_1 = CachedEnvelope::new(Line::new([0.0, 0.0], [1.0, 1.0]));
84        let line_2 = CachedEnvelope::new(Line::new([0.0, 0.0], [-1.0, 1.0]));
85        let tree = RTree::bulk_load(vec![line_1, line_2]);
86
87        assert!(tree.contains(&line_1));
88    }
89
90    #[test]
91    fn container_edge_distance() {
92        let edge = CachedEnvelope::new(Line::new([0.5, 0.5], [0.5, 2.0]));
93
94        assert_abs_diff_eq!(edge.distance_2(&[0.5, 0.5]), 0.0);
95        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.5]), 0.5 * 0.5);
96        assert_abs_diff_eq!(edge.distance_2(&[0.5, 1.0]), 0.0);
97        assert_abs_diff_eq!(edge.distance_2(&[0.0, 0.0]), 0.5);
98        assert_abs_diff_eq!(edge.distance_2(&[0.0, 1.0]), 0.5 * 0.5);
99        assert_abs_diff_eq!(edge.distance_2(&[1.0, 1.0]), 0.5 * 0.5);
100        assert_abs_diff_eq!(edge.distance_2(&[1.0, 3.0]), 0.5 * 0.5 + 1.0);
101    }
102
103    #[test]
104    fn container_length_2() {
105        let line = CachedEnvelope::new(Line::new([1, -1], [5, 5]));
106
107        assert_eq!(line.length_2(), 16 + 36);
108    }
109
110    #[test]
111    fn container_nearest_neighbour() {
112        let mut lines = RTree::new();
113        lines.insert(GeomWithData::new(
114            CachedEnvelope::new(Line::new([0.0, 0.0], [1.0, 1.0])),
115            "Line A",
116        ));
117        lines.insert(GeomWithData::new(
118            CachedEnvelope::new(Line::new([0.0, 0.0], [-1.0, 1.0])),
119            "Line B",
120        ));
121        let my_location = [0.0, 0.0];
122        // Now find the closest line
123        let place = lines.nearest_neighbor(&my_location).unwrap();
124
125        assert_eq!(place.data, "Line A");
126    }
127}
rstar/primitives/cached_envelope.rs

rstar/primitives/
cached_envelope.rs
