Skip to main content

mathverse_geometry/
intersection.rs

1//! Collision and intersection: point-in-polygon, segment-polygon, circle-polygon,
2//! polygon-polygon (SAT), convex hull, convexity test.
3
4use super::shapes2d::{Circle, Point2, Polygon};
5use super::primitives2d::LineSegment2;
6
7// ---------------------------------------------------------------------------
8// Point in polygon
9// ---------------------------------------------------------------------------
10
11/// Ray-casting algorithm: does a horizontal ray from `p` cross the polygon edge an odd number of times?
12pub 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
31/// Winding number algorithm: returns winding number of polygon around `p`.
32/// 0 = outside, nonzero = inside (with winding semantics).
33pub 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
59// ---------------------------------------------------------------------------
60// Segment vs polygon
61// ---------------------------------------------------------------------------
62
63/// Whether a line segment intersects a polygon.
64pub 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
76/// Whether two line segments intersect (proper or improper).
77pub 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    // Collinear cases
88    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
102// ---------------------------------------------------------------------------
103// Circle vs polygon
104// ---------------------------------------------------------------------------
105
106/// Whether a circle intersects a polygon (edge or interior).
107pub 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
123// ---------------------------------------------------------------------------
124// Polygon vs polygon (SAT)
125// ---------------------------------------------------------------------------
126
127/// Separating Axis Theorem: do two convex polygons overlap?
128/// Panics if either polygon is concave (SAT is only valid for convex polygons).
129pub 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        // Perpendicular (normal)
155        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
174// ---------------------------------------------------------------------------
175// Convex hull
176// ---------------------------------------------------------------------------
177
178/// Andrew's monotone chain convex hull algorithm.
179pub 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
218// ---------------------------------------------------------------------------
219// Convexity test
220// ---------------------------------------------------------------------------
221
222/// Whether a simple polygon is convex.
223pub 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}