1use crate::aabb::Aabb;
2
3fn validate_polygon(ring: &[[i64; 2]]) -> bool {
4 ring.len() >= 3
5}
6
7fn project_onto_axis(ring: &[[i64; 2]], ax: i64, ay: i64) -> (i128, i128) {
8 ring.iter()
9 .map(|pt| pt[0] as i128 * ax as i128 + pt[1] as i128 * ay as i128)
10 .fold((i128::MAX, i128::MIN), |(min, max), v| {
11 (min.min(v), max.max(v))
12 })
13}
14
15fn projections_overlap(min_a: i128, max_a: i128, min_b: i128, max_b: i128) -> bool {
16 max_a > min_b && max_b > min_a
17}
18
19fn has_separating_axis(edge_ring: &[[i64; 2]], a: &[[i64; 2]], b: &[[i64; 2]]) -> bool {
20 let n = edge_ring.len();
21
22 for i in 0..n {
23 let next = if i + 1 < n { i + 1 } else { 0 };
24 let dx = edge_ring[next][0] - edge_ring[i][0];
25 let dy = edge_ring[next][1] - edge_ring[i][1];
26 let axis_x = dy;
27 let axis_y = -dx;
28
29 if axis_x == 0 && axis_y == 0 {
30 continue;
31 }
32
33 let (min_a, max_a) = project_onto_axis(a, axis_x, axis_y);
34 let (min_b, max_b) = project_onto_axis(b, axis_x, axis_y);
35
36 if !projections_overlap(min_a, max_a, min_b, max_b) {
37 return true;
38 }
39 }
40
41 false
42}
43
44pub fn sat_overlaps(a: &[[i64; 2]], b: &[[i64; 2]]) -> bool {
45 if !validate_polygon(a) || !validate_polygon(b) {
46 return false;
47 }
48
49 if has_separating_axis(a, a, b) {
50 return false;
51 }
52
53 if has_separating_axis(b, a, b) {
54 return false;
55 }
56
57 true
58}
59
60pub fn sat_overlaps_with_aabb(a: &[[i64; 2]], b: &[[i64; 2]]) -> bool {
61 if !validate_polygon(a) || !validate_polygon(b) {
62 return false;
63 }
64
65 let aabb_a = Aabb::from_ring(a);
66 let aabb_b = Aabb::from_ring(b);
67
68 if !aabb_a.intersects(&aabb_b) {
69 return false;
70 }
71
72 sat_overlaps(a, b)
73}
74
75#[cfg(test)]
76mod tests {
77 use super::*;
78
79 const M: i64 = 1_000_000;
80
81 fn square(ox: i64, oy: i64, size: i64) -> Vec<[i64; 2]> {
82 vec![
83 [ox, oy],
84 [ox + size, oy],
85 [ox + size, oy + size],
86 [ox, oy + size],
87 ]
88 }
89
90 #[test]
91 fn sat_gap_detected() {
92 let a = square(0, 0, M);
93 let b = square(2 * M, 0, M);
94
95 assert!(!sat_overlaps(&a, &b));
96 }
97
98 #[test]
99 fn sat_touching_edges_do_not_overlap() {
100 let a = square(0, 0, M);
101 let b = square(M, 0, M);
102
103 assert!(!sat_overlaps(&a, &b));
104 }
105
106 #[test]
107 fn sat_overlap_detected() {
108 let a = square(0, 0, 2 * M);
109 let b = square(M, M, 2 * M);
110
111 assert!(sat_overlaps(&a, &b));
112 }
113
114 #[test]
115 fn sat_micro_overlap_detected() {
116 let a = square(0, 0, M);
117 let b = vec![[M - 1, 0], [2 * M - 1, 0], [2 * M - 1, M], [M - 1, M]];
118
119 assert!(sat_overlaps(&a, &b));
120 }
121
122 #[test]
123 fn sat_corner_touching_does_not_overlap() {
124 let a = square(0, 0, M);
125 let b = square(M, M, M);
126
127 assert!(!sat_overlaps(&a, &b));
128 }
129
130 #[test]
131 fn sat_triangle_touching_does_not_overlap() {
132 let a = vec![[0, 0], [2 * M, 0], [M, 2 * M]];
133 let b = vec![[2 * M, 0], [3 * M, 0], [2 * M + M / 2, M]];
134
135 assert!(!sat_overlaps(&a, &b));
136 }
137
138 #[test]
139 fn contained_square_overlaps() {
140 let outer = square(0, 0, 10 * M);
141 let inner = square(2 * M, 2 * M, 3 * M);
142
143 assert!(sat_overlaps(&outer, &inner));
144 }
145
146 #[test]
147 fn identical_squares_overlap() {
148 let a = square(0, 0, M);
149 let b = square(0, 0, M);
150
151 assert!(sat_overlaps(&a, &b));
152 }
153
154 #[test]
155 fn sat_is_symmetric() {
156 let a = square(0, 0, 3 * M);
157 let b = square(2 * M, 2 * M, 3 * M);
158
159 assert_eq!(sat_overlaps(&a, &b), sat_overlaps(&b, &a),);
160 }
161
162 #[test]
163 fn aabb_pipeline_rejects_far_polygons() {
164 let a = square(0, 0, M);
165 let b = square(3 * M, 0, M);
166
167 assert!(!sat_overlaps_with_aabb(&a, &b));
168 }
169
170 #[test]
171 fn aabb_prefilter_allows_sat_for_overlapping() {
172 let a = square(0, 0, 3 * M);
173 let b = square(2 * M, 2 * M, 3 * M);
174
175 assert!(sat_overlaps_with_aabb(&a, &b));
176 }
177
178 #[test]
179 fn triangles_overlap_correctly() {
180 let a = vec![[0, 0], [4 * M, 0], [2 * M, 4 * M]];
181 let b = vec![[M, M], [3 * M, M], [2 * M, 3 * M]];
182
183 assert!(sat_overlaps(&a, &b));
184 }
185
186 #[test]
187 fn right_triangles_sharing_hypotenuse_do_not_overlap() {
188 let a = vec![[0, 0], [2 * M, 0], [2 * M, 2 * M]];
189 let b = vec![[0, 0], [0, 2 * M], [2 * M, 2 * M]];
190
191 assert!(!sat_overlaps(&a, &b));
192 }
193
194 #[test]
195 fn triangle_fully_inside_another_overlaps() {
196 let outer = vec![[0, 0], [4 * M, 0], [0, 4 * M]];
197 let inner = vec![[M, M], [2 * M, M], [M, 2 * M]];
198
199 assert!(sat_overlaps(&outer, &inner));
200 }
201
202 #[test]
203 fn sat_handles_world_extreme_coordinates() {
204 const MAX_WORLD: i64 = 40_075_017_000_000;
205
206 let a = vec![
207 [-MAX_WORLD, -MAX_WORLD],
208 [-MAX_WORLD + M, -MAX_WORLD],
209 [-MAX_WORLD + M, -MAX_WORLD + M],
210 [-MAX_WORLD, -MAX_WORLD + M],
211 ];
212 let b = vec![
213 [MAX_WORLD, MAX_WORLD],
214 [MAX_WORLD + M, MAX_WORLD],
215 [MAX_WORLD + M, MAX_WORLD + M],
216 [MAX_WORLD, MAX_WORLD + M],
217 ];
218
219 assert!(!sat_overlaps(&a, &b));
220 }
221
222 #[test]
223 fn sat_with_aabb_rejects_far_apart_polygons() {
224 let a = square(0, 0, M);
225 let b = square(100 * M, 100 * M, M);
226
227 assert!(!sat_overlaps_with_aabb(&a, &b));
228 }
229}