aoclib_rs/
point.rs

1use std::{
2    f64::consts::{FRAC_PI_2, PI},
3    fmt::Debug,
4    hash::Hash,
5    iter::zip,
6    ops::{DivAssign, Rem, Sub},
7};
8
9use crate::abs;
10
11use num_traits::{NumCast, Zero};
12
13/// A point that can be initialized with an array of the appropriate size.
14pub trait PointFromArray<T, const N: usize> {
15    /// Initializes a point from an array.
16    fn from_array(vals: [T; N]) -> Self;
17}
18
19/// A point capable of computing the straight-line distance between itself and another point of the
20/// same type.
21pub trait PointDist {
22    /// Computes the straight-line distance between `self` and `other`.
23    fn dist(&self, other: &Self) -> f64;
24}
25
26/// A point capable of computing the Manhattan distance between itself and another point of the
27/// same type.
28pub trait PointManhattan<T> {
29    /// Computes the Manhattan distance between `self` and `other`.
30    fn manhattan(&self, other: &Self) -> T;
31}
32
33/// 2-dimensional point.
34/// For full functionality for floats, try the `ordered_float` crate
35#[derive(Clone, Debug, PartialEq, Eq, Hash)]
36pub struct Point2d<T: Copy>(PointNd<T, 2>);
37
38impl<T: Copy> Point2d<T> {
39    pub fn new(x: T, y: T) -> Self {
40        Self(PointNd { vals: [x, y] })
41    }
42
43    pub fn x(&self) -> T {
44        self.0.vals[0]
45    }
46
47    pub fn y(&self) -> T {
48        self.0.vals[1]
49    }
50}
51
52impl<T> Point2d<T>
53where
54    T: Copy + DivAssign + PartialOrd + Rem<Output = T> + Sub<Output = T> + Zero,
55{
56    /// Returns the slope between `self` and `other`. Can return an error if the x values of both
57    /// points are the same (to avoid dividing by zero).
58    pub fn get_slope(&self, other: &Self) -> anyhow::Result<Slope<T>> {
59        Slope::from_points_2d(self, other)
60    }
61}
62
63impl<T> Point2d<T>
64where
65    T: Copy + NumCast + PartialOrd + Sub<Output = T> + Zero,
66{
67    /// Returns the angle (from straight up, going clockwise) between `self` and `other` in
68    /// radians. Can return an error if both points are the same.
69    ///
70    /// ```
71    /// use aoclib_rs::point::Point2d;
72    /// assert_eq!(
73    ///     Point2d::new(0, 0).get_angle(&Point2d::new(1, 0)).unwrap(),
74    ///     std::f64::consts::FRAC_PI_2
75    /// );
76    /// ```
77    pub fn get_angle(&self, other: &Self) -> anyhow::Result<f64> {
78        get_angle(other.x() - self.x(), other.y() - self.y())
79    }
80}
81
82impl<T: Copy> PointFromArray<T, 2> for Point2d<T> {
83    fn from_array(vals: [T; 2]) -> Self {
84        Self(PointNd { vals })
85    }
86}
87
88impl<T> PointDist for Point2d<T>
89where
90    T: Copy + NumCast,
91{
92    /// Computes the straight-line distance between `self` and `other`.
93    ///
94    /// ```
95    /// use aoclib_rs::point::{Point2d, PointDist};
96    /// assert_eq!(Point2d::new(1, 1).dist(&Point2d::new(4, 5)), 5.0);
97    /// ```
98    fn dist(&self, other: &Self) -> f64 {
99        self.0.dist(&other.0)
100    }
101}
102
103impl<T> PointManhattan<T> for Point2d<T>
104where
105    T: Copy + PartialOrd + Sub<Output = T> + Zero,
106{
107    /// Computes the Manhattan distance between `self` and `other`.
108    ///
109    /// ```
110    /// use aoclib_rs::point::{Point2d, PointManhattan};
111    /// assert_eq!(Point2d::new(1, 1).manhattan(&Point2d::new(4, 5)), 7);
112    /// ```
113    fn manhattan(&self, other: &Self) -> T {
114        self.0.manhattan(&other.0)
115    }
116}
117
118/// 3-dimensional point.
119/// For full functionality for floats, try the `ordered_float` crate
120#[derive(Clone, Debug, PartialEq, Eq, Hash)]
121pub struct Point3d<T: Copy>(PointNd<T, 3>);
122
123impl<T: Copy> Point3d<T> {
124    pub fn new(x: T, y: T, z: T) -> Self {
125        Self(PointNd { vals: [x, y, z] })
126    }
127
128    pub fn x(&self) -> T {
129        self.0.vals[0]
130    }
131
132    pub fn y(&self) -> T {
133        self.0.vals[1]
134    }
135
136    pub fn z(&self) -> T {
137        self.0.vals[2]
138    }
139}
140
141impl<T: Copy> PointFromArray<T, 3> for Point3d<T> {
142    fn from_array(vals: [T; 3]) -> Self {
143        Self(PointNd { vals })
144    }
145}
146
147impl<T> PointDist for Point3d<T>
148where
149    T: Copy + NumCast,
150{
151    /// Computes the straight-line distance between `self` and `other`.
152    ///
153    /// ```
154    /// use aoclib_rs::point::{Point3d, PointDist};
155    /// assert_eq!(Point3d::new(2, 4, 3).dist(&Point3d::new(6, 9, 23)), 21.0);
156    /// ```
157    fn dist(&self, other: &Self) -> f64 {
158        self.0.dist(&other.0)
159    }
160}
161
162impl<T> PointManhattan<T> for Point3d<T>
163where
164    T: Copy + PartialOrd + Sub<Output = T> + Zero,
165{
166    /// Computes the Manhattan distance between `self` and `other`.
167    ///
168    /// ```
169    /// use aoclib_rs::point::{Point3d, PointManhattan};
170    /// assert_eq!(Point3d::new(2, 4, 3).manhattan(&Point3d::new(6, 9, 23)), 29);
171    /// ```
172    fn manhattan(&self, other: &Self) -> T {
173        self.0.manhattan(&other.0)
174    }
175}
176
177/// N-dimensional point.
178/// For full functionality for floats, try the `ordered_float` crate
179#[derive(Clone, Debug, PartialEq, Eq, Hash)]
180pub struct PointNd<T: Copy, const N: usize> {
181    vals: [T; N],
182}
183
184impl<T: Copy, const N: usize> PointNd<T, N> {
185    pub fn new(vals: [T; N]) -> Self {
186        Self { vals }
187    }
188
189    pub fn n(&self, i: usize) -> T {
190        self.vals[i]
191    }
192}
193
194impl<T: Copy, const N: usize> PointFromArray<T, N> for PointNd<T, N> {
195    fn from_array(vals: [T; N]) -> Self {
196        Self::new(vals)
197    }
198}
199
200impl<T, const N: usize> PointDist for PointNd<T, N>
201where
202    T: Copy + NumCast,
203{
204    /// Computes the straight-line distance between `self` and `other`.
205    ///
206    /// ```
207    /// use aoclib_rs::point::{PointNd, PointDist};
208    /// assert_eq!(PointNd::new([6, 8, 2, 9]).dist(&PointNd::new([8, 12, 5, 23])), 15.0);
209    /// ```
210    fn dist(&self, other: &Self) -> f64 {
211        zip(self.vals.iter(), other.vals.iter())
212            .fold(0.0, |acc, (&s, &o)| {
213                let v_f64: f64 = num_traits::cast(s).unwrap();
214                let other_v_f64: f64 = num_traits::cast(o).unwrap();
215                acc + (v_f64 - other_v_f64).powi(2)
216            })
217            .sqrt()
218    }
219}
220
221impl<T, const N: usize> PointManhattan<T> for PointNd<T, N>
222where
223    T: Copy + PartialOrd + Sub<Output = T> + Zero,
224{
225    /// Computes the Manhattan distance between `self` and `other`.
226    ///
227    /// ```
228    /// use aoclib_rs::point::{PointNd, PointManhattan};
229    /// assert_eq!(PointNd::new([6, 8, 2, 9]).manhattan(&PointNd::new([8, 12, 5, 23])), 23);
230    /// ```
231    fn manhattan(&self, other: &Self) -> T {
232        zip(self.vals.iter(), other.vals.iter()).fold(T::zero(), |acc, (&s, &o)| acc + abs(s - o))
233    }
234}
235
236/// A simplified slope between two integer points.
237#[derive(PartialEq, Eq, Hash, Copy, Clone, Debug)]
238pub struct Slope<T>
239where
240    T: Copy + DivAssign + PartialOrd + Rem<Output = T> + Sub<Output = T> + Zero,
241{
242    horizontal: T,
243    vertical: T,
244}
245
246impl<T> Slope<T>
247where
248    T: Copy + DivAssign + PartialOrd + Rem<Output = T> + Sub<Output = T> + Zero,
249{
250    /// Can return an error if `horizontal` and `vertical` are both `0`.
251    ///
252    /// ```
253    /// let slope = aoclib_rs::point::Slope::new(2, 4).unwrap();
254    /// assert_eq!(slope.horizontal(), 1);
255    /// assert_eq!(slope.vertical(), 2);
256    /// ```
257    pub fn new(horizontal: T, vertical: T) -> anyhow::Result<Self> {
258        let mut s = Self {
259            horizontal,
260            vertical,
261        };
262        s.simplify()?;
263        Ok(s)
264    }
265
266    /// Can return an error if both points are the same.
267    ///
268    /// ```
269    /// use aoclib_rs::point::{Point2d, Slope};
270    /// let slope = Slope::from_points_2d(&Point2d::new(0, 0), &Point2d::new(2, 4)).unwrap();
271    /// assert_eq!(slope.horizontal(), 1);
272    /// assert_eq!(slope.vertical(), 2);
273    /// ```
274    pub fn from_points_2d(pov: &Point2d<T>, other: &Point2d<T>) -> anyhow::Result<Self> {
275        Self::new(other.x() - pov.x(), other.y() - pov.y())
276    }
277
278    pub fn horizontal(&self) -> T {
279        self.horizontal
280    }
281
282    pub fn vertical(&self) -> T {
283        self.vertical
284    }
285
286    /// Reduces the numerator and denominator of the slope by dividing them by the GCD.
287    fn simplify(&mut self) -> anyhow::Result<()> {
288        let gcd = crate::gcd(abs(self.horizontal), abs(self.vertical));
289        if gcd == T::zero() {
290            anyhow::bail!("gcd == 0 - avoiding divide-by-zero");
291        }
292        self.horizontal /= gcd;
293        self.vertical /= gcd;
294        Ok(())
295    }
296}
297
298impl<T> Slope<T>
299where
300    T: Copy + DivAssign + NumCast + PartialOrd + Rem<Output = T> + Sub<Output = T> + Zero,
301{
302    /// Returns the angle (from straight up, going clockwise) of the slope in radians.
303    ///
304    /// ```
305    /// use aoclib_rs::point::Slope;
306    /// assert_eq!(Slope::new(1, 0).unwrap().get_angle(), std::f64::consts::FRAC_PI_2);
307    /// ```
308    pub fn get_angle(&self) -> f64 {
309        // Should be impossible for get_angle() to fail since it would already have failed in
310        // simplify().
311        get_angle(self.horizontal, self.vertical).unwrap()
312    }
313}
314
315/// Returns the angle (from straight up, going clockwise) represented by this slope in radians.
316///
317/// ```
318/// assert_eq!(aoclib_rs::point::get_angle(1, 0).unwrap(), std::f64::consts::FRAC_PI_2);
319/// ```
320pub fn get_angle<T>(horizontal: T, vertical: T) -> anyhow::Result<f64>
321where
322    T: Copy + NumCast + PartialOrd + Zero,
323{
324    if horizontal == T::zero() && vertical == T::zero() {
325        anyhow::bail!("0 slope");
326    }
327
328    if horizontal == T::zero() {
329        // up
330        if vertical < T::zero() {
331            return Ok(0.0);
332        }
333
334        // down
335        return Ok(PI);
336    }
337
338    if vertical == T::zero() {
339        // right
340        if horizontal > T::zero() {
341            return Ok(FRAC_PI_2);
342        }
343
344        // left
345        return Ok(PI + FRAC_PI_2);
346    }
347
348    let horizontal_as_f64: f64 = num_traits::cast(horizontal).unwrap();
349    let vertical_as_f64: f64 = num_traits::cast(vertical).unwrap();
350
351    if horizontal > T::zero() {
352        // top-right
353        if vertical < T::zero() {
354            return Ok((horizontal_as_f64 / -vertical_as_f64).atan());
355        }
356
357        // bottom-right
358        return Ok((vertical_as_f64 / horizontal_as_f64).atan() + FRAC_PI_2);
359    }
360
361    // bottom-left
362    if vertical > T::zero() {
363        return Ok((-horizontal_as_f64 / vertical_as_f64).atan() + PI);
364    }
365
366    // top-left
367    Ok((-vertical_as_f64 / -horizontal_as_f64).atan() + PI + FRAC_PI_2)
368}
369
370#[cfg(test)]
371mod tests {
372    use super::*;
373
374    use std::f64::consts::FRAC_PI_4;
375
376    fn get_angle_good_helper<T>(func: fn(x: T, y: T) -> f64)
377    where
378        T: NumCast,
379    {
380        let testcases = [
381            ((0, -1), 0.0),
382            ((1, -1), FRAC_PI_4),
383            ((1, 0), FRAC_PI_2),
384            ((1, 1), FRAC_PI_2 + FRAC_PI_4),
385            ((0, 1), PI),
386            ((-1, 1), PI + FRAC_PI_4),
387            ((-1, 0), PI + FRAC_PI_2),
388            ((-1, -1), PI + FRAC_PI_2 + FRAC_PI_4),
389        ];
390        for ((x, y), want) in testcases {
391            let x_as_t: T = num_traits::cast(x).unwrap();
392            let y_as_t: T = num_traits::cast(y).unwrap();
393            assert_eq!(func(x_as_t, y_as_t), want);
394        }
395    }
396
397    #[test]
398    fn test_point2d_get_slope_good() {
399        let slope = Point2d::new(1, 1).get_slope(&Point2d::new(1, 2)).unwrap();
400        assert_eq!(slope.horizontal(), 0);
401        assert_eq!(slope.vertical(), 1);
402    }
403
404    #[test]
405    fn test_point2d_get_slope_same_point() {
406        assert!(Point2d::new(1, 1).get_slope(&Point2d::new(1, 1)).is_err());
407    }
408
409    #[test]
410    fn test_point2d_get_angle_good() {
411        get_angle_good_helper(|x: i64, y: i64| {
412            Point2d::new(0, 0).get_angle(&Point2d::new(x, y)).unwrap()
413        });
414        get_angle_good_helper(|x: f64, y: f64| {
415            Point2d::new(0.0, 0.0)
416                .get_angle(&Point2d::new(x, y))
417                .unwrap()
418        });
419    }
420
421    #[test]
422    fn test_point2d_get_angle_same_point() {
423        assert!(Point2d::new(1, 1).get_angle(&Point2d::new(1, 1)).is_err());
424    }
425
426    #[test]
427    fn test_slope_new_zero() {
428        assert!(Slope::new(0, 0).is_err());
429    }
430
431    #[test]
432    fn test_slope_from_points_2d_same_point() {
433        assert!(Slope::from_points_2d(&Point2d::new(1, 1), &Point2d::new(1, 1)).is_err());
434    }
435
436    #[test]
437    fn test_slope_get_angle_good() {
438        get_angle_good_helper(|x: i64, y: i64| Slope::new(x, y).unwrap().get_angle());
439    }
440
441    #[test]
442    fn test_get_angle_good() {
443        get_angle_good_helper(|x: i64, y: i64| get_angle(x, y).unwrap());
444        get_angle_good_helper(|x: f64, y: f64| get_angle(x, y).unwrap());
445    }
446
447    #[test]
448    fn test_get_angle_zero() {
449        assert!(get_angle(0, 0).is_err());
450    }
451}
aoclib_rs/point.rs

aoclib_rs/
point.rs
