1#[derive(Clone, Copy, Debug, PartialEq, Eq)]
2pub struct Aabb {
3 pub min_x: i64,
4 pub min_y: i64,
5 pub max_x: i64,
6 pub max_y: i64,
7}
8
9impl Aabb {
10 pub fn new(min_x: i64, min_y: i64, max_x: i64, max_y: i64) -> Self {
11 assert!(min_x <= max_x, "AABB: min_x ({min_x}) > max_x ({max_x})");
12 assert!(min_y <= max_y, "AABB: min_y ({min_y}) > max_y ({max_y})");
13 Self {
14 min_x,
15 min_y,
16 max_x,
17 max_y,
18 }
19 }
20
21 pub fn from_ring(ring: &[[i64; 2]]) -> Self {
22 if ring.is_empty() {
23 return Self {
24 min_x: 0,
25 max_x: 0,
26 min_y: 0,
27 max_y: 0,
28 };
29 }
30
31 let mut min_x = ring[0][0];
32 let mut max_x = ring[0][0];
33 let mut min_y = ring[0][1];
34 let mut max_y = ring[0][1];
35
36 for pt in &ring[1..] {
37 if pt[0] < min_x {
38 min_x = pt[0];
39 }
40 if pt[0] > max_x {
41 max_x = pt[0];
42 }
43 if pt[1] < min_y {
44 min_y = pt[1];
45 }
46 if pt[1] > max_y {
47 max_y = pt[1];
48 }
49 }
50
51 Self {
52 min_x,
53 min_y,
54 max_x,
55 max_y,
56 }
57 }
58
59 pub fn intersects(&self, other: &Aabb) -> bool {
60 self.min_x < other.max_x
61 && self.max_x > other.min_x
62 && self.min_y < other.max_y
63 && self.max_y > other.min_y
64 }
65
66 pub fn contains_point(&self, x: i64, y: i64) -> bool {
67 x >= self.min_x && x <= self.max_x && y >= self.min_y && y <= self.max_y
68 }
69
70 pub fn merge(&self, other: &Aabb) -> Aabb {
71 Aabb {
72 min_x: self.min_x.min(other.min_x),
73 min_y: self.min_y.min(other.min_y),
74 max_x: self.max_x.max(other.max_x),
75 max_y: self.max_y.max(other.max_y),
76 }
77 }
78
79 pub fn width(&self) -> i64 {
80 self.max_x - self.min_x
81 }
82
83 pub fn height(&self) -> i64 {
84 self.max_y - self.min_y
85 }
86}
87
88#[cfg(test)]
89mod tests {
90 use super::*;
91
92 const M: i64 = 1_000_000;
93
94 #[test]
95 fn from_ring_tracks_extrema() {
96 let ring = vec![[M, M], [2 * M, M], [2 * M, 2 * M], [M, 2 * M]];
97 let aabb = Aabb::from_ring(&ring);
98 assert_eq!(aabb.min_x, M);
99 assert_eq!(aabb.max_x, 2 * M);
100 assert_eq!(aabb.min_y, M);
101 assert_eq!(aabb.max_y, 2 * M);
102 }
103
104 #[test]
105 fn from_ring_handles_single_vertex() {
106 let ring = vec![[5, 3]];
107 let aabb = Aabb::from_ring(&ring);
108
109 assert_eq!(aabb.min_x, 5);
110 assert_eq!(aabb.max_x, 5);
111 assert_eq!(aabb.min_y, 3);
112 assert_eq!(aabb.max_y, 3);
113 }
114
115 #[test]
116 fn from_ring_handles_negative_coordinates() {
117 let ring = vec![[-10, -5], [10, 5]];
118 let aabb = Aabb::from_ring(&ring);
119
120 assert_eq!(aabb.min_x, -10);
121 assert_eq!(aabb.max_x, 10);
122 assert_eq!(aabb.min_y, -5);
123 assert_eq!(aabb.max_y, 5);
124 }
125
126 #[test]
127 fn intersects_overlapping_returns_true() {
128 let a = Aabb::new(0, 0, 2 * M, 2 * M);
129 let b = Aabb::new(M, M, 3 * M, 3 * M);
130 assert!(a.intersects(&b));
131 assert!(b.intersects(&a));
132 }
133
134 #[test]
135 fn intersects_touching_edge_returns_false() {
136 let a = Aabb::new(0, 0, M, M);
137 let b = Aabb::new(M, 0, 2 * M, M);
138 assert!(!a.intersects(&b), "touching edges should NOT intersect");
139 assert!(
140 !b.intersects(&a),
141 "touching edges should NOT intersect (reversed)"
142 );
143 }
144
145 #[test]
146 fn intersects_touching_corner_returns_false() {
147 let a = Aabb::new(0, 0, M, M);
148 let b = Aabb::new(M, M, 2 * M, 2 * M);
149 assert!(!a.intersects(&b), "touching corners should NOT intersect");
150 }
151
152 #[test]
153 fn intersects_separated_returns_false() {
154 let a = Aabb::new(0, 0, M, M);
155 let b = Aabb::new(2 * M, 0, 3 * M, M);
156 assert!(!a.intersects(&b));
157 }
158
159 #[test]
160 fn intersects_contained_returns_true() {
161 let outer = Aabb::new(0, 0, 10 * M, 10 * M);
162 let inner = Aabb::new(2 * M, 2 * M, 5 * M, 5 * M);
163 assert!(outer.intersects(&inner));
164 assert!(inner.intersects(&outer));
165 }
166
167 #[test]
168 fn contains_point_works() {
169 let aabb = Aabb::new(0, 0, M, M);
170 assert!(aabb.contains_point(M / 2, M / 2));
171 assert!(aabb.contains_point(0, 0));
172 assert!(aabb.contains_point(M, M));
173 assert!(!aabb.contains_point(M + 1, 0));
174 }
175
176 #[test]
177 fn merge_covers_both() {
178 let a = Aabb::new(0, 0, M, M);
179 let b = Aabb::new(2 * M, 2 * M, 3 * M, 3 * M);
180 let merged = a.merge(&b);
181 assert_eq!(merged.min_x, 0);
182 assert_eq!(merged.max_x, 3 * M);
183 assert_eq!(merged.min_y, 0);
184 assert_eq!(merged.max_y, 3 * M);
185 }
186
187 #[test]
188 fn merge_disjoint_boxes_contains_both() {
189 let a = Aabb::new(-3 * M, -2 * M, -M, -M);
190 let b = Aabb::new(2 * M, M, 4 * M, 3 * M);
191 let merged = a.merge(&b);
192
193 assert_eq!(merged.min_x, -3 * M);
194 assert_eq!(merged.min_y, -2 * M);
195 assert_eq!(merged.max_x, 4 * M);
196 assert_eq!(merged.max_y, 3 * M);
197 assert!(merged.contains_point(a.min_x, a.min_y));
198 assert!(merged.contains_point(b.max_x, b.max_y));
199 }
200
201 #[test]
202 fn merge_nested_boxes_equals_outer_box() {
203 let outer = Aabb::new(0, 0, 10 * M, 10 * M);
204 let inner = Aabb::new(2 * M, 3 * M, 4 * M, 5 * M);
205
206 assert_eq!(outer.merge(&inner), outer);
207 assert_eq!(inner.merge(&outer), outer);
208 }
209
210 #[test]
211 fn contains_point_includes_corner_and_excludes_outside() {
212 let aabb = Aabb::new(-M, -2 * M, M, 2 * M);
213
214 assert!(aabb.contains_point(-M, -2 * M));
215 assert!(!aabb.contains_point(M + 1, 2 * M));
216 }
217
218 #[test]
219 fn intersects_is_symmetric() {
220 let a = Aabb::new(0, 0, 3 * M, 3 * M);
221 let b = Aabb::new(2 * M, 2 * M, 5 * M, 5 * M);
222 assert_eq!(a.intersects(&b), b.intersects(&a));
223 }
224}