Skip to main content

kernel_api/
polygon.rs

1//! A closed polygon in a plane, its corners in order and the last joined
2//! back to the first: the area it encloses and whether it holds a point.
3//! One implementation over plain coordinates, in single or double
4//! precision.
5
6use crate::nearest::Real;
7
8/// The area `polygon` encloses, signed by the way it is walked: positive
9/// counter-clockwise (x toward y), negative clockwise; zero with fewer
10/// than three corners. A caller wanting the size alone takes `abs`.
11pub fn signed_area<R: Real>(polygon: &[[R; 2]]) -> R {
12    let n = polygon.len();
13    if n < 3 {
14        return R::ZERO;
15    }
16    let mut twice = R::ZERO;
17    for i in 0..n {
18        let (a, b) = (polygon[i], polygon[(i + 1) % n]);
19        twice = twice + (a[0] * b[1] - b[0] * a[1]);
20    }
21    twice / (R::ONE + R::ONE)
22}
23
24/// Whether `p` lies inside `polygons` taken together, by the even-odd
25/// rule: a point inside an odd number of them is in, so a polygon inside
26/// another is a hole whichever way either is walked.
27///
28/// A point on an edge is decided by a half-open rule rather than taken
29/// as in or out: an edge counts from its lower end up to, not including,
30/// its upper end, and a crossing exactly at `p` does not count. Two
31/// polygons sharing an edge then never both hold a point on it.
32pub fn contains<R: Real>(polygons: &[&[[R; 2]]], p: [R; 2]) -> bool {
33    let mut odd = false;
34    for polygon in polygons {
35        let n = polygon.len();
36        for i in 0..n {
37            let (a, b) = (polygon[i], polygon[(i + 1) % n]);
38            if (a[1] > p[1]) != (b[1] > p[1]) {
39                let x = a[0] + (p[1] - a[1]) / (b[1] - a[1]) * (b[0] - a[0]);
40                if x > p[0] {
41                    odd = !odd;
42                }
43            }
44        }
45    }
46    odd
47}
48
49#[cfg(test)]
50mod tests {
51    use super::*;
52
53    #[test]
54    fn area_is_signed_by_the_walk_and_containment_is_even_odd() {
55        let square = [[0.0, 0.0], [2.0, 0.0], [2.0, 3.0], [0.0, 3.0]];
56        let mut clockwise = square;
57        clockwise.reverse();
58        assert_eq!(signed_area(&square), 6.0);
59        assert_eq!(signed_area(&clockwise), -6.0);
60        assert_eq!(signed_area(&square[..2]), 0.0);
61        assert_eq!(signed_area(&[[0.0f32, 0.0], [1.0, 0.0], [0.0, 1.0]]), 0.5);
62
63        let hole = [[0.5, 0.5], [1.5, 0.5], [1.5, 1.5], [0.5, 1.5]];
64        assert!(contains(&[&square], [1.0, 1.0]));
65        assert!(!contains(&[&square, &hole], [1.0, 1.0]));
66        assert!(contains(&[&square, &hole], [1.8, 2.5]));
67        assert!(!contains(&[&square], [3.0, 1.0]));
68        assert!(contains(
69            &[&[[0.0f32, 0.0], [4.0, 0.0], [0.0, 4.0]][..]],
70            [1.0, 1.0]
71        ));
72        // Two squares sharing the edge x = 2: a point on it is in one only.
73        let right = [[2.0, 0.0], [4.0, 0.0], [4.0, 3.0], [2.0, 3.0]];
74        let on_edge = [2.0, 1.0];
75        assert_ne!(contains(&[&square], on_edge), contains(&[&right], on_edge));
76    }
77}