rgeometry/
orientation.rs

1use std::cmp::Ordering;
2
3use crate::data::Vector;
4use crate::PolygonScalar;
5
6#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Copy, Clone)]
7pub enum Orientation {
8  CounterClockWise,
9  ClockWise,
10  CoLinear,
11}
12use Orientation::*;
13
14#[derive(PartialEq, Eq, PartialOrd, Ord, Debug, Copy, Clone)]
15pub enum SoS {
16  CounterClockWise,
17  ClockWise,
18}
19
20// let slope1 = (2^q - 2^r) * (p - q);
21// let slope2 = (2^q - 2^p) * (r - q);
22
23impl Orientation {
24  /// Determine the direction you have to turn if you walk from `p1`
25  /// to `p2` to `p3`.
26  ///
27  /// For fixed-precision types (i8,i16,i32,i64,etc), this function is
28  /// guaranteed to work for any input and never cause any arithmetic overflows.
29  ///
30  /// # Polymorphism
31  ///
32  /// This function works with both [Points](crate::data::Point) and [Vectors](Vector). You should prefer to
33  /// use [Point::orient](crate::data::Point::orient) when possible.
34  ///
35  /// # Examples
36  ///
37  /// ```rust
38  /// # use rgeometry::data::Point;
39  /// # use rgeometry::Orientation;
40  /// let p1 = Point::new([ 0, 0 ]);
41  /// let p2 = Point::new([ 0, 1 ]); // One unit above p1.
42  /// // (0,0) -> (0,1) -> (0,2) == Orientation::CoLinear
43  /// assert!(Orientation::new(&p1, &p2, &Point::new([ 0, 2 ])).is_colinear());
44  /// // (0,0) -> (0,1) -> (-1,2) == Orientation::CounterClockWise
45  /// assert!(Orientation::new(&p1, &p2, &Point::new([ -1, 2 ])).is_ccw());
46  /// // (0,0) -> (0,1) -> (1,2) == Orientation::ClockWise
47  /// assert!(Orientation::new(&p1, &p2, &Point::new([ 1, 2 ])).is_cw());
48  /// ```
49  ///
50  pub fn new<T>(p1: &[T; 2], p2: &[T; 2], p3: &[T; 2]) -> Orientation
51  where
52    T: PolygonScalar,
53  {
54    // raw_arr_turn(p, q, r)
55    match T::cmp_slope(p1, p2, p3) {
56      Ordering::Less => Orientation::ClockWise,
57      Ordering::Equal => Orientation::CoLinear,
58      Ordering::Greater => Orientation::CounterClockWise,
59    }
60  }
61
62  /// Locate `p2` in relation to the line determined by the point `p1` and the direction
63  /// vector.
64  ///
65  /// For fixed-precision types (i8,i16,i32,i64,etc), this function is
66  /// guaranteed to work for any input and never cause any arithmetic overflows.
67  ///
68  /// This function is identical to [`Orientation::new`]`(p1, p1+v, p2)` but will never
69  /// cause arithmetic overflows even if `p+v` would overflow.
70  ///
71  /// # Examples
72  ///
73  /// ```rust
74  /// # use rgeometry::data::{Vector,Point};
75  /// # use rgeometry::Orientation;
76  /// let v = Vector([ 1, 1 ]); // Vector pointing to the top-right corner.
77  /// let p1 = Point::new([ 5, 5 ]);
78  /// assert!(Orientation::along_vector(&p1, &v, &Point::new([ 6, 6 ])).is_colinear());
79  /// assert!(Orientation::along_vector(&p1, &v, &Point::new([ 7, 8 ])).is_ccw());
80  /// assert!(Orientation::along_vector(&p1, &v, &Point::new([ 8, 7 ])).is_cw());
81  /// ```
82  pub fn along_vector<T>(p1: &[T; 2], vector: &Vector<T, 2>, p2: &[T; 2]) -> Orientation
83  where
84    T: PolygonScalar,
85  {
86    match T::cmp_vector_slope(&vector.0, p1, p2) {
87      Ordering::Less => Orientation::ClockWise,
88      Ordering::Equal => Orientation::CoLinear,
89      Ordering::Greater => Orientation::CounterClockWise,
90    }
91  }
92
93  pub fn along_perp_vector<T>(p1: &[T; 2], vector: &Vector<T, 2>, p2: &[T; 2]) -> Orientation
94  where
95    T: PolygonScalar,
96  {
97    match T::cmp_perp_vector_slope(&vector.0, p1, p2) {
98      Ordering::Less => Orientation::ClockWise,
99      Ordering::Equal => Orientation::CoLinear,
100      Ordering::Greater => Orientation::CounterClockWise,
101    }
102  }
103
104  pub fn is_colinear(self) -> bool {
105    matches!(self, Orientation::CoLinear)
106  }
107
108  pub fn is_ccw(self) -> bool {
109    matches!(self, Orientation::CounterClockWise)
110  }
111
112  pub fn is_cw(self) -> bool {
113    matches!(self, Orientation::ClockWise)
114  }
115
116  #[must_use]
117  pub fn then(self, other: Orientation) -> Orientation {
118    match self {
119      Orientation::CoLinear => other,
120      _ => self,
121    }
122  }
123
124  pub fn break_ties(self, a: u32, b: u32, c: u32) -> SoS {
125    match self {
126      CounterClockWise => SoS::CounterClockWise,
127      ClockWise => SoS::ClockWise,
128      CoLinear => SoS::new(a, b, c),
129    }
130  }
131
132  pub fn sos(self, other: SoS) -> SoS {
133    match self {
134      CounterClockWise => SoS::CounterClockWise,
135      ClockWise => SoS::ClockWise,
136      CoLinear => other,
137    }
138  }
139
140  // pub fn around_origin<T>(q: &[T; 2], r: &[T; 2]) -> Orientation
141  // where
142  //   T: Ord + Mul<Output = T> + Clone + Extended,
143  // {
144  //   raw_arr_turn_origin(q, r)
145  // }
146
147  #[must_use]
148  pub fn reverse(self) -> Orientation {
149    match self {
150      Orientation::CounterClockWise => Orientation::ClockWise,
151      Orientation::ClockWise => Orientation::CounterClockWise,
152      Orientation::CoLinear => Orientation::CoLinear,
153    }
154  }
155
156  pub fn ccw_cmp_around_with<T>(
157    vector: &Vector<T, 2>,
158    p1: &[T; 2],
159    p2: &[T; 2],
160    p3: &[T; 2],
161  ) -> Ordering
162  where
163    T: PolygonScalar,
164  {
165    let aq = Orientation::along_vector(p1, vector, p2);
166    let ar = Orientation::along_vector(p1, vector, p3);
167    // let on_zero = |d: &[T; 2]| {
168    //   !((d[0] < p[0] && z[0].is_positive())
169    //     || (d[1] < p[1] && z[1].is_positive())
170    //     || (d[0] > p[0] && z[0].is_negative())
171    //     || (d[1] > p[1] && z[1].is_negative()))
172    // };
173    let on_zero = |d: &[T; 2]| match Orientation::along_perp_vector(p1, vector, d) {
174      CounterClockWise => false,
175      ClockWise => true,
176      CoLinear => true,
177    };
178    let cmp = || match Orientation::new(p1, p2, p3) {
179      CounterClockWise => Ordering::Less,
180      ClockWise => Ordering::Greater,
181      CoLinear => Ordering::Equal,
182    };
183    match (aq, ar) {
184      // Easy cases: Q and R are on either side of the line p->z:
185      (CounterClockWise, ClockWise) => Ordering::Less,
186      (ClockWise, CounterClockWise) => Ordering::Greater,
187      // A CoLinear point may be in front of p->z (0 degree angle) or behind
188      // it (180 degree angle). If the other point is clockwise, it must have an
189      // angle greater than 180 degrees and must therefore be greater than the
190      // colinear point.
191      (CoLinear, ClockWise) => Ordering::Less,
192      (ClockWise, CoLinear) => Ordering::Greater,
193
194      // if Q and R are on the same side of P->Z then the most clockwise point
195      // will have the smallest angle.
196      (CounterClockWise, CounterClockWise) => cmp(),
197      (ClockWise, ClockWise) => cmp(),
198
199      // CoLinear points have an angle of either 0 degrees or 180 degrees. on_zero
200      // can distinguish these two cases:
201      //    on_zero(p) => 0 degrees.
202      //   !on_zero(p) => 180 degrees.
203      (CounterClockWise, CoLinear) => {
204        if on_zero(p3) {
205          Ordering::Greater // angle(r) = 0 & 0 < angle(q) < 180. Thus: Q > R
206        } else {
207          Ordering::Less // angle(r) = 180 & 0 < angle(q) < 180. Thus: Q < R
208        }
209      }
210      (CoLinear, CounterClockWise) => {
211        if on_zero(p2) {
212          Ordering::Less
213        } else {
214          Ordering::Greater
215        }
216      }
217      (CoLinear, CoLinear) => match (on_zero(p2), on_zero(p3)) {
218        (true, true) => Ordering::Equal,
219        (false, false) => Ordering::Equal,
220        (true, false) => Ordering::Less,
221        (false, true) => Ordering::Greater,
222      },
223    }
224  }
225}
226
227// https://arxiv.org/abs/math/9410209
228// Simulation of Simplicity.
229// Break ties (ie colinear orientations) in an arbitrary but consistent way.
230impl SoS {
231  // p: Point::new([a, 2^a])
232  // q: Point::new([b, 2^b])
233  // r: Point::new([c, 2^c])
234  // new(a,b,c) == Orientation::new(p, q, r)
235  pub fn new(a: u32, b: u32, c: u32) -> SoS {
236    assert_ne!(a, b);
237    assert_ne!(b, c);
238    assert_ne!(c, a);
239
240    // Combinations:
241    //               a<b a<c c<b
242    // b a c => CW    _   X   _
243    // c b a => CW    _   _   X
244    // a c b => CW    X   X   X
245    // b c a => CCW   _   _   _
246    // c a b => CCW   X   _   X
247    // a b c => CCW   X   X   _
248
249    let ab = a < b;
250    let ac = a < c;
251    let cb = c < b;
252    if ab ^ ac ^ cb {
253      SoS::ClockWise
254    } else {
255      SoS::CounterClockWise
256    }
257    // if a < b {
258    //   if a < c && c < b {
259    //     SoS::ClockWise // a c b
260    //   } else {
261    //     SoS::CounterClockWise // a b c, c a b
262    //   }
263    // } else if b < c && c < a {
264    //   SoS::CounterClockWise // b c a
265    // } else {
266    //   SoS::ClockWise // b a c, c b a
267    // }
268  }
269
270  pub fn orient(self) -> Orientation {
271    match self {
272      SoS::CounterClockWise => Orientation::CounterClockWise,
273      SoS::ClockWise => Orientation::ClockWise,
274    }
275  }
276
277  #[must_use]
278  pub fn reverse(self) -> SoS {
279    match self {
280      SoS::CounterClockWise => SoS::ClockWise,
281      SoS::ClockWise => SoS::CounterClockWise,
282    }
283  }
284}
285
286#[cfg(test)]
287#[cfg(not(tarpaulin_include))]
288mod tests {
289  use super::*;
290
291  use crate::data::Point;
292  use num::BigInt;
293  use proptest::prelude::*;
294  use test_strategy::proptest;
295
296  #[test]
297  fn orientation_limit_1() {
298    PolygonScalar::cmp_slope(
299      &[i8::MAX, i8::MAX],
300      &[i8::MIN, i8::MIN],
301      &[i8::MIN, i8::MIN],
302    );
303  }
304
305  #[test]
306  fn cmp_slope_1() {
307    assert_eq!(
308      PolygonScalar::cmp_slope(&[0i8, 0], &[1, 1], &[2, 2],),
309      Ordering::Equal
310    );
311  }
312
313  #[test]
314  fn cmp_slope_2() {
315    assert_eq!(
316      Orientation::new(&[0i8, 0], &[0, 1], &[2, 2],),
317      Orientation::ClockWise
318    );
319  }
320
321  #[test]
322  fn orientation_limit_2() {
323    let options = &[i8::MIN, i8::MAX, 0, -10, 10];
324    for [a, b, c, d, e, f] in crate::utils::permutations([options; 6]) {
325      PolygonScalar::cmp_slope(&[a, b], &[c, d], &[e, f]);
326    }
327  }
328
329  #[test]
330  fn cmp_around_1() {
331    use num_bigint::*;
332    let pt1 = [BigInt::from(0), BigInt::from(0)];
333    let pt2 = [BigInt::from(-1), BigInt::from(1)];
334    // let pt2 = [BigInt::from(-717193444810564826_i64), BigInt::from(1)];
335    let vector = Vector([BigInt::from(1), BigInt::from(0)]);
336
337    assert_eq!(
338      Orientation::ccw_cmp_around_with(&vector, &pt1, &pt2, &pt1),
339      Ordering::Greater
340    );
341  }
342
343  #[test]
344  fn sos_unit1() {
345    assert_eq!(SoS::new(0, 1, 2), SoS::CounterClockWise)
346  }
347
348  #[test]
349  #[should_panic]
350  fn sos_unit2() {
351    SoS::new(0, 0, 1);
352  }
353
354  #[test]
355  fn sos_unit3() {
356    assert_eq!(SoS::new(99, 0, 1), SoS::CounterClockWise);
357  }
358
359  #[proptest]
360  fn sos_eq_prop(a: u8, b: u8, c: u8) {
361    if a != b && b != c && c != a {
362      let (a, b, c) = (a as u32, b as u32, c as u32);
363      let one = &BigInt::from(1);
364      let big_a = BigInt::from(a);
365      let big_b = BigInt::from(b);
366      let big_c = BigInt::from(c);
367      let p = Point::new([big_a, one << a]);
368      let q = Point::new([big_b, one << b]);
369      let r = Point::new([big_c, one << c]);
370      prop_assert_eq!(SoS::new(a, b, c).orient(), Orientation::new(&p, &q, &r));
371    }
372  }
373
374  #[proptest]
375  fn sos_rev_prop(a: u32, b: u32, c: u32) {
376    if a != b && b != c && c != a {
377      prop_assert_eq!(SoS::new(a, b, c), SoS::new(c, b, a).reverse());
378      prop_assert_eq!(SoS::new(a, b, c), SoS::new(a, c, b).reverse());
379      prop_assert_eq!(SoS::new(a, b, c), SoS::new(b, a, c).reverse());
380      prop_assert_eq!(SoS::new(a, b, c), SoS::new(b, c, a));
381    }
382  }
383}
rgeometry/orientation.rs

rgeometry/
orientation.rs
