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
use num_traits::{Float, Signed};
use {CoordinateType, LineString, Point, Rect};
/// 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
}
}
impl<T: CoordinateType> From<Rect<T>> for Polygon<T> {
fn from(r: Rect<T>) -> Polygon<T> {
Polygon::new(
vec![
(r.min.x, r.min.y),
(r.max.x, r.min.y),
(r.max.x, r.max.y),
(r.min.x, r.max.y),
(r.min.x, r.min.y),
]
.into(),
Vec::new(),
)
}
}