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

use num_traits::{Float, Signed};
use {CoordinateType, LineString, Point};

/// A representation of an area. Its outer boundary is represented by a [`LineString`](struct.LineString.html) that is both closed and simple
///
/// It has one exterior *ring* or *shell*, and zero or more interior rings, representing holes.
///
/// # Examples
///
/// Polygons can be created from collections of `Point`-like objects, such as arrays or tuples:
///
/// ```
/// use geo_types::{Point, LineString, Polygon};
/// let poly1 = Polygon::new(vec![[0., 0.], [10., 0.]].into(), vec![]);
/// let poly2 = Polygon::new(vec![(0., 0.), (10., 0.)].into(), vec![]);
/// ```
#[derive(PartialEq, Clone, Debug)]
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Polygon<T>
where
    T: CoordinateType,
{
    pub exterior: LineString<T>,
    pub interiors: Vec<LineString<T>>,
}

impl<T> Polygon<T>
where
    T: CoordinateType,
{
    /// Creates a new polygon.
    ///
    /// # Examples
    ///
    /// ```
    /// use geo_types::{Coordinate, LineString, Polygon};
    ///
    /// let exterior = LineString(vec![
    ///     Coordinate { x: 0., y: 0. },
    ///     Coordinate { x: 1., y: 1. },
    ///     Coordinate { x: 1., y: 0. },
    ///     Coordinate { x: 0., y: 0. },
    /// ]);
    /// let interiors = vec![LineString(vec![
    ///     Coordinate { x: 0.1, y: 0.1 },
    ///     Coordinate { x: 0.9, y: 0.9 },
    ///     Coordinate { x: 0.9, y: 0.1 },
    ///     Coordinate { x: 0.1, y: 0.1 },
    /// ])];
    /// let p = Polygon::new(exterior.clone(), interiors.clone());
    /// assert_eq!(p.exterior, exterior);
    /// assert_eq!(p.interiors, interiors);
    /// ```
    pub fn new(exterior: LineString<T>, interiors: Vec<LineString<T>>) -> Polygon<T> {
        Polygon {
            exterior,
            interiors,
        }
    }
    /// Wrap-around previous-vertex
    fn previous_vertex(&self, current_vertex: &usize) -> usize
    where
        T: Float,
    {
        (current_vertex + (self.exterior.0.len() - 1) - 1) % (self.exterior.0.len() - 1)
    }
}

// used to check the sign of a vec of floats
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
enum ListSign {
    Empty,
    Positive,
    Negative,
    Mixed,
}

impl<T> Polygon<T>
where
    T: Float + Signed,
{
    /// Determine whether a Polygon is convex
    // For each consecutive pair of edges of the polygon (each triplet of points),
    // compute the z-component of the cross product of the vectors defined by the
    // edges pointing towards the points in increasing order.
    // Take the cross product of these vectors
    // The polygon is convex if the z-components of the cross products are either
    // all positive or all negative. Otherwise, the polygon is non-convex.
    // see: http://stackoverflow.com/a/1881201/416626
    pub fn is_convex(&self) -> bool {
        let convex = self
            .exterior
            .0
            .iter()
            .enumerate()
            .map(|(idx, _)| {
                let prev_1 = self.previous_vertex(&idx);
                let prev_2 = self.previous_vertex(&prev_1);
                Point(self.exterior.0[prev_2]).cross_prod(
                    Point(self.exterior.0[prev_1]),
                    Point(self.exterior.0[idx])
                )
            })
            // accumulate and check cross-product result signs in a single pass
            // positive implies ccw convexity, negative implies cw convexity
            // anything else implies non-convexity
            .fold(ListSign::Empty, |acc, n| {
                match (acc, n.is_positive()) {
                    (ListSign::Empty, true) | (ListSign::Positive, true) => ListSign::Positive,
                    (ListSign::Empty, false) | (ListSign::Negative, false) => ListSign::Negative,
                    _ => ListSign::Mixed
                }
            });
        convex != ListSign::Mixed
    }
}