rgeometry/data/polygon/
convex.rs

1use num_traits::*;
2use ordered_float::OrderedFloat;
3use rand::distributions::uniform::SampleUniform;
4use rand::distributions::{Distribution, Standard};
5use rand::seq::SliceRandom;
6use rand::Rng;
7use std::ops::*;
8
9use crate::data::{Point, PointLocation, TriangleView, Vector};
10use crate::{Error, Orientation, PolygonScalar, TotalOrd};
11
12use super::Polygon;
13
14#[derive(Debug, Clone, Hash)]
15pub struct PolygonConvex<T>(Polygon<T>);
16
17///////////////////////////////////////////////////////////////////////////////
18// PolygonConvex
19
20impl<T> PolygonConvex<T>
21where
22  T: PolygonScalar,
23{
24  /// Assume that a polygon is convex.
25  ///
26  /// # Safety
27  /// The input polygon has to be strictly convex, ie. no vertices are allowed to
28  /// be concave or colinear.
29  ///
30  /// # Time complexity
31  /// $O(1)$
32  pub fn new_unchecked(poly: Polygon<T>) -> PolygonConvex<T> {
33    PolygonConvex(poly)
34  }
35
36  /// Locate a point relative to a convex polygon.
37  ///
38  /// # Time complexity
39  /// $O(\log n)$
40  ///
41  /// # Examples
42  /// <iframe src="https://web.rgeometry.org/wasm/gist/2cb9ff5bd6ce24f395a5ea30280aabee"></iframe>
43  ///
44  pub fn locate(&self, pt: &Point<T, 2>) -> PointLocation {
45    let poly = &self.0;
46    let vertices = self.boundary_slice();
47    let p0 = poly.point(vertices[0]);
48    let mut lower = 1;
49    let mut upper = vertices.len() - 1;
50    while lower + 1 < upper {
51      let middle = (lower + upper) / 2;
52      if Point::orient(p0, poly.point(vertices[middle]), pt) == Orientation::CounterClockWise {
53        lower = middle;
54      } else {
55        upper = middle;
56      }
57    }
58    let p1 = poly.point(vertices[lower]);
59    let p2 = poly.point(vertices[upper]);
60    let triangle = TriangleView::new_unchecked([p0, p1, p2]);
61    triangle.locate(pt)
62  }
63
64  /// Validates the following properties:
65  ///  * Each vertex is convex, ie. not concave or colinear.
66  ///  * All generate polygon properties hold true (eg. no duplicate points, no self-intersections).
67  ///
68  /// # Time complexity
69  /// $O(n \log n)$
70  pub fn validate(&self) -> Result<(), Error> {
71    for cursor in self.0.iter_boundary() {
72      if cursor.orientation() != Orientation::CounterClockWise {
73        return Err(Error::ConvexViolation);
74      }
75    }
76    self.0.validate()
77  }
78
79  pub fn float(self) -> PolygonConvex<OrderedFloat<f64>>
80  where
81    T: Clone + Into<f64>,
82  {
83    PolygonConvex::new_unchecked(self.0.float())
84  }
85
86  /// $O(1)$
87  pub fn polygon(&self) -> &Polygon<T> {
88    self.into()
89  }
90
91  /// Uniformly sample a random convex polygon.
92  ///
93  /// The output polygon is rooted in `(0,0)`, grows upwards, and has a height and width of [`T::max_value()`](Bounded::max_value).
94  ///
95  /// # Time complexity
96  /// $O(n \log n)$
97  ///
98  // # Examples
99  // ```no_run
100  // # use rgeometry_wasm::playground::*;
101  // # use rgeometry::data::*;
102  // # clear_screen();
103  // # set_viewport(2.0, 2.0);
104  // # let convex: PolygonConvex<i8> = {
105  // PolygonConvex::random(3, &mut rand::thread_rng())
106  // # };
107  // # render_polygon(&convex.float().normalize());
108  // ```
109  // <iframe src="https://web.rgeometry.org/wasm/gist/9abc54a5e2e3d33e3dd1785a71e812d2"></iframe>
110  pub fn random<R>(n: usize, rng: &mut R) -> PolygonConvex<T>
111  where
112    T: Bounded + PolygonScalar + SampleUniform,
113    R: Rng + ?Sized,
114  {
115    let n = n.max(3);
116    loop {
117      let vs = {
118        let mut vs = random_vectors(n, rng);
119        Vector::sort_around(&mut vs);
120        vs
121      };
122      let vertices: Vec<Point<T, 2>> = vs
123        .into_iter()
124        .scan(Point::zero(), |st, vec| {
125          *st += vec;
126          Some((*st).clone())
127        })
128        .collect();
129      let n_vertices = (*vertices).len();
130      debug_assert_eq!(n_vertices, n);
131      // FIXME: Use the convex hull algorithm for polygons rather than point sets.
132      //        It runs in O(n) rather than O(n log n). Hasn't been implemented, yet, though.
133      // If the vertices are all colinear then give up and try again.
134      // FIXME: If the RNG always returns zero then we might loop forever.
135      //        Maybe limit the number of recursions.
136      if let Ok(p) = crate::algorithms::convex_hull(vertices) {
137        return p;
138      }
139    }
140  }
141}
142
143impl PolygonConvex<OrderedFloat<f64>> {
144  #[must_use]
145  pub fn normalize(&self) -> PolygonConvex<OrderedFloat<f64>> {
146    PolygonConvex::new_unchecked(self.0.normalize())
147  }
148}
149
150///////////////////////////////////////////////////////////////////////////////
151// Trait Implementations
152
153impl<T> Deref for PolygonConvex<T> {
154  type Target = Polygon<T>;
155  fn deref(&self) -> &Self::Target {
156    &self.0
157  }
158}
159
160impl<T> From<PolygonConvex<T>> for Polygon<T> {
161  fn from(convex: PolygonConvex<T>) -> Polygon<T> {
162    convex.0
163  }
164}
165
166impl<'a, T> From<&'a PolygonConvex<T>> for &'a Polygon<T> {
167  fn from(convex: &'a PolygonConvex<T>) -> &'a Polygon<T> {
168    &convex.0
169  }
170}
171
172impl Distribution<PolygonConvex<isize>> for Standard {
173  fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> PolygonConvex<isize> {
174    PolygonConvex::random(100, rng)
175  }
176}
177
178///////////////////////////////////////////////////////////////////////////////
179// Helper functions
180
181// Property: random_between(n, max, &mut rng).sum::<usize>() == max
182fn random_between_iter<T, R>(n: usize, rng: &mut R) -> impl Iterator<Item = T>
183where
184  T: PolygonScalar + Bounded + SampleUniform,
185  R: Rng + ?Sized,
186{
187  let zero: T = T::from_constant(0);
188  let max: T = Bounded::max_value();
189  assert!(n > 0);
190  let mut pts = Vec::with_capacity(n);
191  while pts.len() < n - 1 {
192    pts.push(rng.gen_range(zero.clone()..max.clone()));
193  }
194  pts.sort_unstable_by(TotalOrd::total_cmp);
195  pts.push(max);
196  pts.into_iter().scan(zero, |from, x| {
197    let out = x.clone() - (*from).clone();
198    *from = x;
199    Some(out)
200  })
201}
202
203// Property: random_between_zero(10, 100, &mut rng).iter().sum::<isize>() == 0
204fn random_between_zero<T, R>(n: usize, rng: &mut R) -> Vec<T>
205where
206  T: Bounded + PolygonScalar + SampleUniform,
207  R: Rng + ?Sized,
208{
209  assert!(n >= 2);
210  let n_positive = rng.gen_range(1..n); // [1;n[
211  let n_negative = n - n_positive;
212  assert!(n_positive + n_negative == n);
213  let positive = random_between_iter(n_positive, rng);
214  let negative = random_between_iter(n_negative, rng).map(|i: T| -i);
215  let mut result: Vec<T> = positive.chain(negative).collect();
216  result.shuffle(rng);
217  result
218}
219
220// Random vectors that sum to zero.
221fn random_vectors<T, R>(n: usize, rng: &mut R) -> Vec<Vector<T, 2>>
222where
223  T: Bounded + PolygonScalar + SampleUniform,
224  R: Rng + ?Sized,
225{
226  random_between_zero(n, rng)
227    .into_iter()
228    .zip(random_between_zero(n, rng))
229    .map(|(a, b)| Vector([a, b]))
230    .collect()
231}
232
233///////////////////////////////////////////////////////////////////////////////
234// Tests
235
236#[cfg(test)]
237mod tests {
238  use super::*;
239  use rand::rngs::SmallRng;
240  use rand::SeedableRng;
241
242  use proptest::prelude::*;
243  use proptest::proptest as proptest_block;
244
245  proptest_block! {
246    // These traits are usually derived but let's not rely on that.
247    #[test]
248    fn fuzz_convex_traits(poly: PolygonConvex<i8>) {
249      let _ = format!("{:?}", &poly);
250      let _ = poly.clone();
251    }
252
253    #[test]
254    fn fuzz_validate(poly: Polygon<i8>) {
255      let convex = PolygonConvex::new_unchecked(poly);
256      let _ = convex.validate();
257    }
258
259    #[test]
260    fn all_random_convex_polygons_are_valid_i8(poly: PolygonConvex<i8>) {
261      prop_assert_eq!(poly.validate().err(), None)
262    }
263
264    #[test]
265    fn random_convex_prop(poly: PolygonConvex<i8>) {
266      let (min, max) = poly.bounding_box();
267      prop_assert_eq!(min.y_coord(), &0);
268      let width = max.x_coord() - min.x_coord();
269      let height = max.y_coord() - min.y_coord();
270      prop_assert_eq!(width, i8::MAX);
271      prop_assert_eq!(height, i8::MAX);
272    }
273
274    #[test]
275    fn all_random_convex_polygons_are_valid_i64(poly: PolygonConvex<i64>) {
276      prop_assert_eq!(poly.validate().err(), None)
277    }
278
279    #[test]
280    fn sum_to_max(n in 1..1000, seed: u64) {
281      let mut rng = SmallRng::seed_from_u64(seed);
282      let vecs = random_between_iter::<i8, _>(n as usize, &mut rng);
283      prop_assert_eq!(vecs.sum::<i8>(), i8::MAX);
284
285      let vecs = random_between_iter::<i64, _>(n as usize, &mut rng);
286      prop_assert_eq!(vecs.sum::<i64>(), i64::MAX);
287    }
288
289    #[test]
290    fn random_between_zero_properties(n in 2..1000, seed: u64) {
291      let mut rng = SmallRng::seed_from_u64(seed);
292      let vecs: Vec<i8> = random_between_zero(n as usize, &mut rng);
293      prop_assert_eq!(vecs.iter().sum::<i8>(), 0);
294      prop_assert_eq!(vecs.len(), n as usize);
295
296      let vecs: Vec<i64> = random_between_zero(n as usize, &mut rng);
297      prop_assert_eq!(vecs.iter().sum::<i64>(), 0);
298      prop_assert_eq!(vecs.len(), n as usize);
299    }
300
301    #[test]
302    fn sum_to_zero_vector(n in 2..1000, seed: u64) {
303      let mut rng = SmallRng::seed_from_u64(seed);
304      let vecs: Vec<Vector<i8, 2>> = random_vectors(n as usize, &mut rng);
305      prop_assert_eq!(vecs.into_iter().sum::<Vector<i8, 2>>(), Vector([0, 0]))
306    }
307  }
308}
rgeometry/data/polygon/convex.rs

rgeometry/data/polygon/
convex.rs
