rstar/
object.rs

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

rstar/
object.rs
