diff options
Diffstat (limited to 'src/math/polygon')
| -rw-r--r-- | src/math/polygon/mod.rs | 93 | ||||
| -rw-r--r-- | src/math/polygon/triangulate.rs | 114 |
2 files changed, 201 insertions, 6 deletions
diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs index d351ec7..baa1e6d 100644 --- a/src/math/polygon/mod.rs +++ b/src/math/polygon/mod.rs @@ -6,7 +6,8 @@ pub mod triangulate; pub use polygon_graph::*; pub use triangulate::*; -use super::{LineSegment, Surface, Vec2}; +use super::{LineSegment, Surface, TripletOrientation, Vec2}; +use crate::math; use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; use num_traits::Zero; use std::ops::Neg; @@ -120,7 +121,51 @@ impl< } fn contains_line_segment(&self, line_segment: &LineSegment<T>) -> bool { - unimplemented!() + /* 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. */ + + /* 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) | (o, TripletOrientation::Collinear) => { + if 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 } } @@ -151,6 +196,50 @@ mod test { } #[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.)))); + } + + #[test] fn polygon_union() { let first = Polygon::new(vec![ Vec2::new(-2., 1.), diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs index 4860518..096a1c6 100644 --- a/src/math/polygon/triangulate.rs +++ b/src/math/polygon/triangulate.rs @@ -1,13 +1,119 @@ //! Module for turning a polygon into a number of non-overlapping triangles. use super::Polygon; -use crate::math::Triangle; -use nalgebra::Scalar; +use crate::math::{self, LineSegment, Surface, Triangle}; +use nalgebra::{RealField, Scalar}; + +/// Type that saves the flags that match a corner in a space efficient manner. +type Flags = u8; + +/// Tells the algorithm that this corner of the polygon is an ear. An ear means the adjacent corners +/// form a triangle with this corner of which the area is entirely contained by the polygon itself. +const FLAG_EAR: Flags = 0b0000_0001; +/// Tells the algorithm that this corner is convex, meaning its internal angle is less than Pi. +/// Useful, because this is a necessary condition for earness. False if the vertex is reflex. +// TODO: The convex flag is a remnant from the previous algorithm, but currently it's not being +// used. Consider removing it entirely. +const FLAG_CONVEX: Flags = 0b0000_0010; + +fn flag_corner<T: Scalar + Copy>(polygon: &Polygon<T>, corner: usize) -> Flags +where + T: RealField, +{ + // First, check if it is convex. If it is not, it can also not be an ear. + let prev = (corner + polygon.corners.len() - 1) % polygon.corners.len(); + let next = (corner + 1) % polygon.corners.len(); + + /* Since the angle is also in counterclockwise direction, like the polygon itself, the corner + * is convex if and only if the angle is **not**. + */ + if math::triplet_angle( + polygon.corners[prev], + polygon.corners[corner], + polygon.corners[next], + ) < T::pi() + { + // The corner is reflex. + return 0b0; + } + + // The corner is convex, check if it is also an ear. + if polygon.contains_line_segment(&LineSegment::new( + polygon.corners[prev], + polygon.corners[next], + )) { + // Corner is an ear. + FLAG_EAR | FLAG_CONVEX + } else { + // Corner is not an ear. + FLAG_CONVEX + } +} /// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) /// to find an explanation of what exactly is happening. /// Currently only handles simple polygons, but once the polygon struct supports holes must be /// extended to also support those. -pub fn triangulate<T: Scalar + Copy>(_polygon: &Polygon<T>) -> Vec<Triangle<T>> { - unimplemented!() +pub fn triangulate<T: Scalar + Copy>(mut polygon: Polygon<T>) -> Vec<Triangle<T>> +where + T: RealField, +{ + assert!(polygon.corners.len() >= 3); + /* Information about the corner of the polygon. See the flags constant for information about + * what the bits mean. + */ + let mut flags = Vec::with_capacity(polygon.corners.len()); + for c in 0..polygon.corners.len() { + flags.push(flag_corner(&polygon, c)); + } + + let mut triangles = Vec::with_capacity(polygon.corners.len() - 2); + // Clip ears until there's only the last triangle left. + /* NOTE: This could be changed to > 2 and the last triangle would be pushed inside the loop, + * because it is also detected as an ear, however this is more logical to the original idea + * imo. + */ + while polygon.corners.len() > 3 { + // Find the ear with the highest index. + let ear = flags + .iter() + .rposition(|&x| (x & FLAG_EAR) != 0) + .expect("Polygon has more than three vertices, but no ear."); + + // Add the ear's triangle to the list. + { + let prev = (ear + polygon.corners.len() - 1) % polygon.corners.len(); + let next = (ear + 1) % polygon.corners.len(); + triangles.push(Triangle::new( + polygon.corners[prev], + polygon.corners[ear], + polygon.corners[next], + )); + + // Remove the ear from the polygon and the flag list. + polygon.corners.remove(ear); + flags.remove(ear); + } + + // Reassess the status of the two adjacent points. Notice that since the ear was removed, + // their array positions have changed. + let prev = if ear == 0 || ear == polygon.corners.len() { + polygon.corners.len() - 1 + } else { + ear - 1 + }; + let next = if ear == polygon.corners.len() { 0 } else { ear }; + + flags[prev] = flag_corner(&polygon, prev); + flags[next] = flag_corner(&polygon, next); + } + + // Push the remaining triangle into the list. + triangles.push(Triangle::new( + polygon.corners[0], + polygon.corners[1], + polygon.corners[2], + )); + + triangles } |