rstar/
object.rs

1use alloc::rc::Rc;
2use alloc::sync::Arc;
3
4use crate::aabb::AABB;
5use crate::envelope::Envelope;
6use crate::point::{Point, PointExt};
7
8/// Type alias for distance scalar types derived from `PointDistance` objects
9#[allow(type_alias_bounds)]
10pub(crate) type Distance<T: PointDistance> = <<T::Envelope as Envelope>::Point as Point>::Scalar;
11
12/// An object that can be inserted into an r-tree.
13///
14/// This trait must be implemented for any object to be inserted into an r-tree.
15/// Some simple objects that already implement this trait can be found in the
16/// [crate::primitives] module.
17///
18/// The only property required of such an object is its [crate::Envelope].
19/// Most simply, this method should return the [axis aligned bounding box](AABB)
20/// of the object. Other envelope types may be supported in the future.
21///
22/// *Note*: It is a logic error if an object's envelope changes after insertion into
23/// an r-tree.
24///
25/// # Type parameters
26/// `Envelope`: The object's envelope type. At the moment, only [AABB] is
27/// available.
28///
29/// # Example implementation
30/// ```
31/// use rstar::{RTreeObject, AABB};
32///
33/// struct Player
34/// {
35///     name: String,
36///     x_coordinate: f64,
37///     y_coordinate: f64
38/// }
39///
40/// impl RTreeObject for Player
41/// {
42///     type Envelope = AABB<[f64; 2]>;
43///
44///     fn envelope(&self) -> Self::Envelope
45///     {
46///         AABB::from_point([self.x_coordinate, self.y_coordinate])
47///     }
48/// }
49///
50/// use rstar::RTree;
51///
52/// let mut tree = RTree::new();
53///
54/// // Insert a few players...
55/// tree.insert(Player {
56///     name: "Forlorn Freeman".into(),
57///     x_coordinate: 1.,
58///     y_coordinate: 0.
59/// });
60/// tree.insert(Player {
61///     name: "Sarah Croft".into(),
62///     x_coordinate: 0.5,
63///     y_coordinate: 0.5,
64/// });
65/// tree.insert(Player {
66///     name: "Geralt of Trivia".into(),
67///     x_coordinate: 0.,
68///     y_coordinate: 2.,
69/// });
70///
71/// // Now we are ready to ask some questions!
72/// let envelope = AABB::from_point([0.5, 0.5]);
73/// let likely_sarah_croft = tree.locate_in_envelope(envelope).next();
74/// println!("Found {:?} lurking around at (0.5, 0.5)!", likely_sarah_croft.unwrap().name);
75/// # assert!(likely_sarah_croft.is_some());
76///
77/// let unit_square = AABB::from_corners([-1.0, -1.0], [1., 1.]);
78/// for player in tree.locate_in_envelope(unit_square) {
79///    println!("And here is {:?} spelunking in the unit square.", player.name);
80/// }
81/// # assert_eq!(tree.locate_in_envelope(unit_square).count(), 2);
82/// ```
83pub trait RTreeObject {
84    /// The object's envelope type. Usually, [AABB] will be the right choice.
85    /// This type also defines the object's dimensionality.
86    type Envelope: Envelope;
87
88    /// Returns the object's envelope.
89    ///
90    /// Usually, this will return the object's [axis aligned bounding box](AABB).
91    fn envelope(&self) -> Self::Envelope;
92}
93
94/// Defines objects which can calculate their minimal distance to a point.
95///
96/// This trait is most notably necessary for support of [nearest_neighbor](struct.RTree#method.nearest_neighbor)
97/// queries.
98///
99/// # Example
100/// ```
101/// use rstar::{RTreeObject, PointDistance, AABB};
102///
103/// struct Circle
104/// {
105///     origin: [f32; 2],
106///     radius: f32,
107/// }
108///
109/// impl RTreeObject for Circle {
110///     type Envelope = AABB<[f32; 2]>;
111///
112///     fn envelope(&self) -> Self::Envelope {
113///         let corner_1 = [self.origin[0] - self.radius, self.origin[1] - self.radius];
114///         let corner_2 = [self.origin[0] + self.radius, self.origin[1] + self.radius];
115///         AABB::from_corners(corner_1, corner_2)
116///     }
117/// }
118///
119/// impl PointDistance for Circle
120/// {
121///     fn distance_2(&self, point: &[f32; 2]) -> f32
122///     {
123///         let d_x = self.origin[0] - point[0];
124///         let d_y = self.origin[1] - point[1];
125///         let distance_to_origin = (d_x * d_x + d_y * d_y).sqrt();
126///         let distance_to_ring = distance_to_origin - self.radius;
127///         let distance_to_circle = f32::max(0.0, distance_to_ring);
128///         // We must return the squared distance!
129///         distance_to_circle * distance_to_circle
130///     }
131///
132///     // This implementation is not required but more efficient since it
133///     // omits the calculation of a square root
134///     fn contains_point(&self, point: &[f32; 2]) -> bool
135///     {
136///         let d_x = self.origin[0] - point[0];
137///         let d_y = self.origin[1] - point[1];
138///         let distance_to_origin_2 = (d_x * d_x + d_y * d_y);
139///         let radius_2 = self.radius * self.radius;
140///         distance_to_origin_2 <= radius_2
141///     }
142/// }
143///
144///
145/// let circle = Circle {
146///     origin: [1.0, 0.0],
147///     radius: 1.0,
148/// };
149///
150/// assert_eq!(circle.distance_2(&[-1.0, 0.0]), 1.0);
151/// assert_eq!(circle.distance_2(&[-2.0, 0.0]), 4.0);
152/// assert!(circle.contains_point(&[1.0, 0.0]));
153/// ```
154pub trait PointDistance: RTreeObject {
155    /// Returns the squared distance between an object and a point.
156    ///
157    /// # Notes
158    /// - While euclidean distance will be the correct choice for most use cases, any distance metric
159    ///   fulfilling the [usual axioms](https://en.wikipedia.org/wiki/Metric_space)
160    ///   can be used when implementing this method
161    /// - Implementers **must** ensure that the distance metric used matches that of [crate::Envelope::distance_2]
162    fn distance_2(&self, point: &<Self::Envelope as Envelope>::Point) -> Distance<Self>;
163
164    /// Returns `true` if a point is contained within this object.
165    ///
166    /// By default, any point returning a `distance_2` less than or equal to zero is considered to be
167    /// contained within `self`. Changing this default behavior is advised if calculating the squared distance
168    /// is more computationally expensive than a point containment check.
169    fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
170        self.distance_2(point) <= num_traits::zero()
171    }
172
173    /// Returns the squared distance to this object, or `None` if the distance
174    /// is larger than a given maximum value.
175    ///
176    /// Some algorithms only need to know an object's distance
177    /// if it is less than or equal to a maximum value. In these cases, it may be
178    /// faster to calculate a lower bound of the distance first and returning
179    /// early if the object cannot be closer than the given maximum.
180    ///
181    /// The provided default implementation will use the distance to the object's
182    /// envelope as a lower bound.
183    ///
184    /// If performance is critical and the object's distance calculation is fast,
185    /// it may be beneficial to overwrite this implementation.
186    fn distance_2_if_less_or_equal(
187        &self,
188        point: &<Self::Envelope as Envelope>::Point,
189        max_distance_2: Distance<Self>,
190    ) -> Option<Distance<Self>> {
191        let envelope_distance = self.envelope().distance_2(point);
192        if envelope_distance <= max_distance_2 {
193            let distance_2 = self.distance_2(point);
194            if distance_2 <= max_distance_2 {
195                return Some(distance_2);
196            }
197        }
198        None
199    }
200}
201
202impl<P> RTreeObject for P
203where
204    P: Point,
205{
206    type Envelope = AABB<P>;
207
208    fn envelope(&self) -> AABB<P> {
209        AABB::from_point(self.clone())
210    }
211}
212
213impl<P> PointDistance for P
214where
215    P: Point,
216{
217    fn distance_2(&self, point: &P) -> P::Scalar {
218        <Self as PointExt>::distance_2(self, point)
219    }
220
221    fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
222        self == point
223    }
224
225    fn distance_2_if_less_or_equal(
226        &self,
227        point: &<Self::Envelope as Envelope>::Point,
228        max_distance_2: Distance<Self>,
229    ) -> Option<P::Scalar> {
230        let distance_2 = <Self as PointExt>::distance_2(self, point);
231        if distance_2 <= max_distance_2 {
232            Some(distance_2)
233        } else {
234            None
235        }
236    }
237}
238
239impl<T> RTreeObject for Arc<T>
240where
241    T: RTreeObject + ?Sized,
242{
243    type Envelope = T::Envelope;
244    fn envelope(&self) -> Self::Envelope {
245        (**self).envelope()
246    }
247}
248
249impl<T> PointDistance for Arc<T>
250where
251    T: PointDistance + ?Sized,
252{
253    fn distance_2(&self, point: &<Self::Envelope as Envelope>::Point) -> Distance<Self> {
254        (**self).distance_2(point)
255    }
256    fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
257        (**self).contains_point(point)
258    }
259    fn distance_2_if_less_or_equal(
260        &self,
261        point: &<Self::Envelope as Envelope>::Point,
262        max_distance_2: Distance<Self>,
263    ) -> Option<Distance<Self>> {
264        (**self).distance_2_if_less_or_equal(point, max_distance_2)
265    }
266}
267
268impl<T> RTreeObject for Rc<T>
269where
270    T: RTreeObject + ?Sized,
271{
272    type Envelope = T::Envelope;
273    fn envelope(&self) -> Self::Envelope {
274        (**self).envelope()
275    }
276}
277
278impl<T> PointDistance for Rc<T>
279where
280    T: PointDistance + ?Sized,
281{
282    fn distance_2(&self, point: &<Self::Envelope as Envelope>::Point) -> Distance<Self> {
283        (**self).distance_2(point)
284    }
285    fn contains_point(&self, point: &<Self::Envelope as Envelope>::Point) -> bool {
286        (**self).contains_point(point)
287    }
288    fn distance_2_if_less_or_equal(
289        &self,
290        point: &<Self::Envelope as Envelope>::Point,
291        max_distance_2: Distance<Self>,
292    ) -> Option<Distance<Self>> {
293        (**self).distance_2_if_less_or_equal(point, max_distance_2)
294    }
295}
rstar/object.rs

rstar/
object.rs
