1use crate::nearest::Real;
7
8pub 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
24pub 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 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}