competitive/geometry/
line.rs

1use super::{Approx, Ccw, Ccwable, Complex, Float};
2
3#[derive(Clone, Debug, PartialEq)]
4pub struct Line<T> {
5    p1: Complex<T>,
6    p2: Complex<T>,
7}
8impl<T> Line<T> {
9    pub fn new(p1: Complex<T>, p2: Complex<T>) -> Self {
10        Line { p1, p2 }
11    }
12}
13impl<T> Line<T>
14where
15    T: Ccwable,
16{
17    pub fn dir(&self) -> Complex<T> {
18        self.p2 - self.p1
19    }
20    pub fn ccw(&self, p: Complex<T>) -> Ccw {
21        Ccw::ccw(self.p1, self.p2, p)
22    }
23    pub fn is_parallel(&self, other: &Self) -> bool {
24        Approx(self.dir().cross(other.dir())) == Approx(T::zero())
25    }
26    pub fn is_orthogonal(&self, other: &Self) -> bool {
27        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
28    }
29}
30impl<T> Line<T>
31where
32    T: Ccwable + Float,
33{
34    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
35        let e = self.dir().unit();
36        self.p1 + e * (p - self.p1).dot(e)
37    }
38    pub fn reflection(&self, p: Complex<T>) -> Complex<T> {
39        let d = self.projection(p) - p;
40        p + d + d
41    }
42    pub fn distance_point(&self, p: Complex<T>) -> T {
43        (p / self.dir().unit()).re
44    }
45}
46
47#[derive(Clone, Debug, PartialEq)]
48pub struct LineSegment<T> {
49    p1: Complex<T>,
50    p2: Complex<T>,
51}
52impl<T> LineSegment<T> {
53    pub fn new(p1: Complex<T>, p2: Complex<T>) -> Self {
54        LineSegment { p1, p2 }
55    }
56}
57impl<T> LineSegment<T>
58where
59    T: Ccwable,
60{
61    pub fn dir(&self) -> Complex<T> {
62        self.p2 - self.p1
63    }
64    pub fn ccw(&self, p: Complex<T>) -> Ccw {
65        Ccw::ccw(self.p1, self.p2, p)
66    }
67    pub fn is_parallel(&self, other: &Self) -> bool {
68        Approx(self.dir().cross(other.dir())) == Approx(T::zero())
69    }
70    pub fn is_orthogonal(&self, other: &Self) -> bool {
71        Approx(self.dir().dot(other.dir())) == Approx(T::zero())
72    }
73    pub fn intersect(&self, other: &Self) -> bool {
74        self.ccw(other.p1) as i8 * self.ccw(other.p2) as i8 <= 0
75            && other.ccw(self.p1) as i8 * other.ccw(self.p2) as i8 <= 0
76    }
77    pub fn intersect_point(&self, p: Complex<T>) -> bool {
78        self.ccw(p) == Ccw::OnSegment
79    }
80}
81impl<T> LineSegment<T>
82where
83    T: Ccwable + Float,
84{
85    pub fn projection(&self, p: Complex<T>) -> Complex<T> {
86        let e = self.dir().unit();
87        self.p1 + e * (p - self.p1).dot(e)
88    }
89    pub fn reflection(&self, p: Complex<T>) -> Complex<T> {
90        let d = self.projection(p) - p;
91        p + d + d
92    }
93    pub fn cross_point(&self, other: &Self) -> Option<Complex<T>> {
94        if self.intersect(other) {
95            let a = self.dir().cross(other.dir());
96            let b = self.dir().cross(self.p2 - other.p1);
97            if Approx(a.abs()) == Approx(T::zero()) && Approx(b.abs()) == Approx(T::zero()) {
98                Some(other.p1)
99            } else {
100                Some(other.p1 + (other.dir() * b / a))
101            }
102        } else {
103            None
104        }
105    }
106    pub fn distance_point(&self, p: Complex<T>) -> T {
107        let r = self.projection(p);
108        if self.intersect_point(r) {
109            (r - p).abs()
110        } else {
111            (self.p1 - p).abs().min((self.p2 - p).abs())
112        }
113    }
114    pub fn distance(&self, other: &Self) -> T {
115        if self.intersect(other) {
116            T::zero()
117        } else {
118            let d1 = self.distance_point(other.p1);
119            let d2 = self.distance_point(other.p2);
120            let d3 = other.distance_point(self.p1);
121            let d4 = other.distance_point(self.p2);
122            d1.min(d2).min(d3).min(d4)
123        }
124    }
125}
competitive/geometry/line.rs

competitive/geometry/
line.rs
