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        AABB {
62            lower: p1.min_point(&p2),
63            upper: p1.max_point(&p2),
64        }
65    }
66
67    /// Creates a new AABB encompassing a collection of points.
68    pub fn from_points<'a, I>(i: I) -> Self
69    where
70        I: IntoIterator<Item = &'a P> + 'a,
71        P: 'a,
72    {
73        i.into_iter().fold(
74            Self {
75                lower: P::from_value(P::Scalar::max_value()),
76                upper: P::from_value(P::Scalar::min_value()),
77            },
78            |aabb, p| Self {
79                lower: aabb.lower.min_point(p),
80                upper: aabb.upper.max_point(p),
81            },
82        )
83    }
84
85    /// Returns the point within this AABB closest to a given point.
86    ///
87    /// If `point` is contained within the AABB, `point` will be returned.
88    pub fn min_point(&self, point: &P) -> P {
89        self.upper.min_point(&self.lower.max_point(point))
90    }
91
92    /// Returns the squared distance to the AABB's [min_point](AABB::min_point)
93    pub fn distance_2(&self, point: &P) -> P::Scalar {
94        if self.contains_point(point) {
95            Zero::zero()
96        } else {
97            self.min_point(point).sub(point).length_2()
98        }
99    }
100}
101
102impl<P> Envelope for AABB<P>
103where
104    P: Point,
105{
106    type Point = P;
107
108    fn new_empty() -> Self {
109        let max = P::Scalar::max_value();
110        let min = P::Scalar::min_value();
111        Self {
112            lower: P::from_value(max),
113            upper: P::from_value(min),
114        }
115    }
116
117    fn contains_point(&self, point: &P) -> bool {
118        self.lower.all_component_wise(point, |x, y| x <= y)
119            && self.upper.all_component_wise(point, |x, y| x >= y)
120    }
121
122    fn contains_envelope(&self, other: &Self) -> bool {
123        self.lower.all_component_wise(&other.lower, |l, r| l <= r)
124            && self.upper.all_component_wise(&other.upper, |l, r| l >= r)
125    }
126
127    fn merge(&mut self, other: &Self) {
128        self.lower = self.lower.min_point(&other.lower);
129        self.upper = self.upper.max_point(&other.upper);
130    }
131
132    fn merged(&self, other: &Self) -> Self {
133        AABB {
134            lower: self.lower.min_point(&other.lower),
135            upper: self.upper.max_point(&other.upper),
136        }
137    }
138
139    fn intersects(&self, other: &Self) -> bool {
140        self.lower.all_component_wise(&other.upper, |l, r| l <= r)
141            && self.upper.all_component_wise(&other.lower, |l, r| l >= r)
142    }
143
144    fn area(&self) -> P::Scalar {
145        let zero = P::Scalar::zero();
146        let one = P::Scalar::one();
147        let diag = self.upper.sub(&self.lower);
148        diag.fold(one, |acc, cur| max_inline(cur, zero) * acc)
149    }
150
151    fn distance_2(&self, point: &P) -> P::Scalar {
152        self.distance_2(point)
153    }
154
155    fn min_max_dist_2(&self, point: &P) -> <P as Point>::Scalar {
156        let l = self.lower.sub(point);
157        let u = self.upper.sub(point);
158        let mut max_diff = (Zero::zero(), Zero::zero(), 0); // diff, min, index
159        let mut result = P::new();
160
161        for i in 0..P::DIMENSIONS {
162            let mut min = l.nth(i);
163            let mut max = u.nth(i);
164            max = max * max;
165            min = min * min;
166            if max < min {
167                core::mem::swap(&mut min, &mut max);
168            }
169
170            let diff = max - min;
171            *result.nth_mut(i) = max;
172
173            if diff >= max_diff.0 {
174                max_diff = (diff, min, i);
175            }
176        }
177
178        *result.nth_mut(max_diff.2) = max_diff.1;
179        result.fold(Zero::zero(), |acc, curr| acc + curr)
180    }
181
182    fn center(&self) -> Self::Point {
183        let one = <Self::Point as Point>::Scalar::one();
184        let two = one + one;
185        self.lower.component_wise(&self.upper, |x, y| (x + y) / two)
186    }
187
188    fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar {
189        AABB {
190            lower: self.lower.max_point(&other.lower),
191            upper: self.upper.min_point(&other.upper),
192        }
193        .area()
194    }
195
196    fn perimeter_value(&self) -> P::Scalar {
197        let diag = self.upper.sub(&self.lower);
198        let zero = P::Scalar::zero();
199        max_inline(diag.fold(zero, |acc, value| acc + value), zero)
200    }
201
202    fn sort_envelopes<T: RTreeObject<Envelope = Self>>(axis: usize, envelopes: &mut [T]) {
203        envelopes.sort_unstable_by(|l, r| {
204            l.envelope()
205                .lower
206                .nth(axis)
207                .partial_cmp(&r.envelope().lower.nth(axis))
208                .unwrap()
209        });
210    }
211
212    fn partition_envelopes<T: RTreeObject<Envelope = Self>>(
213        axis: usize,
214        envelopes: &mut [T],
215        selection_size: usize,
216    ) {
217        envelopes.select_nth_unstable_by(selection_size, |l, r| {
218            l.envelope()
219                .lower
220                .nth(axis)
221                .partial_cmp(&r.envelope().lower.nth(axis))
222                .unwrap()
223        });
224    }
225}
226
227#[cfg(test)]
228mod test {
229    use super::AABB;
230    use crate::envelope::Envelope;
231    use crate::object::PointDistance;
232
233    #[test]
234    fn empty_rect() {
235        let empty = AABB::<[f32; 2]>::new_empty();
236
237        let other = AABB::from_corners([1.0, 1.0], [1.0, 1.0]);
238        let subject = empty.merged(&other);
239        assert_eq!(other, subject);
240
241        let other = AABB::from_corners([0.0, 0.0], [0.0, 0.0]);
242        let subject = empty.merged(&other);
243        assert_eq!(other, subject);
244
245        let other = AABB::from_corners([0.5, 0.5], [0.5, 0.5]);
246        let subject = empty.merged(&other);
247        assert_eq!(other, subject);
248
249        let other = AABB::from_corners([-0.5, -0.5], [-0.5, -0.5]);
250        let subject = empty.merged(&other);
251        assert_eq!(other, subject);
252    }
253
254    /// Test that min_max_dist_2 is identical to distance_2 for the equivalent
255    /// min max corner of the AABB. This is necessary to prevent optimizations
256    /// from inadvertently changing floating point order of operations.
257    #[test]
258    fn test_min_max_dist_2_issue_40_regression() {
259        let a = [0.7018702292340033, 0.2121617955083932, 0.8120562975177115];
260        let b = [0.7297749764202988, 0.23020869735094462, 0.8194675310336391];
261        let aabb = AABB::from_corners(a, b);
262        let p = [0.6950876013070484, 0.220750082121574, 0.8186032137709887];
263        let corner = [a[0], b[1], a[2]];
264        assert_eq!(aabb.min_max_dist_2(&p), corner.distance_2(&p));
265    }
266
267    #[test]
268    fn test_from_points_issue_170_regression() {
269        let aabb = AABB::from_points(&[(3., 3., 3.), (4., 4., 4.)]);
270        assert_eq!(aabb, AABB::from_corners((3., 3., 3.), (4., 4., 4.)));
271    }
272}
rstar/aabb.rs

rstar/
aabb.rs
