rgeometry/data/
polygon.rs

1// use claim::debug_assert_ok;
2use num_traits::*;
3use ordered_float::OrderedFloat;
4use std::cmp::Ordering;
5use std::iter::Sum;
6use std::ops::Bound::*;
7use std::ops::*;
8
9use crate::data::{
10  DirectedEdge, HalfLineSoS, IHalfLineLineSegmentSoS::*, Point, PointLocation, TriangleView, Vector,
11};
12use crate::intersection::*;
13use crate::{Error, Orientation, PolygonScalar, TotalOrd};
14
15mod iter;
16pub use iter::*;
17
18mod convex;
19pub use convex::*;
20
21use super::Transform;
22
23#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
24pub struct PositionId(usize);
25
26impl From<PositionId> for usize {
27  fn from(pid: PositionId) -> usize {
28    pid.0
29  }
30}
31
32#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
33pub struct RingId(usize);
34
35impl From<RingId> for usize {
36  fn from(rid: RingId) -> usize {
37    rid.0
38  }
39}
40
41#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
42pub struct PointId(usize);
43
44impl From<PointId> for usize {
45  fn from(pid: PointId) -> usize {
46    pid.0
47  }
48}
49
50impl std::fmt::Debug for PointId {
51  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
52    f.write_fmt(format_args!("{}", self.0))
53  }
54}
55
56impl PointId {
57  pub const INVALID: PointId = PointId(usize::MAX);
58  pub fn usize(self) -> usize {
59    self.0
60  }
61}
62
63#[non_exhaustive]
64#[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
65pub struct IndexEdge {
66  pub min: PointId,
67  pub max: PointId,
68}
69
70impl std::fmt::Debug for IndexEdge {
71  fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> Result<(), std::fmt::Error> {
72    f.debug_tuple("IndexEdge")
73      .field(&self.min)
74      .field(&self.max)
75      .finish()
76  }
77}
78
79// Undirected Indexed Edge
80impl IndexEdge {
81  pub fn new(a: PointId, b: PointId) -> IndexEdge {
82    IndexEdge {
83      min: std::cmp::min(a, b),
84      max: std::cmp::max(a, b),
85    }
86  }
87}
88
89impl From<DirectedIndexEdge> for IndexEdge {
90  fn from(directed: DirectedIndexEdge) -> IndexEdge {
91    IndexEdge::new(directed.src, directed.dst)
92  }
93}
94
95#[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
96pub struct DirectedIndexEdge {
97  pub src: PointId,
98  pub dst: PointId,
99}
100
101// A     C
102// B     D
103
104// A*D   C*B
105
106// DONE: intersections : &[impl Into<LineSegment>] -> impl Iterator<Item =(&LineSegment,&LineSegment, ILineSegment)>
107// cut_holes: Polygon -> PolygonSimple
108// cut_holes: Polygon -> Vec<PointId>
109// triangulate: Vec<Point<T,2>> + Vec<PointId> -> Vec<(PointId,PointId,PointId)>
110// triangulate: Polygon -> Vec<Polygon>
111// triangulate: Polygon -> Vec<(PointId, PointId, PointId)>
112
113#[derive(Debug, Clone, Hash)]
114pub struct Polygon<T> {
115  // Use points: Arc<Vec<Point<T, 2>>>, ?
116  // Key: PointId
117  pub(crate) points: Vec<Point<T>>,
118  // Key: PointId
119  pub(crate) ring_index: Vec<RingId>,
120  // Key: PointId
121  pub(crate) position_index: Vec<PositionId>,
122  // Ring 0 is boundary and ccw
123  // Ring n+1 is a hole and cw.
124  // Outer key: RingId
125  // Inner key: PositionId
126  pub(crate) rings: Vec<Vec<PointId>>,
127}
128
129impl<T> Polygon<T> {
130  /// $O(1)$
131  pub fn new_unchecked(vertices: Vec<Point<T, 2>>) -> Polygon<T>
132  where
133    T: PolygonScalar,
134  {
135    let len = vertices.len();
136    Polygon {
137      points: vertices,
138      ring_index: vec![RingId(0); len],
139      position_index: (0..len).map(PositionId).collect(),
140      rings: vec![(0..len).map(PointId).collect()],
141    }
142  }
143
144  /// $O(n^2)$
145  pub fn new(points: Vec<Point<T, 2>>) -> Result<Polygon<T>, Error>
146  where
147    T: PolygonScalar,
148  {
149    // Verify minimum length before calling 'ensure_ccw'.
150    if points.len() < 3 {
151      return Err(Error::InsufficientVertices);
152    }
153    let mut p = Self::new_unchecked(points);
154    p.ensure_ccw()?;
155    p.validate()?;
156    Ok(p)
157  }
158
159  // Validate that a polygon is simple.
160  // https://en.wikipedia.org/wiki/Simple_polygon
161  pub fn validate(&self) -> Result<(), Error>
162  where
163    T: PolygonScalar,
164  {
165    // Has no duplicate points.
166    let mut seen = std::collections::BTreeSet::new();
167    for pt in self.iter() {
168      if !seen.insert(pt) {
169        return Err(Error::DuplicatePoints);
170      }
171    }
172
173    self.validate_weakly()
174  }
175
176  pub fn validate_weakly(&self) -> Result<(), Error>
177  where
178    T: PolygonScalar,
179  {
180    // Rings is never allowed to be empty under any circumstances, even when
181    // using 'Polygon::unchecked_new'.
182    assert!(!self.rings.is_empty());
183
184    // Has at least three points.
185    if self.rings[0].len() < 3 {
186      return Err(Error::InsufficientVertices);
187    }
188    // Is counter-clockwise
189    if self.orientation() != Orientation::CounterClockWise {
190      return Err(Error::ClockWiseViolation);
191    }
192    // Has no self intersections.
193    // XXX: Hm, allow overlapping (but not crossing) edges in the weakly check?
194    let edges: Vec<DirectedEdge<'_, T, 2>> = self.iter_boundary_edges().collect();
195    let mut isects = crate::algorithms::segment_intersections(&edges);
196    if isects.next().is_some() {
197      return Err(Error::SelfIntersections);
198    }
199    Ok(())
200  }
201
202  pub fn locate(&self, origin: &Point<T, 2>) -> PointLocation
203  where
204    T: PolygonScalar,
205  {
206    // FIXME: Support polygons with holes.
207    assert_eq!(
208      self.rings.len(),
209      1,
210      "FIXME: Polygon::locate should support polygons with holes."
211    );
212
213    let direction = Vector::unit_right();
214    let ray = HalfLineSoS::new_directed(origin, &direction);
215    let mut intersections = 0;
216    for edge in self.iter_boundary_edges() {
217      if edge.contains(origin) {
218        return PointLocation::OnBoundary;
219      }
220      if let Some(Crossing(lean)) = ray.intersect(edge) {
221        // Only count crossing that aren't leaning to the right.
222        if !lean.is_cw() {
223          intersections += 1;
224        }
225      }
226    }
227    if intersections % 2 == 0 {
228      PointLocation::Outside
229    } else {
230      PointLocation::Inside
231    }
232  }
233
234  pub fn triangulate(
235    &self,
236  ) -> impl Iterator<Item = (Cursor<'_, T>, Cursor<'_, T>, Cursor<'_, T>)> + '_
237  where
238    T: PolygonScalar,
239  {
240    crate::algorithms::triangulation::earclip::earclip(self)
241      .map(move |(p1, p2, p3)| (self.cursor(p1), self.cursor(p2), self.cursor(p3)))
242  }
243
244  //
245  // # Panics
246  //
247  // May panic for bounded types (i8, isize, etc). Maybe produce inaccurate results for
248  // floating point types (f32, f64).
249  pub fn centroid(&self) -> Point<T>
250  where
251    T: PolygonScalar,
252  {
253    let xs: Vector<T, 2> = self
254      .iter_boundary_edges()
255      .map(|edge| {
256        let p = edge.src.as_vec();
257        let q = edge.dst.as_vec();
258        (p + q) * (p.0[0].clone() * q.0[1].clone() - q.0[0].clone() * p.0[1].clone())
259      })
260      .sum();
261    let three = T::from_constant(3);
262    Point::from(xs / (three * self.signed_area_2x()))
263  }
264
265  pub fn bounding_box(&self) -> (Point<T>, Point<T>)
266  where
267    T: PolygonScalar,
268  {
269    assert!(!self.rings[0].is_empty());
270    let mut min_x = self.points[self.rings[0][0].usize()].x_coord().clone();
271    let mut max_x = self.points[self.rings[0][0].usize()].x_coord().clone();
272    let mut min_y = self.points[self.rings[0][0].usize()].y_coord().clone();
273    let mut max_y = self.points[self.rings[0][0].usize()].y_coord().clone();
274    for pt in self.iter_boundary() {
275      if pt.point().x_coord() < &min_x {
276        min_x = pt.point().x_coord().clone();
277      }
278      if pt.point().x_coord() > &max_x {
279        max_x = pt.point().x_coord().clone();
280      }
281      if pt.point().y_coord() < &min_y {
282        min_y = pt.point().y_coord().clone();
283      }
284      if pt.point().y_coord() > &max_y {
285        max_y = pt.point().y_coord().clone();
286      }
287    }
288    (Point::new([min_x, min_y]), Point::new([max_x, max_y]))
289  }
290
291  /// Computes the area of a polygon. If the polygon winds counter-clockwise,
292  /// the area will be a positive number. If the polygon winds clockwise, the area will
293  /// be negative.
294  ///
295  /// # Return type
296  ///
297  /// This function is polymorphic for the same reason as [`signed_area_2x`](Polygon::signed_area_2x).
298  ///
299  /// # Time complexity
300  ///
301  /// $O(n)$
302  ///
303  /// # Examples
304  /// ```rust
305  /// // The area of this polygon is 1/2 and won't fit in an `i32`
306  /// # use rgeometry::data::*;
307  /// # fn main() -> Result<(), rgeometry::Error> {
308  /// let p = Polygon::new(vec![
309  ///   Point::new([0, 0]),
310  ///   Point::new([1, 0]),
311  ///   Point::new([0, 1]),
312  ///  ])?;
313  /// assert_eq!(p.signed_area::<i32>(), 0);
314  /// # Ok(())
315  /// # }
316  /// ```
317  ///
318  /// ```rust
319  /// // The area of this polygon is 1/2 and will fit in a `Ratio<i32>`.
320  /// # use rgeometry::data::*;
321  /// # use num_rational::Ratio;
322  /// # fn main() -> Result<(), rgeometry::Error> {
323  /// let p = Polygon::new(vec![
324  ///   Point::new([0, 0]),
325  ///   Point::new([1, 0]),
326  ///   Point::new([0, 1]),
327  ///  ])?;
328  /// assert_eq!(p.signed_area::<Ratio<i32>>(), Ratio::from((1,2)));
329  /// # Ok(())
330  /// # }
331  /// ```
332  pub fn signed_area<F>(&self) -> F
333  where
334    T: PolygonScalar + Into<F>,
335    F: NumOps<F, F> + Sum + FromPrimitive,
336  {
337    self.signed_area_2x::<F>() / F::from_usize(2).unwrap()
338  }
339
340  /// Compute double the area of a polygon. If the polygon winds counter-clockwise,
341  /// the area will be a positive number. If the polygon winds clockwise, the area will
342  /// be negative.
343  ///
344  /// Why compute double the area? If you are using integer coordinates then the doubled
345  /// area will also be an integer value. Computing the exact requires a division which
346  /// may leave you with a non-integer result.
347  ///
348  /// # Return type
349  ///
350  /// Storing the area of a polygon may require more bits of precision than are used
351  /// for the coordinates. For example, if 32bit integers are used for point coordinates
352  /// then you might need 65 bits to store the area doubled. For this reason, the return
353  /// type is polymorphic and should be selected with care. If you are unsure which type
354  /// is appropriate, use [`BigInt`](num::BigInt) or [`BigRational`](num::BigRational).
355  ///
356  /// # Time complexity
357  ///
358  /// $O(n)$
359  ///
360  /// # Examples:
361  /// ```rust
362  /// // The area of this polygon is 1/2 and cannot fit in an `i32` variable
363  /// // so lets compute twice the area.
364  /// # use rgeometry::data::*;
365  /// # fn main() -> Result<(), rgeometry::Error> {
366  /// let p = Polygon::new(vec![
367  ///   Point::new([0, 0]),
368  ///   Point::new([1, 0]),
369  ///   Point::new([0, 1]),
370  ///  ])?;
371  /// assert_eq!(p.signed_area_2x::<i32>(), 1);
372  /// # Ok(())
373  /// # }
374  /// ```
375  ///
376  /// ```rust
377  /// // The area of a polygon may require more bits of precision than are
378  /// // used for the coordinates.
379  /// # use num::BigInt;
380  /// # use rgeometry::data::*;
381  /// # fn main() -> Result<(), rgeometry::Error> {
382  /// let p = Polygon::new(vec![
383  ///   Point::new([0, 0]),
384  ///   Point::new([i32::MAX, 0]),
385  ///   Point::new([0, i32::MAX]),
386  ///  ])?;
387  /// assert_eq!(p.signed_area_2x::<i64>(), 4611686014132420609_i64);
388  /// # Ok(())
389  /// # }
390  /// ```
391  pub fn signed_area_2x<F>(&self) -> F
392  where
393    T: PolygonScalar + Into<F>,
394    F: NumOps<F, F> + Sum,
395  {
396    self
397      .iter_boundary_edges()
398      .map(|edge| {
399        let p = edge.src;
400        let q = edge.dst;
401        p.array[0].clone().into() * q.array[1].clone().into()
402          - q.array[0].clone().into() * p.array[1].clone().into()
403      })
404      .sum()
405  }
406
407  pub fn orientation(&self) -> Orientation
408  where
409    T: PolygonScalar,
410  {
411    match self.iter_boundary().min_by(|a, b| a.point().cmp(b.point())) {
412      None => Orientation::CoLinear,
413      Some(cursor) => cursor.orientation(),
414    }
415  }
416
417  /// Access point of a given vertex.
418  /// # Time complexity
419  /// $O(1)$
420  pub fn point(&self, idx: PointId) -> &Point<T> {
421    &self.points[idx.0]
422  }
423
424  // FIXME: The PointId may not be valid. Return Option<Cursor>.
425  /// Access cursor of a given vertex.
426  /// # Time complexity
427  /// $O(1)$
428  pub fn cursor(&self, idx: PointId) -> Cursor<'_, T> {
429    let ring_id = self.ring_index[idx.0];
430    let position_id = self.position_index[idx.0];
431    Cursor {
432      polygon: self,
433      position: Position {
434        ring_id,
435        position_id,
436        size: self.rings[ring_id.0].len(),
437      },
438    }
439  }
440
441  pub fn boundary_slice(&self) -> &[PointId] {
442    &self.rings[0]
443  }
444
445  pub fn equals(&self, other: &Self) -> bool
446  where
447    T: PolygonScalar,
448  {
449    if self.boundary_slice().len() != other.boundary_slice().len() {
450      return false;
451    }
452    for pos in self.iter_boundary() {
453      let iter = CursorIter {
454        cursor_head: pos,
455        cursor_tail: pos.prev(),
456        exhausted: false,
457      };
458      if iter == other.iter_boundary() {
459        return true;
460      }
461    }
462    false
463  }
464
465  pub fn iter_boundary(&self) -> CursorIter<'_, T> {
466    let root_cursor = Cursor {
467      polygon: self,
468      position: Position {
469        ring_id: RingId(0),
470        position_id: PositionId(0),
471        size: self.rings[0].len(),
472      },
473    };
474    CursorIter {
475      cursor_head: root_cursor,
476      cursor_tail: root_cursor.prev(),
477      exhausted: false,
478    }
479  }
480
481  pub fn iter_boundary_edges(&self) -> EdgeIter<'_, T> {
482    EdgeIter {
483      iter: self.iter_boundary(),
484    }
485  }
486
487  #[must_use]
488  pub fn map_points<F>(mut self, f: F) -> Polygon<T>
489  where
490    T: Clone,
491    F: Fn(Point<T>) -> Point<T>,
492  {
493    for pt in self.iter_mut() {
494      *pt = f(pt.clone())
495    }
496    self
497  }
498
499  pub fn iter(&self) -> Iter<'_, T> {
500    Iter {
501      iter: self.points.iter(),
502    }
503  }
504
505  pub fn iter_mut(&mut self) -> IterMut<'_, T> {
506    IterMut {
507      points: self.points.iter_mut(),
508    }
509  }
510
511  pub fn map<U, F>(self, f: F) -> Polygon<U>
512  where
513    T: Clone,
514    U: Clone,
515    F: Fn(T) -> U + Clone,
516  {
517    let pts = self.points.into_iter().map(|p| p.map(f.clone())).collect();
518    Polygon {
519      points: pts,
520      ring_index: self.ring_index,
521      position_index: self.position_index,
522      rings: self.rings,
523    }
524  }
525
526  pub fn cast<U>(self) -> Polygon<U>
527  where
528    T: Clone + Into<U>,
529  {
530    let pts = self.points.into_iter().map(|p| p.cast()).collect();
531    Polygon {
532      points: pts,
533      ring_index: self.ring_index,
534      position_index: self.position_index,
535      rings: self.rings,
536    }
537  }
538
539  pub fn float(self) -> Polygon<OrderedFloat<f64>>
540  where
541    T: Clone + Into<f64>,
542  {
543    self.map(|v| OrderedFloat(v.into()))
544  }
545
546  // Reverse all points between p1 and p2, inclusive of p1 and p2.
547  // For example: p1, a, b, c, p2 =>
548  //              p2, c, b, a, p1
549  pub fn vertices_reverse(&mut self, mut pt1: Position, mut pt2: Position) {
550    loop {
551      self.swap_positions(pt1, pt2);
552      pt1.move_next();
553      if pt1 == pt2 {
554        break;
555      }
556      pt2.move_prev();
557      if pt1 == pt2 {
558        break;
559      }
560    }
561  }
562
563  // Move pt2 back until it is right in front of p1.
564  pub fn vertices_join(&mut self, pt1: Position, mut pt2: Position) {
565    while pt2.prev() != pt1 {
566      let prev = pt2.prev();
567      self.swap_positions(prev, pt2);
568      pt2.position_id = prev.position_id;
569    }
570  }
571
572  /// Panics if the edge isn't part of the polygon.
573  pub fn direct(&self, edge: IndexEdge) -> DirectedIndexEdge {
574    let min_cursor = self.cursor(edge.min);
575    let max_cursor = self.cursor(edge.max);
576    if min_cursor.next() == max_cursor {
577      DirectedIndexEdge {
578        src: edge.min,
579        dst: edge.max,
580      }
581    } else if max_cursor.next() == min_cursor {
582      DirectedIndexEdge {
583        src: edge.max,
584        dst: edge.min,
585      }
586    } else {
587      panic!("Edge isn't part of polygon: {:?}", edge)
588    }
589  }
590
591  pub fn ensure_ccw(&mut self) -> Result<(), Error>
592  where
593    T: PolygonScalar,
594  {
595    match self.orientation() {
596      Orientation::CounterClockWise => Ok(()),
597      Orientation::CoLinear => Err(Error::CoLinearViolation),
598      Orientation::ClockWise => {
599        let root_position = Position {
600          ring_id: RingId(0),
601          position_id: PositionId(0),
602          size: self.rings[0].len(),
603        };
604        self.vertices_reverse(root_position, root_position.prev());
605        Ok(())
606      }
607    }
608  }
609
610  fn position_to_point_id(&self, position: Position) -> PointId {
611    self.rings[position.ring_id.0][position.position_id.0]
612  }
613
614  fn swap_positions(&mut self, pa: Position, pb: Position) {
615    assert_eq!(pa.ring_id, pb.ring_id);
616
617    let ring = &mut self.rings[pa.ring_id.0];
618
619    let pa_point_id: PointId = ring[pa.position_id.0];
620    let pb_point_id: PointId = ring[pb.position_id.0];
621    ring.swap(pa.position_id.0, pb.position_id.0);
622    self.position_index.swap(pa_point_id.0, pb_point_id.0);
623  }
624
625  pub fn is_monotone(&self, direction: &Vector<T, 2>) -> bool
626  where
627    T: PolygonScalar,
628  {
629    crate::algorithms::polygonization::monotone::is_monotone(self, direction)
630  }
631}
632
633impl Polygon<OrderedFloat<f64>> {
634  #[must_use]
635  // Center on <0,0>. Scale size such that max(width,height) = 1.
636  pub fn normalize(&self) -> Polygon<OrderedFloat<f64>> {
637    let (min, max) = self.bounding_box();
638    let [min_x, min_y] = min.array;
639    let [max_x, max_y] = max.array;
640    let width = max_x - min_x;
641    let height = max_y - min_y;
642    let ratio = std::cmp::max(width, height);
643    let centroid = self.centroid();
644    let t = Transform::translate(-Vector::from(centroid));
645    let s = Transform::uniform_scale(ratio.recip());
646    s * t * self
647  }
648}
649
650#[derive(Debug)]
651pub struct Cursor<'a, T> {
652  polygon: &'a Polygon<T>,
653  pub(crate) position: Position,
654}
655
656impl<T: TotalOrd> TotalOrd for Cursor<'_, T> {
657  fn total_cmp(&self, other: &Self) -> Ordering {
658    self.deref().total_cmp(other.deref())
659  }
660}
661
662impl<T> Deref for Cursor<'_, T> {
663  type Target = Point<T>;
664  fn deref(&self) -> &Self::Target {
665    self.point()
666  }
667}
668
669impl<'a, T> PartialEq for Cursor<'a, T> {
670  fn eq(&self, other: &Cursor<'a, T>) -> bool {
671    // FIXME: Make sure the two polygons are the same.
672    self.position == other.position
673  }
674}
675
676// Can't derive it because T should not be 'Clone'.
677impl<T> Clone for Cursor<'_, T> {
678  fn clone(&self) -> Self {
679    *self
680  }
681}
682impl<T> Copy for Cursor<'_, T> {}
683
684impl<'a, T> Cursor<'a, T> {
685  pub fn point_id(self) -> PointId {
686    self.polygon.position_to_point_id(self.position)
687  }
688
689  #[must_use]
690  pub fn prev(mut self) -> Cursor<'a, T> {
691    self.move_prev();
692    self
693  }
694
695  #[must_use]
696  pub fn next(mut self) -> Cursor<'a, T> {
697    self.move_next();
698    self
699  }
700
701  pub fn point(self: Cursor<'a, T>) -> &'a Point<T> {
702    &self.polygon.points[self.point_id().0]
703  }
704
705  pub fn move_next(&mut self) {
706    self.position.move_next()
707  }
708
709  pub fn move_prev(&mut self) {
710    self.position.move_prev()
711  }
712
713  // O(n)
714  pub fn is_ear(&self) -> bool
715  where
716    T: PolygonScalar,
717  {
718    let trig =
719      TriangleView::new_unchecked([self.prev().point(), self.point(), self.next().point()]);
720    if trig.orientation() == Orientation::CounterClockWise {
721      for pt in self.next().next().to(Excluded(self.prev())) {
722        if trig.locate(pt.point()) != PointLocation::Outside {
723          return false;
724        }
725      }
726      true
727    } else {
728      false
729    }
730  }
731
732  pub fn orientation(&self) -> Orientation
733  where
734    T: PolygonScalar,
735  {
736    let p1 = self.prev().point();
737    let p2 = self.point();
738    let p3 = self.next().point();
739    Point::orient(p1, p2, p3)
740  }
741
742  pub fn is_colinear(&self) -> bool
743  where
744    T: PolygonScalar,
745  {
746    self.orientation() == Orientation::CoLinear
747  }
748
749  pub fn to(self: Cursor<'a, T>, end: Bound<Cursor<'a, T>>) -> CursorIter<'a, T> {
750    // FIXME: Check that self and end point to the same polygon.
751    match end {
752      Bound::Unbounded => CursorIter {
753        cursor_head: self,
754        cursor_tail: self.prev(),
755        exhausted: false,
756      },
757      Bound::Included(end) => CursorIter {
758        cursor_head: self,
759        cursor_tail: end,
760        exhausted: false,
761      },
762      Bound::Excluded(end) => CursorIter {
763        cursor_head: self,
764        cursor_tail: end.prev(),
765        exhausted: false,
766      },
767    }
768  }
769}
770
771#[derive(Debug, Copy, Clone, PartialEq, Eq, Ord, PartialOrd)]
772pub struct Position {
773  ring_id: RingId,         // Ring identifier
774  size: usize,             // Ring size
775  position_id: PositionId, // Position in ring. 0 <= position_id < size
776}
777
778impl Position {
779  #[must_use]
780  pub fn prev(mut self) -> Position {
781    self.move_prev();
782    self
783  }
784
785  #[must_use]
786  pub fn next(mut self) -> Position {
787    self.move_next();
788    self
789  }
790
791  pub fn move_next(&mut self) {
792    if self.position_id.0 == self.size - 1 {
793      self.position_id.0 = 0;
794    } else {
795      self.position_id.0 += 1;
796    }
797  }
798
799  pub fn move_prev(&mut self) {
800    if self.position_id.0 == 0 {
801      self.position_id.0 = self.size - 1;
802    } else {
803      self.position_id.0 -= 1;
804    }
805  }
806}
807
808#[cfg(test)]
809pub mod tests {
810  use super::*;
811
812  use crate::testing::*;
813  use ordered_float::NotNan;
814  use proptest::collection::vec;
815  use proptest::prelude::*;
816  use proptest::proptest as proptest_block;
817
818  proptest_block! {
819    #[test]
820    fn random_polygon(poly: Polygon<i8>) {
821      prop_assert_eq!(poly.validate().err(), None);
822    }
823
824    #[test]
825    fn fuzz_new_polygon(pts: Vec<Point<i8>>) {
826      // make sure there's no input that can cause a panic. Err is okay, panic is not.
827      Polygon::new(pts).ok();
828    }
829
830    // These traits are usually derived but let's not rely on that.
831    #[test]
832    fn fuzz_polygon_traits(poly: Polygon<i8>) {
833      let _ = format!("{:?}", &poly);
834      let _ = poly.clone();
835    }
836
837    #[test]
838    fn fuzz_validate(pts: Vec<Point<i8>>) {
839      // make sure there's no input that can cause a panic. Err is okay, panic is not.
840      Polygon::new_unchecked(pts).validate().ok();
841    }
842
843    #[test]
844    fn fuzz_validate_weakly(pts: Vec<Point<i8>>) {
845      // make sure there's no input that can cause a panic. Err is okay, panic is not.
846      Polygon::new_unchecked(pts).validate_weakly().ok();
847    }
848
849    #[test]
850    fn fuzz_centroid(poly in polygon_nn()) {
851      poly.centroid();
852    }
853
854    #[test]
855    fn signed_area_non_negative_prop(poly in polygon_nn()) {
856      prop_assert!( poly.signed_area::<NotNan<f64>>() >= NotNan::zero())
857    }
858
859    #[test]
860    fn fuzz_orientation(pts in vec(any_nn(), 2..100)) {
861      let poly = Polygon::new_unchecked(pts);
862      poly.orientation();
863    }
864
865    #[test]
866    fn fuzz_ensure_ccw(pts in vec(any_nn(), 2..100)) {
867      let mut poly = Polygon::new_unchecked(pts);
868      poly.ensure_ccw().ok();
869    }
870
871    #[test]
872    fn locate_id_prop(poly: Polygon<i8>, origin: Point<i8>) {
873      prop_assert_eq!(
874        locate_by_triangulation(&poly, &origin),
875        poly.locate(&origin)
876      )
877    }
878
879    #[test]
880    fn equals_identity_prop(poly: Polygon<i8>, offset: usize) {
881      let points: Vec<Point<i8>> = poly.iter_boundary().map(|cursor| cursor.point()).cloned().collect();
882      let offset = offset % points.len();
883      let rotated_points: Vec<Point<i8>> = [&points[offset..], &points[0..offset]].concat();
884      prop_assert!(
885        poly.equals(&Polygon::new(rotated_points).unwrap())
886      )
887    }
888  }
889
890  // // #[cfg(not(debug_assertions))] // proxy for release builds.
891  // #[proptest]
892  // fn normalize_props(poly: Polygon<i8>) {
893  //   // Debug builds are ~50x slower than release builds. Sigh.
894  //   let norm = poly.float().normalize();
895  //   // prop_assert_eq!(norm.centroid(), Point::zero());
896  //   let (min, max) = norm.bounding_box();
897  //   let width = max.x_coord() - min.x_coord();
898  //   let height = max.y_coord() - min.y_coord();
899  //   // prop_assert!(width == OrderedFloat(1.0) || height == OrderedFloat(1.0));
900  // }
901
902  #[test]
903  #[should_panic]
904  fn locate_feature_fixme() {
905    let mut poly: Polygon<i8> = Polygon::new(vec![
906      Point { array: [0, 0] },
907      Point { array: [-1, 127] },
908      Point { array: [-50, 48] },
909    ])
910    .expect("valid polygon");
911    // Add an hole (happens to be topologically invalid but that doesn't matter)
912    poly.rings.push(vec![PointId(0), PointId(1), PointId(2)]);
913    let origin = Point { array: [79, 108] };
914    poly.locate(&origin);
915  }
916
917  #[test]
918  fn locate_unit_1() {
919    let poly: Polygon<i8> = Polygon::new(vec![
920      Point { array: [0, 0] },
921      Point { array: [-1, 127] },
922      Point { array: [-50, 48] },
923    ])
924    .expect("valid polygon");
925    let origin = Point { array: [79, 108] };
926
927    assert_eq!(poly.locate(&origin), PointLocation::Outside);
928  }
929
930  #[test]
931  fn locate_unit_2() {
932    let poly: Polygon<i8> = Polygon::new(vec![
933      Point { array: [-9, 83] },
934      Point { array: [-28, 88] },
935      Point { array: [-9, -75] },
936      Point { array: [-2, -6] },
937      Point { array: [-2, 11] },
938    ])
939    .expect("valid polygon");
940    let origin = Point { array: [-9, 0] };
941
942    assert_eq!(
943      locate_by_triangulation(&poly, &origin),
944      poly.locate(&origin)
945    );
946  }
947
948  // Locate a point relative to a polygon. Should be identical to
949  // Polygon::locate but slower.
950  fn locate_by_triangulation<T>(poly: &Polygon<T>, origin: &Point<T>) -> PointLocation
951  where
952    T: PolygonScalar,
953  {
954    for edge in poly.iter_boundary_edges() {
955      if edge.contains(origin) {
956        return PointLocation::OnBoundary;
957      }
958    }
959    for (a, b, c) in poly.triangulate() {
960      let trig = TriangleView::new([&a, &b, &c]).expect("valid triangle");
961      if trig.locate(origin) != PointLocation::Outside {
962        return PointLocation::Inside;
963      }
964    }
965    PointLocation::Outside
966  }
967}
rgeometry/data/polygon.rs

rgeometry/data/
polygon.rs
