diff options
Diffstat (limited to 'src/math/polygon/mod.rs')
| -rw-r--r-- | src/math/polygon/mod.rs | 341 |
1 files changed, 341 insertions, 0 deletions
diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs new file mode 100644 index 0000000..cda1f2a --- /dev/null +++ b/src/math/polygon/mod.rs @@ -0,0 +1,341 @@ +//! Contains functions and structures to help with operations on polygons. + +pub mod polygon_graph; +pub mod triangulate; + +pub use polygon_graph::*; +pub use triangulate::*; + +use super::{LineSegment, Surface, TripletOrientation, Vec2}; +use crate::math; +use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; +use num_traits::Zero; +use serde::{Deserialize, Serialize}; +use std::ops::Neg; + +#[derive(Debug, Deserialize, Serialize)] +// TODO: Support polygons with holes +pub struct Polygon<T: Scalar + Copy> { + pub corners: Vec<Vec2<T>>, +} + +impl<T: Scalar + Copy> Polygon<T> { + pub fn new(corners: Vec<Vec2<T>>) -> Self { + Self { corners } + } + + /// Check whether a point is inside a polygon or not. If a point lies on an edge, it also + /// counts as inside the polygon. + + /// Join this polygon with another, ensuring the area of the two stays the same, but the + /// overlap is not doubled, but instead joined into one. + /// Returns the Polygons themselves, if there is no overlap + pub fn unite(self, other: Polygon<T>) -> Vec<Polygon<T>> + where + T: RealField, + { + let mut graph = PolygonGraph::from_polygon(&self); + graph.add_all(&other); + + // TODO: Make bounding box support multiple polygons + vec![graph.bounding_polygon()] + } +} + +impl< + T: Scalar + + Copy + + ClosedSub + + ClosedMul + + ClosedDiv + + Neg<Output = T> + + PartialOrd + + RealField + + Zero, + > Surface<T> for Polygon<T> +{ + fn contains_point(&self, p: &Vec2<T>) -> bool { + let n = self.corners.len(); + + let a = self.corners[n - 1]; + let mut b = self.corners[n - 2]; + let mut ax; + let mut ay = a.y - p.y; + let mut bx = b.x - p.x; + let mut by = b.y - p.y; + + let mut lup = by > ay; + for i in 0..n { + // ax = bx; + ay = by; + b = self.corners[i]; + bx = b.x - p.x; + by = b.y - p.y; + + if ay == by { + continue; + } + lup = by > ay; + } + + let mut depth = 0; + for i in 0..n { + ax = bx; + ay = by; + let b = &self.corners[i]; + bx = b.x - p.x; + by = b.y - p.y; + + if ay < T::zero() && by < T::zero() { + // both "up" or both "down" + continue; + } + if ay > T::zero() && by > T::zero() { + // both "up" or both "down" + continue; + } + if ax < T::zero() && bx < T::zero() { + // both points on the left + continue; + } + + if ay == by && (if ax < bx { ax } else { bx }) <= T::zero() { + return true; + } + if ay == by { + continue; + } + + let lx = ax + (((bx - ax) * -ay) / (by - ay)); + if lx == T::zero() { + // point on edge + return true; + } + if lx > T::zero() { + depth += 1; + } + if ay == T::zero() && lup && by > ay { + // hit vertex, both up + depth -= 1; + } + if ay == T::zero() && !lup && by < ay { + // hit vertex, both down + depth -= 1; + } + + lup = by > ay; + } + + (depth & 1) == 1 + } + + fn contains_line_segment(&self, line_segment: &LineSegment<T>) -> bool { + /* In case at least one of the points is not contained by the polygon, the line cannot lie + * inside of the polygon in its entirety. + */ + if !self.contains_point(&line_segment.start) || !self.contains_point(&line_segment.end) { + return false; + } + + /* Both end-points are inside the polygon. */ + + /* In case the an endpoint of the line segment is equal to a corner of the polygon, it's + * not enough to merely check one edge, since if the corner is reflex, the segment may + * still be inside, eventhough its similar to the outwards pointing normal of one edge, but + * may be to the inside of the other edge. + */ + let mut start_looks_inside = false; + let mut end_looks_inside = false; + /* Helper function that checks if a point p, when starting from the given corner c is in a + * direction so that considering both edges that are connected to c, the point is in the + * direction of the inside of the polygon. + */ + let corner_vec_pointing_inside = |p: Vec2<T>, c: usize| { + let prev = (c + self.corners.len() - 1) % self.corners.len(); + let next = (c + 1) % self.corners.len(); + + let edge_angle = + math::triplet_angle(self.corners[prev], self.corners[c], self.corners[next]); + let vec_angle = math::triplet_angle(self.corners[prev], self.corners[c], p); + + vec_angle == T::zero() || vec_angle >= edge_angle + }; + + for c in 0..self.corners.len() { + if line_segment.start == self.corners[c] { + start_looks_inside = corner_vec_pointing_inside(line_segment.end, c); + if !start_looks_inside { + return false; + } + } + if line_segment.end == self.corners[c] { + end_looks_inside = corner_vec_pointing_inside(line_segment.start, c); + if !end_looks_inside { + return false; + } + } + } + + if start_looks_inside && end_looks_inside { + return true; + } + + /* Check the intersections of the line segment with all polygon edges and see if it is + * piercing through any of them. + */ + for c in 0..self.corners.len() { + let next = (c + 1) % self.corners.len(); + + let current_edge = LineSegment::new(self.corners[c], self.corners[next]); + + if LineSegment::intersect(&line_segment, ¤t_edge) { + let orientation_start = math::triplet_orientation( + current_edge.start, + current_edge.end, + line_segment.start, + ); + let orientation_end = math::triplet_orientation( + current_edge.start, + current_edge.end, + line_segment.end, + ); + match (orientation_start, orientation_end) { + /* If at least one of the points is on the edge, make sure, the line points + * inside of the polygon, not to the outside. + */ + (TripletOrientation::Collinear, o) => { + if !start_looks_inside && o == TripletOrientation::Clockwise { + return false; + } + } + (o, TripletOrientation::Collinear) => { + if !end_looks_inside && o == TripletOrientation::Clockwise { + return false; + } + } + /* Start and endpoint are on different sides of the edge, therefore the line + * must be partially outside. + */ + _ => return false, + } + } + } + + true + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn polygon_contains() { + let polygon = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(-1., 1.), + Vec2::new(0., 2.), + Vec2::new(1., 3.), + Vec2::new(3., 1.5), + Vec2::new(2., 0.), + Vec2::new(1., 1.), + ]); + + assert!(!polygon.contains_point(&Vec2::new(1., -2.))); + assert!(!polygon.contains_point(&Vec2::new(-1., 0.5))); + assert!(polygon.contains_point(&Vec2::new(0., 0.5))); + assert!(polygon.contains_point(&Vec2::new(0.5, 1.))); + assert!(polygon.contains_point(&Vec2::new(0.5, 1.5))); + assert!(!polygon.contains_point(&Vec2::new(-2., 1.9))); + assert!(!polygon.contains_point(&Vec2::new(0., 3.))); + assert!(polygon.contains_point(&Vec2::new(1., 3.))); + } + + #[test] + fn contains_line_segment() { + let polygon = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(0., 4.5), + Vec2::new(6.5, 4.5), + Vec2::new(5.5, 0.), + Vec2::new(5.5, 3.), + Vec2::new(1.5, 3.), + Vec2::new(1.5, 1.), + Vec2::new(2., 0.5), + Vec2::new(4., 2.), + Vec2::new(4., 0.), + ]); + + /* NOTE: From now on, inside means inside the polygon, but might be on an edge or on a + * corner point, really inside means inside and not on an edge. + */ + + // Start point really inside, end point really inside. Line not completely inside. + assert!(!polygon + .contains_line_segment(&LineSegment::new(Vec2::new(2.5, 0.5), Vec2::new(0.5, 2.5)))); + + // Start point on edge, end point on corner, line completely outside. + assert!(!polygon + .contains_line_segment(&LineSegment::new(Vec2::new(1.5, 2.), Vec2::new(4., 2.)))); + + // Start point on edge, end point on edge, line inside. + assert!(polygon + .contains_line_segment(&LineSegment::new(Vec2::new(3.5, 3.), Vec2::new(3.5, 4.5)))); + + // Start point on corner, end point on corner, line inside. + assert!(polygon + .contains_line_segment(&LineSegment::new(Vec2::new(5.5, 3.), Vec2::new(6.5, 4.5)))); + + // Start point really inside, end point on edge. Line not inside. + assert!(!polygon + .contains_line_segment(&LineSegment::new(Vec2::new(3.5, 0.5), Vec2::new(5.5, 0.5)))); + + // Start point and endpoint outside. Line completely outside. + assert!(!polygon + .contains_line_segment(&LineSegment::new(Vec2::new(7.0, 0.), Vec2::new(7.5, 1.)))); + + // Start point on vertex, pointing in same dir as one of the adjacent edge normals, + // completely inside. + assert!( + polygon.contains_line_segment(&LineSegment::new(Vec2::new(2., 0.5), Vec2::new(4., 0.))) + ); + + // Start and end point on vertex, not pointing in the dir of adjacent edge normals, + // not completely inside. + assert!( + !polygon.contains_line_segment(&LineSegment::new(Vec2::new(4., 2.), Vec2::new(0., 0.))) + ); + } + + #[test] + fn polygon_union() { + let first = Polygon::new(vec![ + Vec2::new(-2., 1.), + Vec2::new(-0.5, 2.5), + Vec2::new(2., 2.), + Vec2::new(0.5, 1.5), + Vec2::new(1., 0.), + Vec2::new(-0.5, 1.), + ]); + + let second = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(-2., 2.), + Vec2::new(3., 2.), + Vec2::new(1.5, 0.), + ]); + + let union = first.unite(second); + assert_eq!(union.len(), 1); + let union = &union[0]; + + println!("Union of the two polygons: {:?}", union); + + assert_eq!(union.corners.len(), 11); + assert!(union + .corners + .iter() + .find(|&p| p.x == 0. && p.y == 0.) + .is_some()); + } +} |