1use super::shapes2d::{Circle, Point2, Polygon};
5use super::primitives2d::LineSegment2;
6
7pub fn point_in_polygon(p: Point2, poly: &Polygon) -> bool {
13 let pts = &poly.points;
14 let n = pts.len();
15 let mut inside = false;
16 let mut j = n - 1;
17 for i in 0..n {
18 let yi_gt = pts[i].y > p.y;
19 let yj_gt = pts[j].y > p.y;
20 if yi_gt != yj_gt {
21 let x_intersect = (pts[j].x - pts[i].x) * (p.y - pts[i].y) / (pts[j].y - pts[i].y) + pts[i].x;
22 if p.x < x_intersect {
23 inside = !inside;
24 }
25 }
26 j = i;
27 }
28 inside
29}
30
31pub fn winding_number(p: Point2, poly: &Polygon) -> i32 {
34 let pts = &poly.points;
35 let n = pts.len();
36 let mut wn = 0i32;
37 for i in 0..n {
38 let a = pts[i];
39 let b = pts[(i + 1) % n];
40 if a.y <= p.y {
41 if b.y > p.y {
42 if cross_2d(a, b, p) > 0.0 {
43 wn += 1;
44 }
45 }
46 } else if b.y <= p.y {
47 if cross_2d(a, b, p) < 0.0 {
48 wn -= 1;
49 }
50 }
51 }
52 wn
53}
54
55fn cross_2d(a: Point2, b: Point2, c: Point2) -> f64 {
56 (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
57}
58
59pub fn segment_intersects_polygon(seg: LineSegment2, poly: &Polygon) -> bool {
65 let pts = &poly.points;
66 let n = pts.len();
67 for i in 0..n {
68 let edge = LineSegment2::new(pts[i], pts[(i + 1) % n]);
69 if segments_intersect(seg, edge) {
70 return true;
71 }
72 }
73 point_in_polygon(seg.a, poly) || point_in_polygon(seg.b, poly)
74}
75
76pub fn segments_intersect(a: LineSegment2, b: LineSegment2) -> bool {
78 let d1 = cross_2d(a.a, a.b, b.a);
79 let d2 = cross_2d(a.a, a.b, b.b);
80 let d3 = cross_2d(b.a, b.b, a.a);
81 let d4 = cross_2d(b.a, b.b, a.b);
82 if ((d1 > 0.0 && d2 < 0.0) || (d1 < 0.0 && d2 > 0.0))
83 && ((d3 > 0.0 && d4 < 0.0) || (d3 < 0.0 && d4 > 0.0))
84 {
85 return true;
86 }
87 if d1.abs() < 1e-10 && on_segment(a, b.a) { return true; }
89 if d2.abs() < 1e-10 && on_segment(a, b.b) { return true; }
90 if d3.abs() < 1e-10 && on_segment(b, a.a) { return true; }
91 if d4.abs() < 1e-10 && on_segment(b, a.b) { return true; }
92 false
93}
94
95fn on_segment(seg: LineSegment2, p: Point2) -> bool {
96 p.x >= seg.a.x.min(seg.b.x) - 1e-10
97 && p.x <= seg.a.x.max(seg.b.x) + 1e-10
98 && p.y >= seg.a.y.min(seg.b.y) - 1e-10
99 && p.y <= seg.a.y.max(seg.b.y) + 1e-10
100}
101
102pub fn circle_intersects_polygon(circ: Circle, poly: &Polygon) -> bool {
108 if point_in_polygon(circ.center, poly) {
109 return true;
110 }
111 let pts = &poly.points;
112 let n = pts.len();
113 for i in 0..n {
114 let edge = LineSegment2::new(pts[i], pts[(i + 1) % n]);
115 let closest = edge.closest_point(circ.center);
116 if closest.distance_to(circ.center) <= circ.radius {
117 return true;
118 }
119 }
120 false
121}
122
123pub fn polygons_intersect(poly_a: &Polygon, poly_b: &Polygon) -> bool {
130 assert!(is_convex(poly_a), "polygons_intersect requires convex polygons (SAT)");
131 assert!(is_convex(poly_b), "polygons_intersect requires convex polygons (SAT)");
132 let axes_a = sat_axes(&poly_a.points);
133 let axes_b = sat_axes(&poly_b.points);
134 for axis in axes_a.iter().chain(axes_b.iter()) {
135 if let Some((min_a, max_a)) = project_polygon(&poly_a.points, *axis) {
136 if let Some((min_b, max_b)) = project_polygon(&poly_b.points, *axis) {
137 if max_a < min_b || max_b < min_a {
138 return false;
139 }
140 }
141 }
142 }
143 true
144}
145
146fn sat_axes(pts: &[Point2]) -> Vec<Point2> {
147 let n = pts.len();
148 let mut axes = Vec::with_capacity(n);
149 for i in 0..n {
150 let edge = Point2::new(
151 pts[(i + 1) % n].x - pts[i].x,
152 pts[(i + 1) % n].y - pts[i].y,
153 );
154 axes.push(Point2::new(-edge.y, edge.x));
156 }
157 axes
158}
159
160fn project_polygon(pts: &[Point2], axis: Point2) -> Option<(f64, f64)> {
161 if pts.is_empty() {
162 return None;
163 }
164 let mut min = pts[0].x * axis.x + pts[0].y * axis.y;
165 let mut max = min;
166 for p in &pts[1..] {
167 let proj = p.x * axis.x + p.y * axis.y;
168 if proj < min { min = proj; }
169 if proj > max { max = proj; }
170 }
171 Some((min, max))
172}
173
174pub fn convex_hull(points: &[Point2]) -> Vec<Point2> {
180 let mut pts = points.to_vec();
181 if pts.len() <= 2 {
182 return pts;
183 }
184 pts.sort_by(|a, b| {
185 a.x.partial_cmp(&b.x).unwrap_or(std::cmp::Ordering::Equal)
186 .then(a.y.partial_cmp(&b.y).unwrap_or(std::cmp::Ordering::Equal))
187 });
188 let mut lower: Vec<Point2> = Vec::new();
189 for p in &pts {
190 while lower.len() >= 2 {
191 let n = lower.len();
192 if cross_2d(lower[n - 2], lower[n - 1], *p) <= 0.0 {
193 lower.pop();
194 } else {
195 break;
196 }
197 }
198 lower.push(*p);
199 }
200 let mut upper: Vec<Point2> = Vec::new();
201 for p in pts.iter().rev() {
202 while upper.len() >= 2 {
203 let n = upper.len();
204 if cross_2d(upper[n - 2], upper[n - 1], *p) <= 0.0 {
205 upper.pop();
206 } else {
207 break;
208 }
209 }
210 upper.push(*p);
211 }
212 lower.pop();
213 upper.pop();
214 lower.extend(upper);
215 lower
216}
217
218pub fn is_convex(poly: &Polygon) -> bool {
224 let pts = &poly.points;
225 let n = pts.len();
226 if n < 3 {
227 return false;
228 }
229 let mut sign = 0i8;
230 for i in 0..n {
231 let a = pts[i];
232 let b = pts[(i + 1) % n];
233 let c = pts[(i + 2) % n];
234 let cross = (b.x - a.x) * (c.y - b.y) - (b.y - a.y) * (c.x - b.x);
235 if cross.abs() < 1e-12 {
236 continue;
237 }
238 let s = if cross > 0.0 { 1 } else { -1 };
239 if sign != 0 && s != sign {
240 return false;
241 }
242 sign = s;
243 }
244 true
245}
246
247#[cfg(test)]
248mod tests {
249 use super::*;
250 use super::super::shapes2d::Polygon;
251
252 fn pt(x: f64, y: f64) -> Point2 { Point2::new(x, y) }
253
254 fn square() -> Polygon {
255 Polygon::new(vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(2.0, 2.0), pt(0.0, 2.0)])
256 }
257
258 #[test]
259 fn point_in_polygon_test() {
260 let sq = square();
261 assert!(point_in_polygon(pt(1.0, 1.0), &sq));
262 assert!(!point_in_polygon(pt(3.0, 3.0), &sq));
263 }
264
265 #[test]
266 fn winding_number_test() {
267 let sq = square();
268 assert_ne!(winding_number(pt(1.0, 1.0), &sq), 0);
269 assert_eq!(winding_number(pt(3.0, 3.0), &sq), 0);
270 }
271
272 #[test]
273 fn segment_polygon_intersect() {
274 let sq = square();
275 let seg = LineSegment2::new(pt(-1.0, 1.0), pt(3.0, 1.0));
276 assert!(segment_intersects_polygon(seg, &sq));
277 let seg2 = LineSegment2::new(pt(3.0, 3.0), pt(5.0, 5.0));
278 assert!(!segment_intersects_polygon(seg2, &sq));
279 }
280
281 #[test]
282 fn circle_polygon_intersect() {
283 let sq = square();
284 let c = Circle::new(pt(1.0, 1.0), 0.5);
285 assert!(circle_intersects_polygon(c, &sq));
286 let c2 = Circle::new(pt(5.0, 5.0), 0.5);
287 assert!(!circle_intersects_polygon(c2, &sq));
288 }
289
290 #[test]
291 fn polygon_intersect_sat() {
292 let a = square();
293 let b = Polygon::new(vec![pt(1.0, 1.0), pt(3.0, 1.0), pt(3.0, 3.0), pt(1.0, 3.0)]);
294 assert!(polygons_intersect(&a, &b));
295 let c = Polygon::new(vec![pt(5.0, 5.0), pt(7.0, 5.0), pt(7.0, 7.0), pt(5.0, 7.0)]);
296 assert!(!polygons_intersect(&a, &c));
297 }
298
299 #[test]
300 fn convex_hull_test() {
301 let pts = vec![pt(0.0, 0.0), pt(1.0, 1.0), pt(2.0, 0.0), pt(1.0, -1.0), pt(1.0, 0.5)];
302 let hull = convex_hull(&pts);
303 assert_eq!(hull.len(), 4);
304 }
305
306 #[test]
307 fn convexity_test() {
308 assert!(is_convex(&square()));
309 let concave = Polygon::new(vec![pt(0.0, 0.0), pt(2.0, 0.0), pt(1.0, 0.5), pt(2.0, 2.0), pt(0.0, 2.0)]);
310 assert!(!is_convex(&concave));
311 }
312}