iron_shapes/
polygon.rs

1// Copyright (c) 2018-2020 Thomas Kramer.
2// SPDX-FileCopyrightText: 2018-2022 Thomas Kramer
3//
4// SPDX-License-Identifier: AGPL-3.0-or-later
5
6//! This module contains data types and functions for polygons with holes.
7
8use crate::CoordinateType;
9
10use crate::edge::Edge;
11use crate::point::Point;
12use crate::rect::Rect;
13
14pub use crate::traits::{BoundingBox, DoubledOrientedArea, MapPointwise, WindingNumber};
15
16pub use crate::simple_polygon::*;
17use crate::types::*;
18
19use crate::traits::TryCastCoord;
20use itertools::Itertools;
21use num_traits::{Num, NumCast};
22use std::cmp::{Ord, PartialEq};
23use std::iter::FromIterator;
24
25/// A polygon possibly with holes. The polygon is defined by a hull and a list of holes
26/// which are both `SimplePolygon`s.
27#[derive(Clone, Hash, Debug, Eq, PartialEq)]
28#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
29pub struct Polygon<T> {
30    /// The outer hull of the polygon.
31    pub exterior: SimplePolygon<T>,
32    /// A list of holes in the polygon.
33    pub interiors: Vec<SimplePolygon<T>>,
34}
35
36/// Shorthand notation for creating a polygon.
37///
38/// # Example
39/// ```
40/// # #[macro_use]
41/// # extern crate iron_shapes;
42/// # fn main() {
43/// use iron_shapes::prelude::*;
44/// let p = polygon!((0, 0), (1, 0), (1, 1));
45/// assert_eq!(p, Polygon::new(vec![(0, 0), (1, 0), (1, 1)]));
46/// # }
47/// ```
48#[macro_export]
49macro_rules! polygon {
50 ($($x:expr),*) => {Polygon::new((vec![$($x),*]))}
51}
52
53/// Create a polygon from a `Vec` of values convertible to `Point`s.
54impl<'a, T, P> From<&'a Vec<P>> for Polygon<T>
55where
56    T: CoordinateType,
57    Point<T>: From<&'a P>,
58{
59    fn from(vec: &'a Vec<P>) -> Self {
60        Polygon {
61            exterior: vec.into(),
62            interiors: Vec::new(),
63        }
64    }
65}
66
67/// Create a polygon from a `Vec` of values convertible to `Point`s.
68impl<T, P> From<Vec<P>> for Polygon<T>
69where
70    T: Copy + PartialOrd,
71    Point<T>: From<P>,
72{
73    fn from(vec: Vec<P>) -> Self {
74        Polygon {
75            exterior: vec.into(),
76            interiors: Vec::new(),
77        }
78    }
79}
80
81/// Create a polygon from a iterator of values convertible to `Point`s.
82impl<T, P> FromIterator<P> for Polygon<T>
83where
84    T: Copy,
85    P: Into<Point<T>>,
86{
87    fn from_iter<I>(iter: I) -> Self
88    where
89        I: IntoIterator<Item = P>,
90    {
91        let exterior: SimplePolygon<T> = SimplePolygon::from_iter(iter);
92        Polygon {
93            exterior,
94            interiors: Vec::new(),
95        }
96    }
97}
98
99/// Create a polygon from a simple polygon.
100impl<T> From<SimplePolygon<T>> for Polygon<T> {
101    fn from(simple_polygon: SimplePolygon<T>) -> Self {
102        Polygon {
103            exterior: simple_polygon,
104            interiors: Vec::new(),
105        }
106    }
107}
108
109/// Create a polygon from a simple polygon.
110impl<T> From<&SimplePolygon<T>> for Polygon<T>
111where
112    T: Copy,
113{
114    fn from(simple_polygon: &SimplePolygon<T>) -> Self {
115        simple_polygon.clone().into()
116    }
117}
118
119/// Create a polygon from a rectangle.
120impl<T> From<Rect<T>> for Polygon<T>
121where
122    T: Copy,
123{
124    fn from(rect: Rect<T>) -> Self {
125        Self::from(&rect)
126    }
127}
128
129/// Create a polygon from a rectangle.
130impl<T> From<&Rect<T>> for Polygon<T>
131where
132    T: Copy,
133{
134    fn from(rect: &Rect<T>) -> Self {
135        SimplePolygon::new_raw(vec![
136            rect.lower_left(),
137            rect.lower_right(),
138            rect.upper_right(),
139            rect.upper_left(),
140        ])
141        .into()
142    }
143}
144
145/// Trait for the conversion of a geometric shape to a polygon.
146pub trait ToPolygon<T> {
147    /// Convert the geometric object into a polygon.
148    fn to_polygon(&self) -> Polygon<T>;
149}
150
151impl<T> Polygon<T> {
152    /// Create a new polygon from a sequence of points.
153    /// Ordering of points is not normalized. This impacts the equality check.
154    pub fn new_raw(exterior: Vec<Point<T>>) -> Self {
155        Self {
156            exterior: SimplePolygon::new_raw(exterior),
157            interiors: Default::default(),
158        }
159    }
160
161    /// Create a new polygon from a hull and a list of holes.
162    /// Ordering of points is not normalized. This impacts the equality check.
163    pub fn new_raw_with_holes<E, I>(exterior: E, holes: Vec<I>) -> Self
164    where
165        E: Into<SimplePolygon<T>>,
166        I: Into<SimplePolygon<T>>,
167    {
168        Polygon {
169            exterior: exterior.into(),
170            interiors: holes.into_iter().map(|i| i.into()).collect(),
171        }
172    }
173
174    /// Create empty polygon without any vertices.
175    pub fn empty() -> Self {
176        Polygon {
177            exterior: SimplePolygon::empty(),
178            interiors: Vec::new(),
179        }
180    }
181
182    /// Get the number of vertices.
183    pub fn len(&self) -> usize {
184        self.exterior.len()
185    }
186
187    /// Check if polygon has no vertices.
188    pub fn is_empty(&self) -> bool {
189        self.exterior.is_empty()
190    }
191}
192
193impl<T: Copy> Polygon<T> {
194    /// Get all exterior edges of the polygon.
195    pub fn edges(&self) -> Vec<Edge<T>> {
196        self.exterior.edges()
197    }
198
199    /// Iterate over all edges of the polygon, including interior edges.
200    pub fn all_edges_iter(&self) -> impl Iterator<Item = Edge<T>> + '_ {
201        self.exterior.edges_iter().chain(
202            self.interiors
203                .iter()
204                .flat_map(|interior| interior.edges_iter()),
205        )
206    }
207}
208
209impl<T: PartialOrd> Polygon<T> {
210    /// Create a new polygon from a sequence of points.
211    pub fn new<I>(i: I) -> Self
212    where
213        I: Into<Self>,
214    {
215        i.into().normalized()
216    }
217
218    /// Create a new polygon from a hull and a list of holes.
219    pub fn new_with_holes<E, I>(exterior: E, holes: Vec<I>) -> Self
220    where
221        E: Into<SimplePolygon<T>>,
222        I: Into<SimplePolygon<T>>,
223    {
224        Polygon {
225            exterior: exterior.into(),
226            interiors: holes.into_iter().map(|i| i.into()).collect(),
227        }
228        .normalized()
229    }
230
231    /// Reorder vertices and holes to get the lexicographically smallest representation of this polygon.
232    /// Does not change the orientations.
233    pub fn normalize(&mut self) {
234        self.exterior.normalize();
235        self.interiors.iter_mut().for_each(|p| p.normalize());
236        self.interiors.sort_by(|a, b| {
237            a.points()
238                .partial_cmp(b.points())
239                .unwrap_or(std::cmp::Ordering::Less)
240        })
241    }
242
243    /// Reorder vertices and holes to get the lexicographically smallest representation of this polygon.
244    /// Does not change the orientations.
245    pub fn normalized(mut self) -> Self {
246        self.normalize();
247        self
248    }
249}
250
251impl<T: CoordinateType> Polygon<T> {
252    /// Get the convex hull of the polygon.
253    ///
254    /// Implements Andrew's Monotone Chain algorithm.
255    /// See: <http://geomalgorithms.com/a10-_hull-1.html>
256    pub fn convex_hull(&self) -> SimplePolygon<T>
257    where
258        T: Ord,
259    {
260        self.exterior.convex_hull()
261    }
262
263    /// Get the vertex with lowest x-coordinate of the exterior polygon.
264    /// Prefer lower y-coordinates to break ties.
265    ///
266    /// # Examples
267    ///
268    /// ```
269    /// use iron_shapes::polygon::Polygon;
270    /// use iron_shapes::point::Point;
271    /// let coords = vec![(0, 0), (1, 0), (-1, 2), (-1, 1)];
272    ///
273    /// let poly = Polygon::new(coords);
274    ///
275    /// assert_eq!(poly.lower_left_vertex(), Point::new(-1, 1));
276    ///
277    /// ```
278    pub fn lower_left_vertex(&self) -> Point<T> {
279        self.exterior.lower_left_vertex()
280    }
281
282    /// Get the orientation of the exterior polygon.
283    ///
284    /// # Examples
285    ///
286    /// ```
287    /// use iron_shapes::polygon::Polygon;
288    /// use iron_shapes::point::Point;
289    /// use iron_shapes::types::Orientation;
290    /// let coords = vec![(0, 0), (3, 0), (3, 1)];
291    ///
292    /// let poly = Polygon::new(coords);
293    ///
294    /// assert_eq!(poly.orientation::<i64>(), Orientation::CounterClockWise);
295    ///
296    /// ```
297    pub fn orientation<Area>(&self) -> Orientation
298    where
299        Area: Num + From<T> + PartialOrd,
300    {
301        self.exterior.orientation::<Area>()
302    }
303}
304
305impl<T> TryBoundingBox<T> for Polygon<T>
306where
307    T: Copy + PartialOrd,
308{
309    fn try_bounding_box(&self) -> Option<Rect<T>> {
310        // TODO: What if holes exceed the exterior boundary?
311        let bbox = self.exterior.try_bounding_box();
312
313        if let Some(bbox) = &bbox {
314            debug_assert!(
315                self.interiors.iter()
316                    .filter_map(|p| p.try_bounding_box())
317                    .all(|internal_bbox| bbox.contains_rectangle(&internal_bbox)),
318                "Bounding boxes of interior polygons exceed the bounding box of the exterior polygon."
319            );
320        } else {
321            // If the bounding box of the hull is not defined there should also be no
322            // defined bounding boxes for the holes.
323            let num_internal_bboxes = self
324                .interiors
325                .iter()
326                .filter_map(|p| p.try_bounding_box())
327                .count();
328            debug_assert_eq!(
329                num_internal_bboxes, 0,
330                "Polygon with empty zero-vertex hull cannot contain holes."
331            );
332        }
333
334        bbox
335    }
336}
337
338impl<T> WindingNumber<T> for Polygon<T>
339where
340    T: CoordinateType,
341{
342    /// Calculate the winding number of the polygon around this point.
343    ///
344    /// TODO: Define how point on edges and vertices is handled.
345    ///
346    /// See: <http://geomalgorithms.com/a03-_inclusion.html>
347    fn winding_number(&self, point: Point<T>) -> isize {
348        let ext = self.exterior.winding_number(point);
349        let int: isize = self.interiors.iter().map(|p| p.winding_number(point)).sum();
350        ext + int
351    }
352}
353
354impl<T> MapPointwise<T> for Polygon<T>
355where
356    T: CoordinateType,
357{
358    fn transform<F: Fn(Point<T>) -> Point<T>>(&self, tf: F) -> Self {
359        Polygon {
360            exterior: self.exterior.transform(&tf),
361            interiors: self.interiors.iter().map(|p| p.transform(&tf)).collect(),
362        }
363    }
364}
365
366impl<T, A> DoubledOrientedArea<A> for Polygon<T>
367where
368    T: CoordinateType,
369    A: Num + From<T>,
370{
371    /// Calculates the doubled oriented area.
372    ///
373    /// Using doubled area allows to compute in the integers because the area
374    /// of a polygon with integer coordinates is either integer or half-integer.
375    ///
376    /// The area will be positive if the vertices are listed counter-clockwise,
377    /// negative otherwise.
378    ///
379    /// Complexity: O(n)
380    ///
381    /// # Examples
382    ///
383    /// ```
384    /// use iron_shapes::polygon::{Polygon, DoubledOrientedArea};
385    /// let coords = vec![(0, 0), (3, 0), (3, 1)];
386    ///
387    /// let poly = Polygon::new(coords);
388    ///
389    /// let area: i64 = poly.area_doubled_oriented();
390    /// assert_eq!(area, 3);
391    ///
392    /// ```
393    fn area_doubled_oriented(&self) -> A {
394        let ext: A = self.exterior.area_doubled_oriented();
395        let int = self
396            .interiors
397            .iter()
398            .map(|p| p.area_doubled_oriented())
399            .fold(A::zero(), |a, b| a + b);
400        ext + int
401    }
402}
403
404impl<T: CoordinateType + NumCast, Dst: CoordinateType + NumCast> TryCastCoord<T, Dst>
405    for Polygon<T>
406{
407    type Output = Polygon<Dst>;
408
409    fn try_cast(&self) -> Option<Self::Output> {
410        if let Some(new_hull) = self.exterior.try_cast() {
411            let new_holes: Vec<_> = self
412                .interiors
413                .iter()
414                .map(|hole| hole.try_cast())
415                .while_some()
416                .collect();
417            if new_holes.len() == self.interiors.len() {
418                Some(Polygon::new_with_holes(new_hull, new_holes))
419            } else {
420                // Some wholes could not be casted.
421                None
422            }
423        } else {
424            // The hull could not be casted.
425            None
426        }
427    }
428}
429
430#[cfg(test)]
431mod tests {
432    use crate::prelude::*;
433
434    #[test]
435    fn test_create_polygon() {
436        let coords = vec![(0, 0), (1, 0), (1, 1), (0, 1)];
437
438        let poly: Polygon<i32> = (&coords).into();
439
440        assert_eq!(poly.exterior.len(), coords.len());
441    }
442
443    #[test]
444    fn test_area() {
445        let coords = vec![(0, 0), (1, 0), (1, 1), (0, 1)];
446
447        let poly: Polygon<i32> = (&coords).into();
448
449        let doubled_area: i64 = poly.area_doubled_oriented();
450        assert_eq!(doubled_area, 2);
451    }
452
453    #[test]
454    fn test_orientation() {
455        use crate::types::Orientation;
456        let coords = vec![(0, 0), (1, 0), (1, 1)];
457
458        let poly: Polygon<i32> = (&coords).into();
459
460        assert_eq!(poly.orientation::<i64>(), Orientation::CounterClockWise);
461    }
462
463    #[test]
464    fn test_bounding_box() {
465        use crate::rect::Rect;
466        use crate::traits::TryBoundingBox;
467        let coords = vec![(1, 0), (-1, -2), (1, 0), (42, 37)];
468
469        let poly: Polygon<i32> = (&coords).into();
470
471        assert_eq!(poly.try_bounding_box(), Some(Rect::new((-1, -2), (42, 37))))
472    }
473
474    #[test]
475    fn test_winding_number() {
476        let coords = vec![(0, 0), (2, 0), (2, 2), (0, 2)];
477
478        let poly: Polygon<i32> = (&coords).into();
479
480        assert_eq!(poly.winding_number(Point::new(1, 1)), 1);
481        assert_eq!(poly.winding_number(Point::new(-1, -1)), 0);
482        assert_eq!(poly.winding_number(Point::new(10, 10)), 0);
483
484        // Test point on edges
485        assert_eq!(poly.winding_number(Point::new(1, 0)), 1); // Bottom edge
486        assert_eq!(poly.winding_number(Point::new(2, 1)), 0); // Right edge
487        assert_eq!(poly.winding_number(Point::new(1, 2)), 0); // Top edge
488        assert_eq!(poly.winding_number(Point::new(0, 1)), 1); // Left edge
489
490        // Test point on vertex.
491        assert_eq!(poly.winding_number(Point::new(0, 0)), 1);
492        assert_eq!(poly.winding_number(Point::new(2, 0)), 0);
493        assert_eq!(poly.winding_number(Point::new(2, 2)), 0);
494        assert_eq!(poly.winding_number(Point::new(0, 2)), 0);
495    }
496
497    #[test]
498    fn test_convex_hull() {
499        let poly = Polygon::new(vec![(0, 0), (1, 1), (2, 0), (2, 2), (0, 2)]);
500        let exp_hull = Polygon::new(vec![(0, 0), (2, 0), (2, 2), (0, 2)])
501            .exterior
502            .normalized();
503        assert_eq!(poly.convex_hull(), exp_hull);
504
505        let poly = Polygon::new(vec![(1, 0), (2, 1), (1, 2), (1, 1), (0, 1)]);
506        let exp_hull = Polygon::new(vec![(1, 0), (2, 1), (1, 2), (0, 1)])
507            .exterior
508            .normalized();
509        assert_eq!(poly.convex_hull(), exp_hull);
510
511        // Degenerate case. All x coordinates are the same.
512        let poly = Polygon::new(vec![(0, 0), (0, 1), (0, 7)]);
513        let exp_hull = Polygon::new(vec![(0, 0), (0, 7)]).exterior.normalized();
514        assert_eq!(poly.convex_hull(), exp_hull);
515
516        // Degenerate case. All y coordinates are the same.
517        let poly = Polygon::new(vec![(0, 0), (1, 0), (7, 0)]);
518        let exp_hull = Polygon::new(vec![(0, 0), (7, 0)]).exterior.normalized();
519        assert_eq!(poly.convex_hull(), exp_hull);
520
521        // Degenerate case. All points are equal.
522        let poly4 = Polygon::new(vec![(0, 0), (0, 0), (0, 0)]);
523        let exp_hull4 = Polygon::new(vec![(0, 0)]).exterior.normalized();
524        assert_eq!(poly4.convex_hull(), exp_hull4);
525    }
526
527    #[test]
528    fn test_normalized_eq() {
529        let poly1 = Polygon::new(vec![(0, 0), (1, 0), (1, 1)]);
530        let poly2 = Polygon::new(vec![(1, 1), (0, 0), (1, 0)]);
531        let poly3 = Polygon::new(vec![(0, 0), (1, 0), (1, 2)]);
532
533        assert_eq!(poly1, poly2);
534        assert_eq!(poly2, poly1);
535
536        assert_ne!(poly1, poly3)
537    }
538}
iron_shapes/polygon.rs

iron_shapes/
polygon.rs
