From 58ca374fab6dd90c4d7415bdcc98add002274894 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 11:23:16 +0100 Subject: Move polygon functions into own mod The math module was starting to be mostly polygon files and functions, so those got their own subfolder to make the math module less of a mess. --- src/math/polygon/triangulate.rs | 13 +++++++++++++ 1 file changed, 13 insertions(+) create mode 100644 src/math/polygon/triangulate.rs (limited to 'src/math/polygon/triangulate.rs') diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs new file mode 100644 index 0000000..4860518 --- /dev/null +++ b/src/math/polygon/triangulate.rs @@ -0,0 +1,13 @@ +//! Module for turning a polygon into a number of non-overlapping triangles. + +use super::Polygon; +use crate::math::Triangle; +use nalgebra::Scalar; + +/// 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(_polygon: &Polygon) -> Vec> { + unimplemented!() +} -- cgit v1.2.3-70-g09d2 From 1363c7713d19bd733a97dff5727827cf7684a27b Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Mon, 23 Nov 2020 21:06:56 +0100 Subject: Add ear clipping algorithm --- src/math/polygon/mod.rs | 93 +++++++++++++++++++++++++++++++- src/math/polygon/triangulate.rs | 114 ++++++++++++++++++++++++++++++++++++++-- 2 files changed, 201 insertions(+), 6 deletions(-) (limited to 'src/math/polygon/triangulate.rs') 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) -> 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 } } @@ -150,6 +195,50 @@ mod test { 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.)))); + } + #[test] fn polygon_union() { let first = Polygon::new(vec![ 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(polygon: &Polygon, 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(_polygon: &Polygon) -> Vec> { - unimplemented!() +pub fn triangulate(mut polygon: Polygon) -> Vec> +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 } -- cgit v1.2.3-70-g09d2 From 3b0c99351da92410bbfaba233e40376b767cb64e Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Mon, 23 Nov 2020 23:25:45 +0100 Subject: Add triangulation function --- src/math/polygon/mod.rs | 33 ++++++++++++++++++++------------- src/math/polygon/triangulate.rs | 30 ++++++++++++++++++++++++++++++ 2 files changed, 50 insertions(+), 13 deletions(-) (limited to 'src/math/polygon/triangulate.rs') diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs index e19e097..cc89169 100644 --- a/src/math/polygon/mod.rs +++ b/src/math/polygon/mod.rs @@ -42,7 +42,15 @@ impl Polygon { } impl< - T: Scalar + Copy + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd + Zero, + T: Scalar + + Copy + + ClosedSub + + ClosedMul + + ClosedDiv + + Neg + + PartialOrd + + RealField + + Zero, > Surface for Polygon { fn contains_point(&self, p: &Vec2) -> bool { @@ -145,18 +153,11 @@ impl< let prev = (c + self.corners.len() - 1) % self.corners.len(); let next = (c + 1) % self.corners.len(); - let last_edge_orientation = - math::triplet_orientation(self.corners[prev], self.corners[c], p); - let current_edge_orientation = - math::triplet_orientation(self.corners[c], self.corners[next], p); - - if last_edge_orientation == TripletOrientation::Clockwise - && current_edge_orientation == TripletOrientation::Clockwise - { - false - } else { - true - } + 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() { @@ -297,6 +298,12 @@ mod test { 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] diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs index 096a1c6..78dfa03 100644 --- a/src/math/polygon/triangulate.rs +++ b/src/math/polygon/triangulate.rs @@ -117,3 +117,33 @@ where triangles } + +#[cfg(test)] +mod test { + use super::*; + use crate::math::Vec2; + + #[test] + fn triangulate() { + 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.), + ]); + + let triangles = super::triangulate(polygon); + + assert_eq!(triangles.len(), 8); + assert_eq!( + triangles[0], + (Triangle::new(Vec2::new(2., 0.5), Vec2::new(4., 2.), Vec2::new(4., 0.))) + ); + } +} -- cgit v1.2.3-70-g09d2