二次元ユークリッド幾何 - 直線と点との接触 (CCW)

概要

CCW (Counter Clock Wise; 反時計回判定) とは, \(A \to B\) に向かう直線に対して点 \(P\) が右にあるか左にあるか, または直線上にあるかを判定する方法の一つ. 二つのベクトル \((B - A)\) と \((P - A)\) の外積の符号を見ればよい.

次を CCW 関数と定義する.

\[\mathrm{ccw}(A, B, P) = \begin{cases} 1 & \text{if } (B - A) \times (P - A) \gt 0 \\ 0 & \text{if } (B - A) \times (P - A) \lt 0 \\ -1 & \text{if } (B - A) \times (P - A) = 0 \\ \end{cases}\]

そこで直線 \((A \to B)\) と点 \(P\) との接触判定は次のように行う.

\[\mathrm{ccw}^{\text{line}}(A \to B, P) = \begin{cases} \text{ Left } & \text{if } \mathrm{ccw}(A, B, P) = 1 \\ \text{ Right } & \text{if } \mathrm{ccw}(A, B, P) = -1 \\ \text{ Online } & \text{if } \mathrm{ccw}(A, B, P) = 0 \\ \end{cases}\]

実装

/// Geometry2D - CCW (直線と点の関係)
use crate::geometry2d::line::*;
use crate::geometry2d::point::*;

#[derive(Debug, PartialEq, Eq, Clone, Copy)]
pub enum CCW {
    Right,
    Left,
    Online,
}

pub fn ccw(a: Point, b: Point, c: Point) -> i32 {
    let u = b - a;
    let v = c - a;
    let d = u.det(&v);
    if d > 0.0 {
        1
    } else if d < 0.0 {
        -1
    } else {
        0
    }
}

pub fn ccw_line(l: Line, p: Point) -> CCW {
    let d = ccw(l.0, l.1, p);
    if d > 0 {
        CCW::Left
    } else if d < 0 {
        CCW::Right
    } else {
        CCW::Online
    }
}

#[cfg(test)]
mod test_ccw_line {
    use crate::geometry2d::ccw_line::*;

    #[test]
    fn it_works() {
        let l = Line(Point(0.0, 0.0), Point(1.0, 1.0));
        assert_eq!(ccw_line(l, Point(1.0, 0.0)), CCW::Right);
        assert_eq!(ccw_line(l, Point(0.0, 1.0)), CCW::Left);
        assert_eq!(ccw_line(l, Point(2.0, 2.0)), CCW::Online);
    }
}