rstar/
aabb.rs

1use crate::point::{max_inline, Point, PointExt};
2use crate::{Envelope, RTreeObject};
3use num_traits::{Bounded, One, Zero};
4
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Serialize};
7
8/// An n-dimensional axis aligned bounding box (AABB).
9///
10/// An object's AABB is the smallest box totally encompassing an object
11/// while being aligned to the current coordinate system.
12/// Although these structures are commonly called bounding _boxes_, they exist in any
13/// dimension.
14///
15/// Note that AABBs cannot be inserted into r-trees. Use the
16/// [Rectangle](crate::primitives::Rectangle) struct for this purpose.
17///
18/// # Type arguments
19/// `P`: The struct is generic over which point type is used. Using an n-dimensional point
20/// type will result in an n-dimensional bounding box.
21#[derive(Clone, Debug, Copy, PartialEq, Eq, Ord, PartialOrd, Hash)]
22#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
23pub struct AABB<P>
24where
25    P: Point,
26{
27    lower: P,
28    upper: P,
29}
30
31impl<P> AABB<P>
32where
33    P: Point,
34{
35    /// Returns the AABB encompassing a single point.
36    pub fn from_point(p: P) -> Self {
37        AABB {
38            lower: p.clone(),
39            upper: p,
40        }
41    }
42
43    /// Returns the AABB's lower corner.
44    ///
45    /// This is the point contained within the AABB with the smallest coordinate value in each
46    /// dimension.
47    pub fn lower(&self) -> P {
48        self.lower.clone()
49    }
50
51    /// Returns the AABB's upper corner.
52    ///
53    /// This is the point contained within the AABB with the largest coordinate value in each
54    /// dimension.
55    pub fn upper(&self) -> P {
56        self.upper.clone()
57    }
58
59    /// Creates a new AABB encompassing two points.
60    pub fn from_corners(p1: P, p2: P) -> Self {
61        Self {
62            lower: p1.min_point(&p2),
63            upper: p1.max_point(&p2),
64        }
65    }
66
67    /// Returns the AABB from already known lower/upper bounds.
68    pub fn from_bounds(lower: P, upper: P) -> Self {
69        debug_assert_eq!(lower.min_point(&upper), lower);
70        debug_assert_eq!(lower.max_point(&upper), upper);
71        Self { lower, upper }
72    }
73
74    /// Creates a new AABB from a center and a distance.
75    ///
76    /// Creates the smallest AABB which includes all points within `distance` of `center`.
77    pub fn from_center(center: P, distance: P::Scalar) -> Self {
78        let distance = P::from_value(distance);
79
80        let p1 = center.add(&distance);
81        let p2 = center.sub(&distance);
82
83        Self::from_corners(p1, p2)
84    }
85
86    /// Creates a new AABB encompassing a collection of points.
87    pub fn from_points<'a, I>(i: I) -> Self
88    where
89        I: IntoIterator<Item = &'a P> + 'a,
90        P: 'a,
91    {
92        i.into_iter().fold(
93            Self {
94                lower: P::from_value(P::Scalar::max_value()),
95                upper: P::from_value(P::Scalar::min_value()),
96            },
97            |aabb, p| Self {
98                lower: aabb.lower.min_point(p),
99                upper: aabb.upper.max_point(p),
100            },
101        )
102    }
103
104    /// Returns the point within this AABB closest to a given point.
105    ///
106    /// If `point` is contained within the AABB, `point` will be returned.
107    pub fn min_point(&self, point: &P) -> P {
108        self.upper.min_point(&self.lower.max_point(point))
109    }
110
111    /// Returns the squared distance to the AABB's [min_point](AABB::min_point)
112    pub fn distance_2(&self, point: &P) -> P::Scalar {
113        if self.contains_point(point) {
114            Zero::zero()
115        } else {
116            self.min_point(point).sub(point).length_2()
117        }
118    }
119}
120
121impl<P> Envelope for AABB<P>
122where
123    P: Point,
124{
125    type Point = P;
126
127    fn new_empty() -> Self {
128        let max = P::Scalar::max_value();
129        let min = P::Scalar::min_value();
130        Self {
131            lower: P::from_value(max),
132            upper: P::from_value(min),
133        }
134    }
135
136    fn is_empty(&self) -> bool {
137        self.lower.nth(0) > self.upper.nth(0)
138    }
139
140    fn contains_point(&self, point: &P) -> bool {
141        self.lower.all_component_wise(point, |x, y| x <= y)
142            && self.upper.all_component_wise(point, |x, y| x >= y)
143    }
144
145    fn contains_envelope(&self, other: &Self) -> bool {
146        self.lower.all_component_wise(&other.lower, |l, r| l <= r)
147            && self.upper.all_component_wise(&other.upper, |l, r| l >= r)
148    }
149
150    fn merge(&mut self, other: &Self) {
151        self.lower = self.lower.min_point(&other.lower);
152        self.upper = self.upper.max_point(&other.upper);
153    }
154
155    fn merged(&self, other: &Self) -> Self {
156        AABB {
157            lower: self.lower.min_point(&other.lower),
158            upper: self.upper.max_point(&other.upper),
159        }
160    }
161
162    fn intersects(&self, other: &Self) -> bool {
163        self.lower.all_component_wise(&other.upper, |l, r| l <= r)
164            && self.upper.all_component_wise(&other.lower, |l, r| l >= r)
165    }
166
167    fn area(&self) -> P::Scalar {
168        let zero = P::Scalar::zero();
169        let one = P::Scalar::one();
170        let diag = self.upper.sub(&self.lower);
171        diag.fold(one, |acc, cur| max_inline(cur, zero) * acc)
172    }
173
174    fn distance_2(&self, point: &P) -> P::Scalar {
175        self.distance_2(point)
176    }
177
178    fn min_max_dist_2(&self, point: &P) -> <P as Point>::Scalar {
179        let l = self.lower.sub(point);
180        let u = self.upper.sub(point);
181        let mut max_diff = (Zero::zero(), Zero::zero(), 0); // diff, min, index
182        let mut result = P::new();
183
184        for i in 0..P::DIMENSIONS {
185            let mut min = l.nth(i);
186            let mut max = u.nth(i);
187            max = max * max;
188            min = min * min;
189            if max < min {
190                core::mem::swap(&mut min, &mut max);
191            }
192
193            let diff = max - min;
194            *result.nth_mut(i) = max;
195
196            if diff >= max_diff.0 {
197                max_diff = (diff, min, i);
198            }
199        }
200
201        *result.nth_mut(max_diff.2) = max_diff.1;
202        result.fold(Zero::zero(), |acc, curr| acc + curr)
203    }
204
205    fn center(&self) -> Self::Point {
206        let one = <Self::Point as Point>::Scalar::one();
207        let two = one + one;
208        self.lower.component_wise(&self.upper, |x, y| (x + y) / two)
209    }
210
211    fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar {
212        AABB {
213            lower: self.lower.max_point(&other.lower),
214            upper: self.upper.min_point(&other.upper),
215        }
216        .area()
217    }
218
219    fn perimeter_value(&self) -> P::Scalar {
220        let diag = self.upper.sub(&self.lower);
221        let zero = P::Scalar::zero();
222        max_inline(diag.fold(zero, |acc, value| acc + value), zero)
223    }
224
225    fn sort_envelopes<T: RTreeObject<Envelope = Self>>(axis: usize, envelopes: &mut [T]) {
226        envelopes.sort_unstable_by(|l, r| {
227            l.envelope()
228                .lower
229                .nth(axis)
230                .partial_cmp(&r.envelope().lower.nth(axis))
231                .unwrap()
232        });
233    }
234
235    fn partition_envelopes<T: RTreeObject<Envelope = Self>>(
236        axis: usize,
237        envelopes: &mut [T],
238        selection_size: usize,
239    ) {
240        envelopes.select_nth_unstable_by(selection_size, |l, r| {
241            l.envelope()
242                .lower
243                .nth(axis)
244                .partial_cmp(&r.envelope().lower.nth(axis))
245                .unwrap()
246        });
247    }
248}
249
250#[cfg(test)]
251mod test {
252    use super::AABB;
253    use crate::envelope::Envelope;
254    use crate::object::PointDistance;
255
256    #[test]
257    fn empty_rect() {
258        let empty = AABB::<[f32; 2]>::new_empty();
259
260        let other = AABB::from_corners([1.0, 1.0], [1.0, 1.0]);
261        let subject = empty.merged(&other);
262        assert_eq!(other, subject);
263
264        let other = AABB::from_corners([0.0, 0.0], [0.0, 0.0]);
265        let subject = empty.merged(&other);
266        assert_eq!(other, subject);
267
268        let other = AABB::from_corners([0.5, 0.5], [0.5, 0.5]);
269        let subject = empty.merged(&other);
270        assert_eq!(other, subject);
271
272        let other = AABB::from_corners([-0.5, -0.5], [-0.5, -0.5]);
273        let subject = empty.merged(&other);
274        assert_eq!(other, subject);
275    }
276
277    /// Test that min_max_dist_2 is identical to distance_2 for the equivalent
278    /// min max corner of the AABB. This is necessary to prevent optimizations
279    /// from inadvertently changing floating point order of operations.
280    #[test]
281    fn test_min_max_dist_2_issue_40_regression() {
282        let a = [0.7018702292340033, 0.2121617955083932, 0.8120562975177115];
283        let b = [0.7297749764202988, 0.23020869735094462, 0.8194675310336391];
284        let aabb = AABB::from_corners(a, b);
285        let p = [0.6950876013070484, 0.220750082121574, 0.8186032137709887];
286        let corner = [a[0], b[1], a[2]];
287        assert_eq!(aabb.min_max_dist_2(&p), corner.distance_2(&p));
288    }
289
290    #[test]
291    fn test_from_points_issue_170_regression() {
292        let aabb = AABB::from_points(&[(3., 3., 3.), (4., 4., 4.)]);
293        assert_eq!(aabb, AABB::from_corners((3., 3., 3.), (4., 4., 4.)));
294    }
295
296    #[test]
297    fn test_is_empty() {
298        let empty = AABB::<[f32; 2]>::new_empty();
299        assert!(empty.is_empty());
300
301        let not_empty = AABB::from_corners([1.0, 1.0], [1.0, 1.0]);
302        assert!(!not_empty.is_empty());
303    }
304}
rstar/aabb.rs

rstar/
aabb.rs
