space_partitioning/quadtree/
aabb.rs

1use crate::intersections::IntersectsWith;
2use crate::quadtree::Point;
3use std::ops::{Add, RangeInclusive};
4
5/// An axis-aligned bounding box defined by its edge coordinates.
6#[derive(Debug, PartialEq, Eq, Default, Copy, Clone)]
7pub struct AABB {
8    /// Top left coordinate of the rectangle of the element.
9    pub tl: Point,
10    /// Bottom right coordinate of the rectangle of the element.
11    pub br: Point,
12}
13
14impl AABB {
15    /// Constructs a new [`AABB`] from the coordinates of its edges.
16    ///
17    /// # Arguments
18    /// * [`x1`] - The left-most X coordinate.
19    /// * [`y1`] - The top-most Y coordinate.
20    /// * [`x2`] - The right-most X coordinate.
21    /// * [`y2`] - The bottom-most Y coordinate.
22    #[inline]
23    pub fn new(x1: i32, y1: i32, x2: i32, y2: i32) -> Self {
24        Self {
25            tl: Point::new(x1, y1),
26            br: Point::new(x2, y2),
27        }
28    }
29
30    #[inline]
31    pub fn from_ranges(x: RangeInclusive<i32>, y: RangeInclusive<i32>) -> Self {
32        Self {
33            tl: Point::new(*x.start(), *y.start()),
34            br: Point::new(*x.end(), *y.end()),
35        }
36    }
37}
38
39impl IntersectsWith<AABB> for AABB {
40    /// Tests whether this [`AABB`] intersects with another one.
41    ///
42    /// # Remarks
43    /// It is assumed that none of the AABBs is degenerate,
44    /// i.e., neither a line nor a point.
45    ///
46    /// # Arguments
47    /// * [`other`] - The AABB to test for intersection.
48    #[inline]
49    fn intersects_with(&self, other: &AABB) -> bool {
50        // TODO: We might want to have tree specifically for storing point data rather than rects
51        //       as this would simplify the tests below.
52
53        let x1_max = self.tl.x.max(other.tl.x);
54        let x2_min = self.br.x.min(other.br.x);
55        let y1_max = self.tl.y.max(other.tl.y);
56        let y2_min = self.br.y.min(other.br.y);
57
58        // In the non-degenerate case (rect/rect), this covers the intersection.
59        let a = x1_max < x2_min;
60        let b = y1_max < y2_min;
61        let intersects = a & b;
62
63        // If intersects is true, we could skip the entire following
64        // block. With instruction pipelining, this could incur penalties from
65        // branch mis-predictions however, so it might be better to just calculate
66        // the test for degenerate cases anyway.
67        // In the degenerate case we need a more relaxed test.
68        let d_a = x1_max <= x2_min;
69        let d_b = y1_max <= y2_min;
70
71        // Only use the above values in degenerate cases.
72        let degenerate_x = (other.tl.x == other.br.x) | (self.tl.x == self.br.x);
73        let degenerate_y = (other.tl.y == other.br.y) | (self.tl.y == self.br.y);
74        let is_degenerate = degenerate_x | degenerate_y;
75        let d_intersects = is_degenerate & d_a & d_b;
76
77        intersects | d_intersects
78    }
79}
80
81impl Add for AABB {
82    type Output = Self;
83
84    fn add(self, rhs: Self) -> Self::Output {
85        let min_x = self.tl.x.min(rhs.tl.x);
86        let min_y = self.tl.y.min(rhs.tl.y);
87        let max_x = self.br.x.max(rhs.br.x);
88        let max_y = self.br.y.max(rhs.br.y);
89        AABB::new(min_x, min_y, max_x, max_y)
90    }
91}
92
93impl From<[i32; 4]> for AABB {
94    #[inline]
95    fn from(rect: [i32; 4]) -> Self {
96        Self::from(&rect)
97    }
98}
99
100impl From<&[i32; 4]> for AABB {
101    #[inline]
102    fn from(rect: &[i32; 4]) -> Self {
103        Self::new(rect[0], rect[1], rect[2], rect[3])
104    }
105}
106
107impl Into<[i32; 4]> for AABB {
108    fn into(self) -> [i32; 4] {
109        [self.tl.x, self.tl.y, self.br.x, self.br.y]
110    }
111}
112
113impl AsRef<[i32; 4]> for AABB {
114    fn as_ref(&self) -> &[i32; 4] {
115        let ptr = self as *const _ as *const [i32; 4];
116        unsafe { ptr.as_ref() }.unwrap()
117    }
118}
119
120#[cfg(test)]
121mod test {
122    use super::*;
123
124    #[test]
125    fn aabb_is_16_bytes() {
126        assert_eq!(std::mem::size_of::<AABB>(), 16);
127    }
128
129    #[test]
130    fn from_works() {
131        let aabb = AABB::from([1, 2, 3, 4]);
132        assert_eq!(aabb.tl.x, 1);
133        assert_eq!(aabb.tl.y, 2);
134        assert_eq!(aabb.br.x, 3);
135        assert_eq!(aabb.br.y, 4);
136    }
137
138    #[test]
139    fn from_ref_works() {
140        let aabb = AABB::from(&[1, 2, 3, 4]);
141        assert_eq!(aabb.tl.x, 1);
142        assert_eq!(aabb.tl.y, 2);
143        assert_eq!(aabb.br.x, 3);
144        assert_eq!(aabb.br.y, 4);
145    }
146
147    #[test]
148    fn as_ref_works() {
149        let aabb = AABB::new(1, 2, 3, 4);
150        let array: &[i32; 4] = aabb.as_ref();
151        for i in 1..=4 {
152            assert_eq!(array[i as usize - 1], i);
153        }
154    }
155
156    #[test]
157    fn intersects_with_self_works() {
158        let a = AABB::new(0, 0, 1, 1);
159        assert!(a.intersects_with(&a));
160    }
161
162    #[test]
163    fn intersects_when_partial_overlap_works() {
164        let a = AABB::new(0, 0, 2, 2);
165        let b = AABB::new(1, 1, 3, 3);
166        assert!(a.intersects_with(&b));
167        assert!(b.intersects_with(&a));
168
169        let a = AABB::new(0, 0, 2, 2);
170        let b = AABB::new(-1, -1, 1, 1);
171        assert!(a.intersects_with(&b));
172        assert!(b.intersects_with(&a));
173
174        let a = AABB::new(0, 0, 2, 2);
175        let b = AABB::new(-1, 1, 1, 2);
176        assert!(a.intersects_with(&b));
177        assert!(b.intersects_with(&a));
178    }
179
180    #[test]
181    fn intersects_when_not_overlapping_works() {
182        let a = AABB::new(0, 0, 2, 2);
183        let b = AABB::new(2, 0, 3, 3);
184        assert!(!a.intersects_with(&b));
185        assert!(!b.intersects_with(&a));
186
187        let c = AABB::new(0, 0, 2, 2);
188        let d = AABB::new(10, 10, 12, 12);
189        assert!(!c.intersects_with(&d));
190        assert!(!d.intersects_with(&c));
191    }
192
193    #[test]
194    fn intersects_when_degenerate_works() {
195        // With a line
196        let a = AABB::new(-1, 0, 0, -1);
197        let b = AABB::new(1, 1, 0, 1);
198        assert!(!a.intersects_with(&b));
199        assert!(!a.intersects_with(&a));
200        assert!(!b.intersects_with(&b));
201    }
202
203    #[test]
204    fn intersects_rect_point_works() {
205        let point = AABB::new(3, 3, 3, 3);
206
207        // Point lies inside the rectangle.
208        let covering_rect = AABB::new(-10, -10, 10, 10);
209        assert!(covering_rect.intersects_with(&point));
210
211        // Point lies outside the rectangle.
212        let other_rect = AABB::new(-10, -10, 0, 0);
213        assert!(!other_rect.intersects_with(&point));
214    }
215
216    #[test]
217    fn intersects_line_point_works() {
218        let line = AABB::new(-10, 0, 10, 0);
219        let point = AABB::new(1, 0, 1, 0);
220        assert!(line.intersects_with(&point));
221
222        let boundary_point = AABB::new(10, 0, 10, 0);
223        assert!(line.intersects_with(&boundary_point));
224    }
225
226    #[test]
227    fn intersects_point_point_works() {
228        let point = AABB::new(-1, -1, -1, -1);
229        assert!(point.intersects_with(&point));
230    }
231}
space_partitioning/quadtree/aabb.rs

space_partitioning/quadtree/
aabb.rs
