haar_lib/geom/
point_in_polygon.rs

1//! 点と多角形の位置関係
2
3use crate::geom::{ccw::*, *};
4use std::f64::consts::PI;
5
6/// 点と多角形の位置関係
7#[derive(Clone, Copy, Debug, PartialEq, Eq)]
8#[allow(non_camel_case_types)]
9pub enum PointPolygon {
10    /// 点が多角形の内部にある
11    INCLUSION,
12    /// 点が多角形上にある
13    ON_SEGMENT,
14    /// 点が多角形の外部にある
15    EXCLUSION,
16}
17
18impl PointPolygon {
19    /// `INCLUSION`かを判定
20    pub fn inclusion(self) -> bool {
21        self == Self::INCLUSION
22    }
23    /// `ON_SEGMENT`かを判定
24    pub fn on_segment(self) -> bool {
25        self == Self::ON_SEGMENT
26    }
27    /// `EXCLUSION`かを判定
28    pub fn exclusion(self) -> bool {
29        self == Self::EXCLUSION
30    }
31}
32
33/// 点と多角形の位置関係を求める
34pub fn point_in_polygon(p: Vector, pl: &[Vector], eps: Eps) -> PointPolygon {
35    use self::PointPolygon::*;
36
37    let n = pl.len();
38    let mut d = 0.0;
39
40    for i in 0..n {
41        if ccw(pl[i], pl[(i + 1) % n], p, eps) == CCW::ON_SEGMENT {
42            return ON_SEGMENT;
43        }
44
45        let mut a = pl[i].angle(p);
46        let mut b = pl[(i + 1) % n].angle(p);
47
48        if eps.lt(a, 0.0) {
49            a += 2.0 * PI;
50        }
51        if eps.lt(b, 0.0) {
52            b += 2.0 * PI;
53        }
54
55        let mut ang = b - a;
56
57        if eps.gt(ang.abs(), PI) {
58            if eps.le(ang, 0.0) {
59                ang += 2.0 * PI;
60            } else {
61                ang -= 2.0 * PI;
62            }
63        }
64
65        d += ang;
66    }
67
68    if eps.eq((d.abs() - 2.0 * PI).abs(), 0.0) {
69        INCLUSION
70    } else {
71        EXCLUSION
72    }
73}