use crate::intersections::{SegmentIntersectionKind, segment_intersection_kind};
use crate::predicates::{Orientation, orient2d, polygon_orientation};
use crate::primitives::{Point2, PointSegmentRelation, Segment2};
#[derive(Debug, Clone, PartialEq)]
pub struct Polygon2 {
vertices: Vec<Point2>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PolygonBasicValidity {
TooFewVertices,
ConsecutiveDuplicateVertices,
ZeroArea,
Valid,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct PolygonSelfIntersection {
pub edge_a: usize,
pub edge_b: usize,
pub kind: SegmentIntersectionKind,
}
impl Polygon2 {
pub fn new(vertices: Vec<Point2>) -> Self {
Polygon2 { vertices }
}
pub fn vertices(&self) -> &[Point2] {
&self.vertices
}
pub fn len(&self) -> usize {
self.vertices.len()
}
pub fn is_empty(&self) -> bool {
self.vertices.is_empty()
}
pub fn edge(&self, i: usize) -> Segment2 {
let n = self.vertices.len();
Segment2::new(self.vertices[i], self.vertices[(i + 1) % n])
}
pub fn signed_area(&self) -> f64 {
let n = self.vertices.len();
if n < 3 {
return 0.0;
}
let mut sum = 0.0;
for i in 0..n {
let j = (i + 1) % n;
sum += self.vertices[i].x() * self.vertices[j].y()
- self.vertices[j].x() * self.vertices[i].y();
}
sum * 0.5
}
pub fn orientation(&self) -> Orientation {
polygon_orientation(&self.vertices)
}
pub fn basic_validity(&self) -> PolygonBasicValidity {
let n = self.vertices.len();
if n < 3 {
return PolygonBasicValidity::TooFewVertices;
}
for i in 0..n {
let j = (i + 1) % n;
if self.vertices[i] == self.vertices[j] {
return PolygonBasicValidity::ConsecutiveDuplicateVertices;
}
}
if self.orientation() == Orientation::Collinear {
return PolygonBasicValidity::ZeroArea;
}
PolygonBasicValidity::Valid
}
pub fn find_self_intersection(&self) -> Option<PolygonSelfIntersection> {
let n = self.vertices.len();
if n < 2 {
return None;
}
for i in 0..n {
for j in (i + 1)..n {
let adjacent = j == i + 1 || (i == 0 && j == n - 1);
if adjacent {
continue;
}
let kind = segment_intersection_kind(self.edge(i), self.edge(j));
if kind != SegmentIntersectionKind::None {
return Some(PolygonSelfIntersection {
edge_a: i,
edge_b: j,
kind,
});
}
}
}
None
}
pub fn relation_to(&self, p: Point2) -> PointPolygonRelation {
let n = self.vertices.len();
let mut inside = false;
for i in 0..n {
let edge = self.edge(i);
if edge.relation_to(p) != PointSegmentRelation::NotOnSegment {
return PointPolygonRelation::OnBoundary;
}
let (a, b) = (edge.a(), edge.b());
let straddles = (a.y() > p.y()) != (b.y() > p.y());
if !straddles {
continue;
}
let upward = b.y() > a.y();
let side = orient2d(a, b, p);
let crosses_to_the_right = if upward {
side == Orientation::CounterClockwise
} else {
side == Orientation::Clockwise
};
if crosses_to_the_right {
inside = !inside;
}
}
if inside {
PointPolygonRelation::Inside
} else {
PointPolygonRelation::Outside
}
}
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PointPolygonRelation {
Inside,
OnBoundary,
Outside,
}
#[cfg(test)]
mod tests {
use super::*;
fn p(x: f64, y: f64) -> Point2 {
Point2::new(x, y).unwrap()
}
fn square_ccw() -> Polygon2 {
Polygon2::new(vec![p(0.0, 0.0), p(4.0, 0.0), p(4.0, 4.0), p(0.0, 4.0)])
}
#[test]
fn signed_area_ccw_positive_cw_negative() {
let ccw = square_ccw();
assert_eq!(ccw.signed_area(), 16.0);
let cw = Polygon2::new(vec![p(0.0, 0.0), p(0.0, 4.0), p(4.0, 4.0), p(4.0, 0.0)]);
assert_eq!(cw.signed_area(), -16.0);
}
#[test]
fn orientation_matches_winding() {
assert_eq!(square_ccw().orientation(), Orientation::CounterClockwise);
}
#[test]
fn basic_validity_too_few_vertices() {
assert_eq!(
Polygon2::new(vec![]).basic_validity(),
PolygonBasicValidity::TooFewVertices
);
assert_eq!(
Polygon2::new(vec![p(0.0, 0.0), p(1.0, 1.0)]).basic_validity(),
PolygonBasicValidity::TooFewVertices
);
}
#[test]
fn basic_validity_consecutive_duplicate() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)]);
assert_eq!(
poly.basic_validity(),
PolygonBasicValidity::ConsecutiveDuplicateVertices
);
}
#[test]
fn basic_validity_wraparound_duplicate() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0), p(0.0, 0.0)]);
assert_eq!(
poly.basic_validity(),
PolygonBasicValidity::ConsecutiveDuplicateVertices
);
}
#[test]
fn basic_validity_zero_area_collinear() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0), p(2.0, 0.0)]);
assert_eq!(poly.basic_validity(), PolygonBasicValidity::ZeroArea);
}
#[test]
fn basic_validity_valid_triangle() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)]);
assert_eq!(poly.basic_validity(), PolygonBasicValidity::Valid);
}
#[test]
fn triangle_never_self_intersects() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0), p(0.0, 1.0)]);
assert_eq!(poly.find_self_intersection(), None);
}
#[test]
fn simple_square_does_not_self_intersect() {
assert_eq!(square_ccw().find_self_intersection(), None);
}
#[test]
fn bowtie_quadrilateral_self_intersects() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(4.0, 4.0), p(4.0, 0.0), p(0.0, 4.0)]);
let found = poly
.find_self_intersection()
.expect("bowtie must self-intersect");
assert_eq!(found.edge_a, 0);
assert_eq!(found.edge_b, 2);
assert_eq!(found.kind, SegmentIntersectionKind::Proper);
}
#[test]
fn adjacent_edges_shared_vertex_is_not_reported() {
assert_eq!(square_ccw().find_self_intersection(), None);
let triangle = Polygon2::new(vec![p(0.0, 0.0), p(1.0, 0.0), p(0.5, 1.0)]);
assert_eq!(triangle.find_self_intersection(), None);
}
#[test]
fn edge_on_single_vertex_polygon_is_a_degenerate_zero_length_segment_not_a_panic() {
let v = p(3.0, 4.0);
let poly = Polygon2::new(vec![v]);
assert_eq!(poly.edge(0), Segment2::new(v, v));
}
#[test]
fn relation_to_convex_square() {
let poly = square_ccw();
assert_eq!(poly.relation_to(p(2.0, 2.0)), PointPolygonRelation::Inside);
assert_eq!(
poly.relation_to(p(0.0, 0.0)),
PointPolygonRelation::OnBoundary
);
assert_eq!(
poly.relation_to(p(2.0, 0.0)),
PointPolygonRelation::OnBoundary
);
assert_eq!(
poly.relation_to(p(4.0, 2.0)),
PointPolygonRelation::OnBoundary
);
assert_eq!(
poly.relation_to(p(-1.0, 2.0)),
PointPolygonRelation::Outside
);
assert_eq!(poly.relation_to(p(5.0, 5.0)), PointPolygonRelation::Outside);
}
#[test]
fn relation_to_does_not_care_about_winding() {
let ccw = square_ccw();
let cw = Polygon2::new(vec![p(0.0, 0.0), p(0.0, 4.0), p(4.0, 4.0), p(4.0, 0.0)]);
assert_eq!(ccw.relation_to(p(2.0, 2.0)), PointPolygonRelation::Inside);
assert_eq!(cw.relation_to(p(2.0, 2.0)), PointPolygonRelation::Inside);
}
#[test]
fn relation_to_non_convex_l_shape() {
let poly = Polygon2::new(vec![
p(0.0, 0.0),
p(4.0, 0.0),
p(4.0, 2.0),
p(2.0, 2.0),
p(2.0, 4.0),
p(0.0, 4.0),
]);
assert_eq!(poly.relation_to(p(1.0, 1.0)), PointPolygonRelation::Inside);
assert_eq!(poly.relation_to(p(3.0, 3.0)), PointPolygonRelation::Outside);
assert_eq!(
poly.relation_to(p(2.0, 2.0)),
PointPolygonRelation::OnBoundary
);
}
#[test]
fn relation_to_point_exactly_on_a_horizontal_ray_through_a_vertex() {
let poly = Polygon2::new(vec![
p(0.0, 0.0),
p(4.0, 2.0),
p(8.0, 0.0),
p(8.0, 4.0),
p(0.0, 4.0),
]);
assert_eq!(
poly.relation_to(p(-1.0, 2.0)),
PointPolygonRelation::Outside
);
assert_eq!(poly.relation_to(p(5.0, 3.0)), PointPolygonRelation::Inside);
}
#[test]
fn relation_to_degenerate_single_vertex_polygon() {
let v = p(3.0, 4.0);
let poly = Polygon2::new(vec![v]);
assert_eq!(poly.relation_to(v), PointPolygonRelation::OnBoundary);
assert_eq!(poly.relation_to(p(0.0, 0.0)), PointPolygonRelation::Outside);
}
#[test]
fn relation_to_degenerate_collinear_polygon_has_no_interior() {
let poly = Polygon2::new(vec![p(0.0, 0.0), p(2.0, 0.0), p(4.0, 0.0)]);
assert_eq!(poly.basic_validity(), PolygonBasicValidity::ZeroArea);
assert_eq!(
poly.relation_to(p(1.0, 0.0)),
PointPolygonRelation::OnBoundary
);
assert_eq!(poly.relation_to(p(1.0, 1.0)), PointPolygonRelation::Outside);
}
}