rgeometry/algorithms/polygonization/
monotone.rs

1// https://en.wikipedia.org/wiki/Monotone_polygon
2use crate::data::{Cursor, Point, Polygon, Vector};
3use crate::{Error, Orientation, PolygonScalar, TotalOrd};
4
5use std::cmp::Ordering;
6use std::collections::VecDeque;
7use std::ops::Bound::*;
8
9///Check if the given polyon is monotone with resprect to given direction
10pub fn is_monotone<T>(poly: &Polygon<T>, direction: &Vector<T, 2>) -> bool
11where
12  T: PolygonScalar,
13{
14  // We can only check polygons without. It would be nice to enforce this with types.
15  assert_eq!(poly.rings.len(), 1);
16
17  let cmp_cursors =
18    |a: &Cursor<'_, T>, b: &Cursor<'_, T>| direction.cmp_along(a, b).then_with(|| a.total_cmp(b));
19  // XXX: Is there a way to get both the min and max element at the same time?
20  let max_cursor = {
21    match poly.iter_boundary().max_by(cmp_cursors) {
22      Some(c) => c,
23      None => return false,
24    }
25  };
26  let min_cursor = {
27    match poly.iter_boundary().min_by(cmp_cursors) {
28      Some(c) => c,
29      None => return false,
30    }
31  };
32
33  // All points going counter-clockwise from min_cursor to max_cursor must be
34  // less-than or equal to the next point in the chain along the direction vector.
35  for pt in min_cursor.to(Excluded(max_cursor)) {
36    if direction.cmp_along(&pt, &pt.next()) == Ordering::Greater {
37      return false;
38    }
39  }
40
41  // Walking down the other chain, the condition is opposite: All points
42  // must be greater-than or equal to the next point in the chain along the direction vector.
43  for pt in max_cursor.to(Excluded(min_cursor)) {
44    if direction.cmp_along(&pt, &pt.next()) == Ordering::Less {
45      return false;
46    }
47  }
48
49  true
50}
51
52/// Generates a monotone polygon from given points with respect to given direction
53pub fn new_monotone_polygon<T>(
54  mut points: Vec<Point<T, 2>>,
55  direction: &Vector<T, 2>,
56) -> Result<Polygon<T>, Error>
57where
58  T: PolygonScalar,
59{
60  // First compare along the direction vector.
61  // If two points are the same distance along the vector, compare their X and Y components.
62  points.sort_by(|prev, curr| {
63    direction
64      .cmp_along(prev, curr)
65      .then_with(|| prev.total_cmp(curr))
66  });
67
68  points.dedup();
69  if points.len() < 3 {
70    return Err(Error::InsufficientVertices);
71  }
72
73  let (min_point, max_point) = (
74    points.first().unwrap().clone(),
75    points.last().unwrap().clone(),
76  );
77
78  let mut polygon_points: VecDeque<Point<T, 2>> = VecDeque::new();
79
80  while let Some(curr) = points.pop() {
81    match Orientation::new(&min_point, &max_point, &curr) {
82      Orientation::ClockWise => polygon_points.push_front(curr),
83      _ => polygon_points.push_back(curr),
84    }
85  }
86  let vec = Vec::from(polygon_points);
87
88  Polygon::new(vec)
89}
90
91//testing
92#[cfg(test)]
93mod monotone_testing {
94  use super::*;
95  use crate::data::{Point, Polygon, PolygonConvex, Vector};
96  use crate::Orientation;
97  use proptest::prelude::*;
98  use std::collections::BTreeSet;
99  use test_strategy::proptest;
100
101  #[proptest]
102  fn convex_polygon_is_montone(convex_polygon: PolygonConvex<i8>, direction: Vector<i8, 2>) {
103    prop_assert!(is_monotone(convex_polygon.polygon(), &direction));
104  }
105
106  #[test]
107  //ToDo: Find a way to proptest the Non-monotone case
108  fn non_y_monotone() {
109    let polygon = Polygon::new(vec![
110      Point::new([0, 1]),
111      Point::new([1, 2]),
112      Point::new([1, -2]),
113      Point::new([0, -1]),
114      Point::new([-1, -2]),
115      Point::new([-1, 2]),
116    ])
117    .unwrap();
118    assert!(!is_monotone(&polygon, &Vector::from(Point::new([0, 1]))));
119  }
120
121  #[test]
122  fn monotone_mountain() {
123    let polygon = Polygon::new(vec![
124      Point::new([0, 3]),
125      Point::new([1, 2]),
126      Point::new([1, -2]),
127      Point::new([0, -3]),
128    ])
129    .unwrap();
130    assert!(is_monotone(&polygon, &Vector::from(Point::new([0, 1]))));
131  }
132
133  #[proptest]
134  fn monotone_is_monotone_prop(points: Vec<Point<i8, 2>>, direction: Vector<i8, 2>) {
135    if let Ok(p) = new_monotone_polygon(points, &direction) {
136      prop_assert!(is_monotone(&p, &direction));
137      prop_assert_eq!(p.validate().err(), None);
138    }
139  }
140
141  #[proptest]
142  fn valid_monotone(points: Vec<Point<i8, 2>>, direction: Vector<i8, 2>) {
143    // dedup points
144    let mut points = points;
145    let mut set = BTreeSet::new();
146    points.retain(|pt| set.insert(*pt));
147    // If we have at least three, non-colinear points, then we must be able to
148    // create a monotone polygon.
149    if !points
150      .windows(3)
151      .all(|window| Orientation::new(&window[0], &window[1], &window[2]).is_colinear())
152    {
153      let p = new_monotone_polygon(points, &direction).unwrap();
154      prop_assert!(is_monotone(&p, &direction));
155      prop_assert_eq!(p.validate().err(), None);
156    }
157  }
158}
rgeometry/algorithms/polygonization/monotone.rs

rgeometry/algorithms/polygonization/
monotone.rs
