mesh_geometry/queries/
point_in_polygon.rs

1//! Point-in-polygon queries for mesh-geometry.
2
3use crate::{Float, Point2};
4
5/// Returns true if `pt` is inside the planar polygon `poly` (winding-number).
6/// Assumes `poly` is closed (first != last) and simple (non-self-intersecting).
7pub fn point_in_polygon<T: Float>(pt: Point2<T>, poly: &[Point2<T>]) -> bool {
8    let mut winding: i32 = 0;
9    let n = poly.len();
10    for i in 0..n {
11        let p1 = poly[i];
12        let p2 = poly[(i + 1) % n];
13        if p1.y <= pt.y {
14            if p2.y > pt.y && is_left(p1, p2, pt) > T::zero() {
15                winding += 1;
16            }
17        } else {
18            if p2.y <= pt.y && is_left(p1, p2, pt) < T::zero() {
19                winding -= 1;
20            }
21        }
22    }
23    winding != 0
24}
25
26#[inline]
27fn is_left<T: Float>(a: Point2<T>, b: Point2<T>, c: Point2<T>) -> T {
28    (b.x - a.x) * (c.y - a.y) - (c.x - a.x) * (b.y - a.y)
29}
30
31#[cfg(test)]
32mod tests {
33    use super::*;
34    use crate::Point2;
35
36    #[test]
37    fn inside_triangle() {
38        let tri = [
39            Point2::new(0.0, 0.0),
40            Point2::new(5.0, 0.0),
41            Point2::new(0.0, 5.0),
42        ];
43        assert!(point_in_polygon(Point2::new(1.0,1.0), &tri));
44        assert!(!point_in_polygon(Point2::new(5.0,5.0), &tri));
45    }
46
47    #[test]
48    fn inside_square_and_hole() {
49        let square = [
50            Point2::new(-1.0, -1.0),
51            Point2::new( 1.0, -1.0),
52            Point2::new( 1.0,  1.0),
53            Point2::new(-1.0,  1.0),
54        ];
55        assert!(point_in_polygon(Point2::new(0.0,0.0), &square));
56        assert!(!point_in_polygon(Point2::new(2.0,0.0), &square));
57    }
58}
mesh_geometry/queries/point_in_polygon.rs

mesh_geometry/queries/
point_in_polygon.rs
