competitive/geometry/
ccw.rs

1use super::{Approx, ApproxOrd, Complex, Zero};
2use std::{
3    cmp::Ordering,
4    ops::{Add, Mul, Sub},
5};
6
7pub trait Ccwable:
8    ApproxOrd + Copy + Zero + Add<Output = Self> + Sub<Output = Self> + Mul<Output = Self>
9{
10}
11
12impl Ccwable for i8 {}
13impl Ccwable for i16 {}
14impl Ccwable for i32 {}
15impl Ccwable for i64 {}
16impl Ccwable for i128 {}
17impl Ccwable for isize {}
18impl Ccwable for f32 {}
19impl Ccwable for f64 {}
20
21#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
22pub enum Ccw {
23    /// a--b--c
24    OnlineFront = -2,
25    /// a--b-vc
26    Clockwise = -1,
27    /// a--c--b
28    OnSegment = 0,
29    /// a--b-^c
30    CounterClockwise = 1,
31    /// c--a--b
32    OnlineBack = 2,
33}
34impl Ccw {
35    pub fn ccw<T>(a: Complex<T>, b: Complex<T>, c: Complex<T>) -> Self
36    where
37        T: Ccwable,
38    {
39        let x = b - a;
40        let y = c - a;
41        let zero = T::zero();
42        match x.cross(y).approx_cmp(&zero) {
43            Ordering::Less => Self::Clockwise,
44            Ordering::Greater => Self::CounterClockwise,
45            Ordering::Equal => {
46                if Approx(x.dot(y)) < Approx(zero) {
47                    Self::OnlineBack
48                } else if Approx((a - b).dot(c - b)) < Approx(zero) {
49                    Self::OnlineFront
50                } else {
51                    Self::OnSegment
52                }
53            }
54        }
55    }
56    pub fn ccw_open<T>(a: Complex<T>, b: Complex<T>, c: Complex<T>) -> Self
57    where
58        T: Ccwable,
59    {
60        let x = b - a;
61        let y = c - a;
62        let zero = T::zero();
63        match x.cross(y).approx_cmp(&zero) {
64            Ordering::Less => Self::Clockwise,
65            Ordering::Greater => Self::CounterClockwise,
66            Ordering::Equal => {
67                if Approx(x.dot(y)) <= Approx(zero) {
68                    Self::OnlineBack
69                } else if Approx((a - b).dot(c - b)) <= Approx(zero) {
70                    Self::OnlineFront
71                } else {
72                    Self::OnSegment
73                }
74            }
75        }
76    }
77}
competitive/geometry/ccw.rs

competitive/geometry/
ccw.rs
