algorithm_rs/
geometry.rs

1use std::collections::VecDeque;
2use std::ops::{Add, Div, Mul, Sub};
3
4// FIXME (himkt): Eq for Point<f64> won't work as expected.
5#[derive(Copy, Clone, Debug, Eq, PartialEq, Ord, PartialOrd)]
6pub struct Point<T>(pub T, pub T);
7
8impl<T: Add<T, Output = T>> std::ops::Add<Point<T>> for Point<T> {
9    type Output = Point<T>;
10    fn add(self, _rhs: Point<T>) -> Self::Output {
11        Point(self.0 + _rhs.0, self.1 + _rhs.1)
12    }
13}
14
15impl<T: Sub<T, Output = T>> std::ops::Sub<Point<T>> for Point<T> {
16    type Output = Point<T>;
17    fn sub(self, _rhs: Point<T>) -> Self {
18        Point(self.0 - _rhs.0, self.1 - _rhs.1)
19    }
20}
21
22impl<T: Copy + Mul<T, Output = T>> std::ops::Mul<T> for Point<T> {
23    type Output = Point<T>;
24    fn mul(self, k: T) -> Self {
25        Self(k * self.0, k * self.1)
26    }
27}
28
29impl<T: Copy + Div<T, Output = T>> std::ops::Div<T> for Point<T> {
30    type Output = Self;
31    fn div(self, k: T) -> Self {
32        Self(self.0 / k, self.1 / k)
33    }
34}
35
36impl<T: Mul<T, Output = T> + Sub<T, Output = T>> Point<T> {
37    pub fn det(self, _rhs: Point<T>) -> T {
38        self.0 * _rhs.1 - self.1 * _rhs.0
39    }
40}
41
42#[cfg(test)]
43mod test_point {
44    use crate::geometry::Point;
45
46    #[test]
47    fn it_works_i64() {
48        let p1: Point<i64> = Point(4, 6);
49        let p2 = Point(6, 4);
50
51        assert_eq!(p1 + p2, Point(10, 10));
52        assert_eq!(p1 - p2, Point(-2, 2));
53        assert_eq!(p1 * 4, Point(16, 24));
54        assert_eq!(p1 / 2, Point(2, 3));
55    }
56
57    #[test]
58    fn it_works_f64() {
59        let p1: Point<f64> = Point(4.0, 6.0);
60        let p2 = Point(6.0, 4.0);
61
62        assert_eq!(p1 + p2, Point(10.0, 10.0));
63        assert_eq!(p1 - p2, Point(-2.0, 2.0));
64        assert_eq!(p1 * 4.0, Point(16.0, 24.0));
65        assert_eq!(p1 / 2.0, Point(2.0, 3.0));
66    }
67}
68
69pub struct Line<T>(pub Point<T>, pub Point<T>);
70
71pub trait LineAPI<T> {
72    fn distance(&self, p: Point<T>) -> f64;
73    fn contains_point(&self, p: Point<T>) -> bool;
74}
75
76// i64
77impl LineAPI<i64> for Line<i64> {
78    fn distance(&self, p: Point<i64>) -> f64 {
79        let v1 = self.1 - self.0;
80        let v2 = p - self.0;
81        let l1 = ((v1.0 * v1.0 + v1.1 * v1.1) as f64).sqrt();
82        let det = v1.det(v2) as f64;
83        det / l1
84    }
85
86    fn contains_point(&self, p: Point<i64>) -> bool {
87        let d = self.1 - self.0;
88        let e = p - self.0;
89        d.1 * e.0 == d.0 * e.1
90    }
91}
92
93// f64
94impl LineAPI<f64> for Line<f64> {
95    fn distance(&self, p: Point<f64>) -> f64 {
96        let v1 = self.1 - self.0;
97        let v2 = p - self.0;
98        let l1 = (v1.0 * v1.0 + v1.1 * v1.1).sqrt();
99        let det = v1.det(v2);
100        det / l1
101    }
102
103    fn contains_point(&self, p: Point<f64>) -> bool {
104        let d = self.1 - self.0;
105        let e = p - self.0;
106        d.1 * e.0 == d.0 * e.1
107    }
108}
109
110#[cfg(test)]
111mod test_line {
112    use crate::geometry::Line;
113    use crate::geometry::LineAPI;
114    use crate::geometry::Point;
115
116    #[test]
117    fn it_works_line_f64() {
118        let x = Point(0.0, 0.0);
119        let y = Point(2.0, 3.0);
120        let line = Line(x, y);
121
122        let z = Point(0.0, 3.0);
123        let d = line.distance(z);
124        let d_truth = 1.664_100_588_675_687_4;
125
126        let result = (d * 1_000_000_000.0) as i64;
127        let expected = (d_truth * 1_000_000_000.0) as i64;
128        assert_eq!(result, expected);
129    }
130
131    #[test]
132    fn it_works_line_i64() {
133        let x = Point(0, 0);
134        let y = Point(2, 3);
135        let line = Line(x, y);
136
137        let z = Point(0, 3);
138        let d = line.distance(z);
139        let d_truth = 1.664_100_588_675_687_4;
140
141        let result = (d * 1_000_000_000.0) as i64;
142        let expected = (d_truth * 1_000_000_000.0) as i64;
143        assert_eq!(result, expected);
144
145        // contain
146        assert!(line.contains_point(Point(4, 6)));
147        assert!(line.contains_point(Point(-2, -3)));
148        assert!(!line.contains_point(Point(1, 1)));
149    }
150}
151
152pub fn convex_hull(ps: Vec<(i64, i64)>) -> Vec<(i64, i64)> {
153    let n = ps.len();
154
155    let mut ps: Vec<Point<i64>> = ps.iter().map(|&(x, y)| Point::<i64>(x, y)).collect();
156
157    ps.sort();
158
159    let mut k = 0;
160    let mut deque: VecDeque<Point<i64>> = VecDeque::new();
161
162    for &pi in &ps {
163        while k > 1 && (deque[k - 1] - deque[k - 2]).det(pi - deque[k - 1]) <= 0 {
164            deque.pop_back();
165            k -= 1;
166        }
167        deque.push_back(pi);
168        k += 1;
169    }
170
171    let t = k;
172    for i in (0..n - 1).rev() {
173        let pi = ps[i];
174        while k > t && (deque[k - 1] - deque[k - 2]).det(pi - deque[k - 1]) <= 0 {
175            deque.pop_back();
176            k -= 1;
177        }
178        deque.push_back(pi);
179        k += 1;
180    }
181
182    let mut ret: Vec<(i64, i64)> = deque.into_iter().take(k - 1).map(|pair| (pair.0, pair.1)).collect();
183
184    ret.sort_unstable();
185    ret
186}
187
188#[cfg(test)]
189mod test_convex_hull {
190    use crate::geometry::convex_hull;
191
192    #[test]
193    fn it_works() {
194        let ps = vec![(0, 0), (2, 2), (3, 1), (1, 4), (4, 4)];
195        let hull = convex_hull(ps);
196        assert_eq!(hull, vec![(0, 0), (1, 4), (3, 1), (4, 4)]);
197
198        let ps = vec![(0, 0), (2, 2), (4, 4)];
199        let hull = convex_hull(ps);
200        assert_eq!(hull, vec![(0, 0), (4, 4)]);
201
202        let ps = vec![(0, 0), (0, 1), (0, 2), (1, 1)];
203        let hull = convex_hull(ps);
204        assert_eq!(hull, vec![(0, 0), (0, 2), (1, 1)]);
205    }
206}
algorithm_rs/geometry.rs

algorithm_rs/
geometry.rs
