rstar/algorithm/
selection_functions.rs

1use crate::envelope::Envelope;
2use crate::object::PointDistance;
3use crate::object::RTreeObject;
4use crate::Point;
5
6/// Advanced trait to iterate through an r-tree. Usually it should not be required to be implemented.
7///
8/// It is important to know some details about the inner structure of
9/// r-trees to understand this trait. Any node in an r-tree is either a *leaf* (containing exactly one `T: RTreeObject`) or
10/// a *parent* (containing multiple nodes).
11/// The main benefit of r-trees lies in their ability to efficiently guide searches through
12/// the tree. This is done by *pruning*: Knowing the envelopes of parent nodes
13/// often allows the search to completely skip them and all contained children instead of having
14/// to iterate through them, e.g. when searching for elements in a non-intersecting envelope.
15/// This often reduces the expected time from `O(n)` to `O(log(n))`.
16///
17/// This trait can be used to define searches through the r-tree by defining whether a node
18/// should be further investigated ("unpacked") or pruned.
19///
20/// Usually, the various `locate_[...]` methods of [`super::super::RTree`] should cover most
21/// common searches. Otherwise, implementing `SelectionFunction` and using
22/// [`crate::RTree::locate_with_selection_function`]
23/// can be used to tailor a custom search.
24pub trait SelectionFunction<T>
25where
26    T: RTreeObject,
27{
28    /// Return `true` if a parent node should be unpacked during a search.
29    ///
30    /// The parent node's envelope is given to guide the decision.
31    fn should_unpack_parent(&self, envelope: &T::Envelope) -> bool;
32
33    /// Returns `true` if a given child node should be returned during a search.
34    /// The default implementation will always return `true`.
35    fn should_unpack_leaf(&self, _leaf: &T) -> bool {
36        true
37    }
38}
39
40pub struct SelectInEnvelopeFunction<T>
41where
42    T: RTreeObject,
43{
44    envelope: T::Envelope,
45}
46
47impl<T> SelectInEnvelopeFunction<T>
48where
49    T: RTreeObject,
50{
51    pub fn new(envelope: T::Envelope) -> Self {
52        SelectInEnvelopeFunction { envelope }
53    }
54}
55
56impl<T> SelectionFunction<T> for SelectInEnvelopeFunction<T>
57where
58    T: RTreeObject,
59{
60    fn should_unpack_parent(&self, parent_envelope: &T::Envelope) -> bool {
61        self.envelope.intersects(parent_envelope)
62    }
63
64    fn should_unpack_leaf(&self, leaf: &T) -> bool {
65        self.envelope.contains_envelope(&leaf.envelope())
66    }
67}
68
69pub struct SelectInEnvelopeFuncIntersecting<T>
70where
71    T: RTreeObject,
72{
73    envelope: T::Envelope,
74}
75
76impl<T> SelectInEnvelopeFuncIntersecting<T>
77where
78    T: RTreeObject,
79{
80    pub fn new(envelope: T::Envelope) -> Self {
81        SelectInEnvelopeFuncIntersecting { envelope }
82    }
83}
84
85impl<T> SelectionFunction<T> for SelectInEnvelopeFuncIntersecting<T>
86where
87    T: RTreeObject,
88{
89    fn should_unpack_parent(&self, envelope: &T::Envelope) -> bool {
90        self.envelope.intersects(envelope)
91    }
92
93    fn should_unpack_leaf(&self, leaf: &T) -> bool {
94        leaf.envelope().intersects(&self.envelope)
95    }
96}
97
98pub struct SelectAllFunc;
99
100impl<T> SelectionFunction<T> for SelectAllFunc
101where
102    T: RTreeObject,
103{
104    fn should_unpack_parent(&self, _: &T::Envelope) -> bool {
105        true
106    }
107}
108
109/// A [trait.SelectionFunction] that only selects elements whose envelope
110/// contains a specific point.
111pub struct SelectAtPointFunction<T>
112where
113    T: RTreeObject,
114{
115    point: <T::Envelope as Envelope>::Point,
116}
117
118impl<T> SelectAtPointFunction<T>
119where
120    T: PointDistance,
121{
122    pub fn new(point: <T::Envelope as Envelope>::Point) -> Self {
123        SelectAtPointFunction { point }
124    }
125}
126
127impl<T> SelectionFunction<T> for SelectAtPointFunction<T>
128where
129    T: PointDistance,
130{
131    fn should_unpack_parent(&self, envelope: &T::Envelope) -> bool {
132        envelope.contains_point(&self.point)
133    }
134
135    fn should_unpack_leaf(&self, leaf: &T) -> bool {
136        leaf.contains_point(&self.point)
137    }
138}
139
140/// A selection function that only chooses elements equal (`==`) to a
141/// given element
142pub struct SelectEqualsFunction<'a, T>
143where
144    T: RTreeObject + PartialEq + 'a,
145{
146    /// Only elements equal to this object will be removed.
147    object_to_remove: &'a T,
148}
149
150impl<'a, T> SelectEqualsFunction<'a, T>
151where
152    T: RTreeObject + PartialEq,
153{
154    pub fn new(object_to_remove: &'a T) -> Self {
155        SelectEqualsFunction { object_to_remove }
156    }
157}
158
159impl<'a, T> SelectionFunction<T> for SelectEqualsFunction<'a, T>
160where
161    T: RTreeObject + PartialEq,
162{
163    fn should_unpack_parent(&self, parent_envelope: &T::Envelope) -> bool {
164        parent_envelope.contains_envelope(&self.object_to_remove.envelope())
165    }
166
167    fn should_unpack_leaf(&self, leaf: &T) -> bool {
168        leaf == self.object_to_remove
169    }
170}
171
172pub struct SelectWithinDistanceFunction<T>
173where
174    T: RTreeObject + PointDistance,
175{
176    circle_origin: <T::Envelope as Envelope>::Point,
177    squared_max_distance: <<T::Envelope as Envelope>::Point as Point>::Scalar,
178}
179
180impl<T> SelectWithinDistanceFunction<T>
181where
182    T: RTreeObject + PointDistance,
183{
184    pub fn new(
185        circle_origin: <T::Envelope as Envelope>::Point,
186        squared_max_distance: <<T::Envelope as Envelope>::Point as Point>::Scalar,
187    ) -> Self {
188        SelectWithinDistanceFunction {
189            circle_origin,
190            squared_max_distance,
191        }
192    }
193}
194
195impl<T> SelectionFunction<T> for SelectWithinDistanceFunction<T>
196where
197    T: RTreeObject + PointDistance,
198{
199    fn should_unpack_parent(&self, parent_envelope: &T::Envelope) -> bool {
200        let envelope_distance = parent_envelope.distance_2(&self.circle_origin);
201        envelope_distance <= self.squared_max_distance
202    }
203
204    fn should_unpack_leaf(&self, leaf: &T) -> bool {
205        leaf.distance_2_if_less_or_equal(&self.circle_origin, self.squared_max_distance)
206            .is_some()
207    }
208}
209
210pub struct SelectByAddressFunction<T>
211where
212    T: RTreeObject,
213{
214    envelope: T::Envelope,
215    element_address: *const T,
216}
217
218impl<T> SelectByAddressFunction<T>
219where
220    T: RTreeObject,
221{
222    pub fn new(envelope: T::Envelope, element_address: &T) -> Self {
223        Self {
224            envelope,
225            element_address,
226        }
227    }
228}
229
230impl<T> SelectionFunction<T> for SelectByAddressFunction<T>
231where
232    T: RTreeObject,
233{
234    fn should_unpack_parent(&self, parent_envelope: &T::Envelope) -> bool {
235        parent_envelope.contains_envelope(&self.envelope)
236    }
237
238    fn should_unpack_leaf(&self, leaf: &T) -> bool {
239        core::ptr::eq(self.element_address, leaf)
240    }
241}
rstar/algorithm/selection_functions.rs

rstar/algorithm/
selection_functions.rs
