haar_lib/geom/
ccw.rs

1//! 点と線分の位置関係
2//!
3//! # Problems
4//! - <https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/1/CGL_1_C>
5
6use crate::geom::*;
7
8/// 点と線分の位置関係
9#[derive(Clone, Copy, Debug, PartialEq)]
10#[allow(non_camel_case_types)]
11pub enum CCW {
12    /// 点が線分と同一直線上にあり、かつ、点が線分の方向に対して後ろにある。
13    ONLINE_BACK,
14    /// 点が線分に対して、半時計回り方向にある(左側)。
15    COUNTER_CLOCKWISE,
16    /// 点が線分上にある。
17    ON_SEGMENT,
18    /// 点が線分に対して、時計回り方向にある(右側)。
19    CLOCKWISE,
20    /// 点が線分と同一直線上にあり、かつ、点が線分の方向に対して前にある。
21    ONLINE_FRONT,
22}
23
24impl CCW {
25    /// `ONLINE_BACK`ならば`true`を返す。
26    pub fn online_back(self) -> bool {
27        self == Self::ONLINE_BACK
28    }
29    /// `COUNTER_CLOCKWISE`ならば`true`を返す。
30    pub fn counter_clockwise(self) -> bool {
31        self == Self::COUNTER_CLOCKWISE
32    }
33    /// `ON_SEGMENT`ならば`true`を返す。
34    pub fn on_segment(self) -> bool {
35        self == Self::ON_SEGMENT
36    }
37    /// `CLOCKWISE`ならば`true`を返す。
38    pub fn clockwise(self) -> bool {
39        self == Self::CLOCKWISE
40    }
41    /// `ONLINE_FRONT`ならば`true`を返す。
42    pub fn online_front(self) -> bool {
43        self == Self::ONLINE_FRONT
44    }
45
46    /// `ONLINE_BACK`または`COUNTER_CLOCKWISE`ならば`-1`を返す。
47    ///
48    /// `ON_SEGMENT`ならば`0`を返す。
49    ///
50    /// `CLOCKWISE`または`ONLINE_FRONT`ならば`1`を返す。
51    pub fn to_value(self) -> i32 {
52        use self::CCW::*;
53        match self {
54            ONLINE_BACK | COUNTER_CLOCKWISE => -1,
55            ON_SEGMENT => 0,
56            CLOCKWISE | ONLINE_FRONT => 1,
57        }
58    }
59}
60
61/// `p0`から`p1`に向かう線分に対して、点`p2`の位置関係を求める。
62pub fn ccw(p0: Vector, p1: Vector, p2: Vector, eps: Eps) -> CCW {
63    use self::CCW::*;
64    let cr = (p1 - p0).cross(p2 - p0);
65    let d = (p1 - p0).dot(p2 - p0);
66
67    if eps.eq(cr, 0.0) {
68        if eps.lt(d, 0.0) {
69            ONLINE_BACK
70        } else if eps.gt((p2 - p0).abs(), (p1 - p0).abs()) {
71            ONLINE_FRONT
72        } else {
73            ON_SEGMENT
74        }
75    } else if eps.gt(cr, 0.0) {
76        COUNTER_CLOCKWISE
77    } else {
78        CLOCKWISE
79    }
80}
haar_lib/geom/ccw.rs

haar_lib/geom/
ccw.rs
