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)]
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.clone(),
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()
74            .fold(Self::new_empty(), |aabb, p| aabb.add_point(p))
75    }
76
77    /// Returns the AABB that contains `self` and another point.
78    fn add_point(&self, point: &P) -> Self {
79        AABB {
80            lower: self.lower.min_point(point),
81            upper: self.upper.max_point(point),
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        new_empty()
110    }
111
112    fn contains_point(&self, point: &P) -> bool {
113        self.lower.all_component_wise(point, |x, y| x <= y)
114            && self.upper.all_component_wise(point, |x, y| x >= y)
115    }
116
117    fn contains_envelope(&self, other: &Self) -> bool {
118        self.lower.all_component_wise(&other.lower, |l, r| l <= r)
119            && self.upper.all_component_wise(&other.upper, |l, r| l >= r)
120    }
121
122    fn merge(&mut self, other: &Self) {
123        self.lower = self.lower.min_point(&other.lower);
124        self.upper = self.upper.max_point(&other.upper);
125    }
126
127    fn merged(&self, other: &Self) -> Self {
128        AABB {
129            lower: self.lower.min_point(&other.lower),
130            upper: self.upper.max_point(&other.upper),
131        }
132    }
133
134    fn intersects(&self, other: &Self) -> bool {
135        self.lower.all_component_wise(&other.upper, |l, r| l <= r)
136            && self.upper.all_component_wise(&other.lower, |l, r| l >= r)
137    }
138
139    fn area(&self) -> P::Scalar {
140        let zero = P::Scalar::zero();
141        let one = P::Scalar::one();
142        let diag = self.upper.sub(&self.lower);
143        diag.fold(one, |acc, cur| max_inline(cur, zero) * acc)
144    }
145
146    fn distance_2(&self, point: &P) -> P::Scalar {
147        self.distance_2(point)
148    }
149
150    fn min_max_dist_2(&self, point: &P) -> <P as Point>::Scalar {
151        let l = self.lower.sub(point);
152        let u = self.upper.sub(point);
153        let mut max_diff = (Zero::zero(), Zero::zero(), 0); // diff, min, index
154        let mut result = P::new();
155
156        for i in 0..P::DIMENSIONS {
157            let mut min = l.nth(i);
158            let mut max = u.nth(i);
159            max = max * max;
160            min = min * min;
161            if max < min {
162                core::mem::swap(&mut min, &mut max);
163            }
164
165            let diff = max - min;
166            *result.nth_mut(i) = max;
167
168            if diff >= max_diff.0 {
169                max_diff = (diff, min, i);
170            }
171        }
172
173        *result.nth_mut(max_diff.2) = max_diff.1;
174        result.fold(Zero::zero(), |acc, curr| acc + curr)
175    }
176
177    fn center(&self) -> Self::Point {
178        let one = <Self::Point as Point>::Scalar::one();
179        let two = one + one;
180        self.lower.component_wise(&self.upper, |x, y| (x + y) / two)
181    }
182
183    fn intersection_area(&self, other: &Self) -> <Self::Point as Point>::Scalar {
184        AABB {
185            lower: self.lower.max_point(&other.lower),
186            upper: self.upper.min_point(&other.upper),
187        }
188        .area()
189    }
190
191    fn perimeter_value(&self) -> P::Scalar {
192        let diag = self.upper.sub(&self.lower);
193        let zero = P::Scalar::zero();
194        max_inline(diag.fold(zero, |acc, value| acc + value), zero)
195    }
196
197    fn sort_envelopes<T: RTreeObject<Envelope = Self>>(axis: usize, envelopes: &mut [T]) {
198        envelopes.sort_by(|l, r| {
199            l.envelope()
200                .lower
201                .nth(axis)
202                .partial_cmp(&r.envelope().lower.nth(axis))
203                .unwrap()
204        });
205    }
206
207    fn partition_envelopes<T: RTreeObject<Envelope = Self>>(
208        axis: usize,
209        envelopes: &mut [T],
210        selection_size: usize,
211    ) {
212        envelopes.select_nth_unstable_by(selection_size, |l, r| {
213            l.envelope()
214                .lower
215                .nth(axis)
216                .partial_cmp(&r.envelope().lower.nth(axis))
217                .unwrap()
218        });
219    }
220}
221
222fn new_empty<P: Point>() -> AABB<P> {
223    let max = P::Scalar::max_value();
224    let min = P::Scalar::min_value();
225    AABB {
226        lower: P::from_value(max),
227        upper: P::from_value(min),
228    }
229}
230
231#[cfg(test)]
232mod test {
233    use super::AABB;
234    use crate::envelope::Envelope;
235    use crate::object::PointDistance;
236
237    /// Test that min_max_dist_2 is identical to distance_2 for the equivalent
238    /// min max corner of the AABB. This is necessary to prevent optimizations
239    /// from inadvertently changing floating point order of operations.
240    #[test]
241    fn test_min_max_dist_2_issue_40_regression() {
242        let a = [0.7018702292340033, 0.2121617955083932, 0.8120562975177115];
243        let b = [0.7297749764202988, 0.23020869735094462, 0.8194675310336391];
244        let aabb = AABB::from_corners(a, b);
245        let p = [0.6950876013070484, 0.220750082121574, 0.8186032137709887];
246        let corner = [a[0], b[1], a[2]];
247        assert_eq!(aabb.min_max_dist_2(&p), corner.distance_2(&p));
248    }
249}
rstar/aabb.rs

rstar/
aabb.rs
