cp_library_rs/geometry/
basic.rs

1//! 点、直線等に関する基礎的な操作
2
3use crate::geometry::vec2::Vec2;
4
5/// 点（2次元平面）
6pub type Point = Vec2<f64>;
7
8/// 十分に小さい数
9pub const EPS: f64 = 1e-8;
10
11impl From<(f64, f64)> for Point {
12    fn from(value: (f64, f64)) -> Self {
13        Self(value.0, value.1)
14    }
15}
16
17impl Point {
18    /// 2点間のユークリッド距離を求める
19    ///
20    /// ```math
21    /// \|\boldsymbol{a} - \boldsymbol{b}\| = \sqrt{(a_x - b_x)^2 + (a_y - b_y)^2}
22    /// ```
23    pub fn dist(&self, other: Self) -> f64 {
24        self.dist2(other).sqrt()
25    }
26
27    /// ノルムを求める
28    ///
29    /// ```math
30    /// \|\boldsymbol{a}\| = \sqrt{a_x^2 + a_y^2}
31    /// ```
32    pub fn norm(&self) -> f64 {
33        self.norm2().sqrt()
34    }
35
36    /// 同じ向きの単位ベクトルを求める
37    pub fn unit(&self) -> Self {
38        *self / self.norm()
39    }
40
41    /// 法線ベクトル
42    /// （90度回転させたベクトル）
43    /// を求める
44    pub fn normal(&self) -> Self {
45        let Self(x, y) = *self;
46        Self(-y, x)
47    }
48
49    /// 原点周りに $`\theta`$ 回転させた点を求める
50    pub fn rotate_o(&self, theta: f64) -> Self {
51        let Self(x, y) = *self;
52        Self(
53            theta.cos() * x - theta.sin() * y,
54            theta.sin() * x + theta.cos() * y,
55        )
56    }
57}
58
59/// 直線（2次元平面）
60#[derive(Debug)]
61pub struct Line(pub Point, pub Point);
62
63impl Line {
64    /// 射影
65    /// （直線`l`に対して点`p`から引いた垂線の足）
66    /// を求める
67    pub fn projection(&self, p: Point) -> Point {
68        let Self(a, b) = *self;
69        let t = (p - a).dot(a - b) / (a - b).norm2();
70        a + (a - b) * t
71    }
72
73    /// 反射
74    /// （直線`l`に対して点`p`に対称な点）
75    /// を求める
76    pub fn reflection(&self, p: Point) -> Point {
77        p + (self.projection(p) - p) * 2.0
78    }
79
80    /// 2直線の直交判定
81    pub fn is_orthogonal(&self, other: &Self) -> bool {
82        (self.1 - self.0).dot(other.1 - other.0).abs() < EPS
83    }
84
85    /// 2直線の平行判定
86    pub fn is_parallel(&self, other: &Self) -> bool {
87        (self.1 - self.0).cross(other.1 - other.0).abs() < EPS
88    }
89
90    /// 2直線の交点を求める
91    ///
92    /// **戻り値**
93    /// - `Point` : 交点
94    pub fn cross_point(&self, other: &Self) -> Point {
95        let d1 = (self.1 - self.0).cross(other.1 - other.0);
96        let d2 = (self.1 - self.0).cross(self.1 - other.0);
97
98        if d1.abs() < EPS && d2.abs() < EPS {
99            return other.0;
100        }
101
102        other.0 + (other.1 - other.0) * (d2 / d1)
103    }
104
105    /// 点`p`と直線の距離を求める
106    pub fn dist_point(&self, p: Point) -> f64 {
107        let Self(a, b) = *self;
108        (b - a).cross(p - a).abs() / a.dist(b)
109    }
110}
111
112/// 3点 O, A, B の位置関係
113#[derive(Debug, PartialEq, Eq)]
114pub enum Orientation {
115    /// O, A, B が反時計回りになる場合
116    ///
117    /// > ```text
118    /// >  B   A
119    /// >  ↑ ➚
120    /// >  O
121    /// > ```
122    CounterClockwise,
123    /// O, A, B が時計回りになる場合
124    ///
125    /// > ```text
126    /// >  A   B
127    /// >  ↑ ➚
128    /// >  O
129    /// > ```
130    Clockwise,
131    /// B, O, A がこの順で同一直線上にある場合
132    ///
133    /// > ```text
134    /// > B ← O → A
135    /// > ```
136    OnlineBack,
137    /// O, A, B がこの順で同一直線上にある場合
138    ///
139    /// > ```text
140    /// > O → A → B
141    /// > ```
142    OnlineFront,
143    /// B が線分 OA 上にある場合
144    ///
145    /// > ```text
146    /// > O → B → A
147    /// > ```
148    OnSegment,
149}
150
151impl Orientation {
152    /// 3点 O, A, B の位置関係を調べる
153    pub fn calc(O: Point, mut A: Point, mut B: Point) -> Self {
154        A = A - O;
155        B = B - O;
156
157        if A.cross(B) > EPS {
158            return Orientation::CounterClockwise;
159        }
160
161        if A.cross(B) < -EPS {
162            return Orientation::Clockwise;
163        }
164
165        if A.dot(B) < 0.0 {
166            return Orientation::OnlineBack;
167        }
168
169        if A.norm2() < B.norm2() {
170            return Orientation::OnlineFront;
171        }
172
173        Orientation::OnSegment
174    }
175
176    /// 値を取得する
177    pub fn val(&self) -> f64 {
178        match self {
179            Orientation::CounterClockwise => 1.0,
180            Orientation::Clockwise => -1.0,
181            Orientation::OnlineBack => 2.0,
182            Orientation::OnlineFront => -2.0,
183            Orientation::OnSegment => 0.0,
184        }
185    }
186}
187
188/// 線分（2次元平面）
189#[derive(Debug, Clone, Copy)]
190pub struct Segment(pub Point, pub Point);
191
192impl Segment {
193    /// 2つの線分が衝突しているかどうかを判定する
194    pub fn has_intersection(&self, other: &Self) -> bool {
195        (Orientation::calc(self.0, self.1, other.0).val()
196            * Orientation::calc(self.0, self.1, other.1).val())
197            <= 0.0
198            && (Orientation::calc(other.0, other.1, self.0).val()
199                * Orientation::calc(other.0, other.1, self.1).val())
200                <= 0.0
201    }
202
203    /// 2つの線分の交点を求める
204    ///
205    /// **戻り値**
206    /// - 2つの線分が点`x`で交わるとき → Some(`x`)
207    /// - 2つの線分が交点を持たないとき → None
208    pub fn cross_point(&self, other: &Self) -> Option<Point> {
209        self.has_intersection(other).then(|| {
210            let l1 = self.to_line();
211            let l2 = other.to_line();
212            l1.cross_point(&l2)
213        })
214    }
215
216    /// 点`p`と線分の距離を求める
217    pub fn dist_point(&self, p: Point) -> f64 {
218        let Self(a, b) = *self;
219
220        if (b - a).dot(p - a) < EPS {
221            return p.dist(a);
222        }
223
224        if (a - b).dot(p - b) < EPS {
225            return p.dist(b);
226        }
227
228        self.to_line().dist_point(p)
229    }
230
231    /// 線分同士の距離を求める
232    pub fn dist_segment(&self, other: &Self) -> f64 {
233        if self.has_intersection(other) {
234            return 0.0;
235        }
236
237        let mut res = f64::MAX;
238
239        for d in [
240            self.dist_point(other.0),
241            self.dist_point(other.1),
242            other.dist_point(self.0),
243            other.dist_point(self.1),
244        ] {
245            if res > d {
246                res = d;
247            }
248        }
249
250        res
251    }
252
253    /// 直線に変換する
254    pub fn to_line(&self) -> Line {
255        let Self(a, b) = *self;
256        Line(a, b)
257    }
258}
cp_library_rs/geometry/basic.rs

cp_library_rs/geometry/
basic.rs
