1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

// https://en.wikipedia.org/wiki/Monotone_polygon
use crate::data::{Cursor, Point, Polygon, Vector};
use crate::{Error, Orientation, PolygonScalar};

use std::cmp::Ordering;
use std::collections::VecDeque;
use std::ops::Bound::*;

///Check if the given polyon is monotone with resprect to given direction
pub fn is_monotone<T>(poly: &Polygon<T>, direction: &Vector<T, 2>) -> bool
where
  T: PolygonScalar,
{
  // We can only check polygons without. It would be nice to enforce this with types.
  assert_eq!(poly.rings.len(), 1);

  let cmp_cursors = |a: &Cursor<'_, T>, b: &Cursor<'_, T>| direction.cmp_along(a, b).then(a.cmp(b));
  // XXX: Is there a way to get both the min and max element at the same time?
  let max_cursor = {
    match poly.iter_boundary().max_by(cmp_cursors) {
      Some(c) => c,
      None => return false,
    }
  };
  let min_cursor = {
    match poly.iter_boundary().min_by(cmp_cursors) {
      Some(c) => c,
      None => return false,
    }
  };

  // All points going counter-clockwise from min_cursor to max_cursor must be
  // less-than or equal to the next point in the chain along the direction vector.
  for pt in min_cursor.to(Excluded(max_cursor)) {
    if direction.cmp_along(&pt, &pt.next()) == Ordering::Greater {
      return false;
    }
  }

  // Walking down the other chain, the condition is opposite: All points
  // must be greater-than or equal to the next point in the chain along the direction vector.
  for pt in max_cursor.to(Excluded(min_cursor)) {
    if direction.cmp_along(&pt, &pt.next()) == Ordering::Less {
      return false;
    }
  }

  true
}

/// Generates a monotone polygon from given points with respect to given direction
pub fn new_monotone_polygon<T>(
  mut points: Vec<Point<T, 2>>,
  direction: &Vector<T, 2>,
) -> Result<Polygon<T>, Error>
where
  T: PolygonScalar,
{
  // First compare along the direction vector.
  // If two points are the same distance along the vector, compare their X and Y components.
  points.sort_by(|prev, curr| direction.cmp_along(prev, curr).then(prev.cmp(&curr)));

  points.dedup();
  if points.len() < 3 {
    return Err(Error::InsufficientVertices);
  }

  let (min_point, max_point) = (
    points.first().unwrap().clone(),
    points.last().unwrap().clone(),
  );

  let mut polygon_points: VecDeque<Point<T, 2>> = VecDeque::new();

  while let Some(curr) = points.pop() {
    match Orientation::new(&min_point, &max_point, &curr) {
      Orientation::ClockWise => polygon_points.push_front(curr),
      _ => polygon_points.push_back(curr),
    }
  }
  let vec = Vec::from(polygon_points);

  Polygon::new(vec)
}

//testing
#[cfg(test)]
mod monotone_testing {
  use super::*;
  use crate::data::{Point, Polygon, PolygonConvex, Vector};
  use crate::Orientation;
  use proptest::prelude::*;
  use std::collections::BTreeSet;
  use test_strategy::proptest;

  #[proptest]
  fn convex_polygon_is_montone(convex_polygon: PolygonConvex<i8>, direction: Vector<i8, 2>) {
    prop_assert!(is_monotone(&convex_polygon.polygon(), &direction));
  }

  #[test]
  //ToDo: Find a way to proptest the Non-monotone case
  fn non_y_monotone() {
    let polygon = Polygon::new(vec![
      Point::new([0, 1]),
      Point::new([1, 2]),
      Point::new([1, -2]),
      Point::new([0, -1]),
      Point::new([-1, -2]),
      Point::new([-1, 2]),
    ])
    .unwrap();
    assert!(!is_monotone(&polygon, &Vector::from(Point::new([0, 1]))));
  }

  #[test]
  fn monotone_mountain() {
    let polygon = Polygon::new(vec![
      Point::new([0, 3]),
      Point::new([1, 2]),
      Point::new([1, -2]),
      Point::new([0, -3]),
    ])
    .unwrap();
    assert!(is_monotone(&polygon, &Vector::from(Point::new([0, 1]))));
  }

  #[proptest]
  fn monotone_is_monotone_prop(points: Vec<Point<i8, 2>>, direction: Vector<i8, 2>) {
    if let Ok(p) = new_monotone_polygon(points, &direction) {
      prop_assert!(is_monotone(&p, &direction));
      prop_assert_eq!(p.validate().err(), None);
    }
  }

  #[proptest]
  fn valid_monotone(points: Vec<Point<i8, 2>>, direction: Vector<i8, 2>) {
    // dedup points
    let mut points = points;
    let mut set = BTreeSet::new();
    points.retain(|pt| set.insert(pt.clone()));
    // If we have at least three, non-colinear points, then we must be able to
    // create a monotone polygon.
    if !points
      .windows(3)
      .all(|window| Orientation::new(&window[0], &window[1], &window[2]).is_colinear())
    {
      let p = new_monotone_polygon(points, &direction).unwrap();
      prop_assert!(is_monotone(&p, &direction));
      prop_assert_eq!(p.validate().err(), None);
    }
  }
}