From d7d90e8b3615db38d1af238ac9c8193c283ca156 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 00:36:32 +0100 Subject: Add triangle struct and triangulation template --- src/math/line_segment.rs | 107 ++----------------------------- src/math/mod.rs | 4 ++ src/math/triangle.rs | 161 +++++++++++++++++++++++++++++++++++++++++++++++ src/math/triangulate.rs | 12 ++++ 4 files changed, 183 insertions(+), 101 deletions(-) create mode 100644 src/math/triangle.rs create mode 100644 src/math/triangulate.rs (limited to 'src') diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index e6ca70f..244b0af 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -1,4 +1,4 @@ -use super::{Rect, Vec2}; +use super::{Rect, TripletOrientation, Vec2}; use alga::general::{ClosedDiv, ClosedMul, ClosedSub}; use nalgebra::{RealField, Scalar}; use num_traits::Zero; @@ -50,10 +50,10 @@ impl LineSegment { */ // Cache the necessary orientations. - let ls1_ls2start_orientation = triplet_orientation(ls1.start, ls1.end, ls2.start); - let ls1_ls2end_orientation = triplet_orientation(ls1.start, ls1.end, ls2.end); - let ls2_ls1start_orientation = triplet_orientation(ls2.start, ls2.end, ls1.start); - let ls2_ls1end_orientation = triplet_orientation(ls2.start, ls2.end, ls1.end); + let ls1_ls2start_orientation = super::triplet_orientation(ls1.start, ls1.end, ls2.start); + let ls1_ls2end_orientation = super::triplet_orientation(ls1.start, ls1.end, ls2.end); + let ls2_ls1start_orientation = super::triplet_orientation(ls2.start, ls2.end, ls1.start); + let ls2_ls1end_orientation = super::triplet_orientation(ls2.start, ls2.end, ls1.end); // Check for the first case that wase described (general case). if ls1_ls2start_orientation != ls1_ls2end_orientation @@ -139,7 +139,7 @@ impl LineSegment { assert_eq!( split_points .iter() - .find(|&p| triplet_orientation(self.start, self.end, *p) + .find(|&p| super::triplet_orientation(self.start, self.end, *p) != TripletOrientation::Collinear), None ); @@ -173,76 +173,9 @@ impl LineSegment { } } -#[derive(PartialEq, Eq)] -pub(crate) enum TripletOrientation { - Clockwise, - Counterclockwise, - Collinear, -} - -/// Helper function to determine which direction one would turn to traverse from the first point -/// over the second to the third point. The third option is collinear, in which case the three points -/// are on the same line. -pub(crate) fn triplet_orientation(a: Vec2, b: Vec2, c: Vec2) -> TripletOrientation -where - T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero, -{ - /* Check the slopes of the vector from a to b and b to c. If the slope of ab is greater than - * that of bc, the rotation is clockwise. If ab is smaller than bc it's counterclockwise. If - * they are the same it follows that the three points are collinear. - */ - match (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y) { - q if q > T::zero() => TripletOrientation::Counterclockwise, - q if q < T::zero() => TripletOrientation::Clockwise, - _ => TripletOrientation::Collinear, - } -} - -/// Calculate the angle between three points. Guaranteed to have 0 <= angle < 2Pi. The angle is -/// calculated as the angle between a line from a to b and then from b to c, increasing -/// counterclockwise. -/// -/// # Panics -/// If the length from a to b or the length from b to c is zero. -pub(crate) fn triplet_angle(a: Vec2, b: Vec2, c: Vec2) -> T -where - T: Scalar + Copy + ClosedSub + RealField + Zero, -{ - assert!(a != b); - assert!(b != c); - - // Handle the extreme 0 and 180 degree cases - let orientation = triplet_orientation(a, b, c); - if orientation == TripletOrientation::Collinear { - if LineSegment::new(a, b).contains_collinear(c) - || LineSegment::new(b, c).contains_collinear(a) - { - return T::zero(); - } else { - return T::pi(); - } - } - - // Calculate the vectors out of the points - let ba = a - b; - let bc = c - b; - - // Calculate the angle between 0 and Pi. - let angle = ((ba * bc) / (ba.length() * bc.length())).acos(); - - // Make angle into a full circle angle by looking at the orientation of the triplet. - let angle = match orientation { - TripletOrientation::Counterclockwise => T::pi() + (T::pi() - angle), - _ => angle, - }; - - angle -} - #[cfg(test)] mod test { use super::*; - use std::f64::consts::PI; #[test] fn contains_collinear() { @@ -256,32 +189,4 @@ mod test { assert!(!segment.contains_collinear(Vec2::new(3., 3.))); assert!(!segment.contains_collinear(Vec2::new(-1., 0.))); } - - #[test] - fn triplet_angle() { - assert_eq!( - super::triplet_angle(Vec2::new(0., 0.), Vec2::new(0., -1.), Vec2::new(-1., -1.)), - 1.5 * PI - ); - assert_eq!( - super::triplet_angle(Vec2::new(2., 2.), Vec2::new(0., 0.), Vec2::new(-1., -1.)), - PI - ); - assert_eq!( - super::triplet_angle(Vec2::new(3., 1.), Vec2::new(0., 0.), Vec2::new(6., 2.)), - 0. - ); - assert_eq!( - super::triplet_angle(Vec2::new(3., 1.), Vec2::new(0., 0.), Vec2::new(-6., -2.)), - PI - ); - assert_eq!( - super::triplet_angle(Vec2::new(0., 1.), Vec2::new(0., 2.), Vec2::new(-3., 2.)), - 0.5 * PI - ); - assert_eq!( - super::triplet_angle(Vec2::new(3., 1.), Vec2::new(2., 2.), Vec2::new(0., 2.)), - 0.75 * PI - ); - } } diff --git a/src/math/mod.rs b/src/math/mod.rs index 0b591d7..07bc36b 100644 --- a/src/math/mod.rs +++ b/src/math/mod.rs @@ -2,12 +2,16 @@ pub mod line_segment; pub mod polygon; pub mod polygon_graph; pub mod rect; +pub mod triangle; +pub mod triangulate; pub mod vec2; pub use self::line_segment::*; pub use self::polygon::*; pub use self::polygon_graph::*; pub use self::rect::*; +pub use self::triangle::*; +pub use self::triangulate::*; pub use self::vec2::*; use std::cmp::Ordering; diff --git a/src/math/triangle.rs b/src/math/triangle.rs new file mode 100644 index 0000000..53c7560 --- /dev/null +++ b/src/math/triangle.rs @@ -0,0 +1,161 @@ +use super::{LineSegment, Vec2}; +use alga::general::{ClosedMul, ClosedSub}; +use nalgebra::{RealField, Scalar}; +use num_traits::Zero; + +/// Represents a triangle +pub struct Triangle { + /// The three corners of the triangle. Internally, it is made sure that the corners are always + /// ordered in a counterclockwise manner, to make operations like contains simpler. + corners: [Vec2; 3], +} + +impl Triangle { + /// Create a new Triangle as defined by its three corner points + pub fn new(a: Vec2, b: Vec2, c: Vec2) -> Self + where + T: ClosedSub + ClosedMul + PartialOrd + Zero, + { + // Make sure the three points are in counterclockwise order. + match triplet_orientation(a, b, c) { + TripletOrientation::Counterclockwise => Self { corners: [a, b, c] }, + TripletOrientation::Clockwise => Self { corners: [a, c, b] }, + TripletOrientation::Collinear => { + warn!( + "Creating triangle without any area: [{:?}, {:?}, {:?}]", + a, b, c + ); + Self { corners: [a, b, c] } + } + } + } + + /// Create a new Triangle from a three-point slice, instead of the three points one after + /// another. + pub fn from_slice(corners: [Vec2; 3]) -> Self + where + T: ClosedSub + ClosedMul + PartialOrd + Zero, + { + Self::new(corners[0], corners[1], corners[2]) + } + + /// Check if the triangle contains a given point. If the point is right on an edge, it still + /// counts as inside it. + pub fn contains_point(&self, point: Vec2) -> bool + where + T: ClosedSub + ClosedMul + PartialOrd + Zero, + { + // Since the points are ordered counterclockwise, check if the point is to the left of all + // edges (or on an edge) from one point to the next. When the point is to the left of all + // edges, it must be inside the triangle. + for i in 0..3 { + if triplet_orientation(self.corners[i], self.corners[(i + 1) % 3], point) + == TripletOrientation::Clockwise + { + return false; + } + } + + true + } +} + +#[derive(PartialEq, Eq)] +pub(crate) enum TripletOrientation { + Clockwise, + Counterclockwise, + Collinear, +} + +/// Helper function to determine which direction one would turn to traverse from the first point +/// over the second to the third point. The third option is collinear, in which case the three points +/// are on the same line. +pub(crate) fn triplet_orientation(a: Vec2, b: Vec2, c: Vec2) -> TripletOrientation +where + T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero, +{ + /* Check the slopes of the vector from a to b and b to c. If the slope of ab is greater than + * that of bc, the rotation is clockwise. If ab is smaller than bc it's counterclockwise. If + * they are the same it follows that the three points are collinear. + */ + match (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y) { + q if q > T::zero() => TripletOrientation::Counterclockwise, + q if q < T::zero() => TripletOrientation::Clockwise, + _ => TripletOrientation::Collinear, + } +} + +/// Calculate the angle between three points. Guaranteed to have 0 <= angle < 2Pi. The angle is +/// calculated as the angle between a line from a to b and then from b to c, increasing +/// counterclockwise. +/// +/// # Panics +/// If the length from a to b or the length from b to c is zero. +pub(crate) fn triplet_angle(a: Vec2, b: Vec2, c: Vec2) -> T +where + T: Scalar + Copy + ClosedSub + RealField + Zero, +{ + assert!(a != b); + assert!(b != c); + + // Handle the extreme 0 and 180 degree cases + let orientation = triplet_orientation(a, b, c); + if orientation == TripletOrientation::Collinear { + if LineSegment::new(a, b).contains_collinear(c) + || LineSegment::new(b, c).contains_collinear(a) + { + return T::zero(); + } else { + return T::pi(); + } + } + + // Calculate the vectors out of the points + let ba = a - b; + let bc = c - b; + + // Calculate the angle between 0 and Pi. + let angle = ((ba * bc) / (ba.length() * bc.length())).acos(); + + // Make angle into a full circle angle by looking at the orientation of the triplet. + let angle = match orientation { + TripletOrientation::Counterclockwise => T::pi() + (T::pi() - angle), + _ => angle, + }; + + angle +} + +#[cfg(test)] +mod test { + use super::*; + use std::f64::consts::PI; + + #[test] + fn triplet_angle() { + assert_eq!( + super::triplet_angle(Vec2::new(0., 0.), Vec2::new(0., -1.), Vec2::new(-1., -1.)), + 1.5 * PI + ); + assert_eq!( + super::triplet_angle(Vec2::new(2., 2.), Vec2::new(0., 0.), Vec2::new(-1., -1.)), + PI + ); + assert_eq!( + super::triplet_angle(Vec2::new(3., 1.), Vec2::new(0., 0.), Vec2::new(6., 2.)), + 0. + ); + assert_eq!( + super::triplet_angle(Vec2::new(3., 1.), Vec2::new(0., 0.), Vec2::new(-6., -2.)), + PI + ); + assert_eq!( + super::triplet_angle(Vec2::new(0., 1.), Vec2::new(0., 2.), Vec2::new(-3., 2.)), + 0.5 * PI + ); + assert_eq!( + super::triplet_angle(Vec2::new(3., 1.), Vec2::new(2., 2.), Vec2::new(0., 2.)), + 0.75 * PI + ); + } +} diff --git a/src/math/triangulate.rs b/src/math/triangulate.rs new file mode 100644 index 0000000..8ef92f1 --- /dev/null +++ b/src/math/triangulate.rs @@ -0,0 +1,12 @@ +//! Module for turning a polygon into a number of non-overlapping triangles. + +use super::{Polygon, 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 8785fda836fe3884bd51444fc55983fe135c6c9d Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 01:08:06 +0100 Subject: Add unit tests for triangle --- src/math/triangle.rs | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+) (limited to 'src') diff --git a/src/math/triangle.rs b/src/math/triangle.rs index 53c7560..05e258d 100644 --- a/src/math/triangle.rs +++ b/src/math/triangle.rs @@ -30,6 +30,11 @@ impl Triangle { } } + /// Get the corners immutably + pub fn corners(&self) -> &[Vec2; 3] { + &self.corners + } + /// Create a new Triangle from a three-point slice, instead of the three points one after /// another. pub fn from_slice(corners: [Vec2; 3]) -> Self @@ -60,6 +65,21 @@ impl Triangle { } } +/// Convert a three-point-slice into a triangle +impl From<[Vec2; 3]> + for Triangle +{ + fn from(corners: [Vec2; 3]) -> Self { + Self::new(corners[0], corners[1], corners[2]) + } +} +/// Convert a triangle into a three-point-slice. The corners are in counterclockwise order. +impl Into<[Vec2; 3]> for Triangle { + fn into(self) -> [Vec2; 3] { + self.corners + } +} + #[derive(PartialEq, Eq)] pub(crate) enum TripletOrientation { Clockwise, @@ -131,6 +151,43 @@ mod test { use super::*; use std::f64::consts::PI; + #[test] + fn new() { + let a = Vec2::new(0., 0.); + let b = Vec2::new(0., 1.); + let c = Vec2::new(1., 1.); + + // Create with counterclockwise order. + let triangle = Triangle::new(a, b, c); + assert_eq!(triangle.corners(), &[a, b, c]); + + // Create with clockwise order. + let triangle = Triangle::new(a, c, b); + assert_eq!(triangle.corners(), &[a, b, c]); + + // Create with different starting corner + let triangle = Triangle::from([b, c, a]); + assert_eq!(triangle.corners(), &[b, c, a]); + + // Create with collinear corners + let triangle = Triangle::new(c, c, b); + assert_eq!(triangle.corners(), &[c, c, b]); + } + + #[test] + fn contains_point() { + let a = Vec2::new(0., 0.); + let b = Vec2::new(-1., -1.); + let c = Vec2::new(-2., 0.); + + let triangle = Triangle::new(a, b, c); + + assert!(triangle.contains_point(b)); + assert!(triangle.contains_point(Vec2::new(-0.5, -0.5))); + assert!(triangle.contains_point(Vec2::new(-1., -0.5))); + assert!(!triangle.contains_point(Vec2::new(-2., -2.))); + } + #[test] fn triplet_angle() { assert_eq!( -- cgit v1.2.3-70-g09d2 From 32aec90d0fac637e165913f194422e5b3d96de36 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 01:12:07 +0100 Subject: Apply clippy lints --- src/math/polygon_graph.rs | 10 +++------- src/math/triangle.rs | 6 ++---- 2 files changed, 5 insertions(+), 11 deletions(-) (limited to 'src') diff --git a/src/math/polygon_graph.rs b/src/math/polygon_graph.rs index 7721cbf..14b2b0d 100644 --- a/src/math/polygon_graph.rs +++ b/src/math/polygon_graph.rs @@ -9,7 +9,7 @@ struct Node { } struct EdgeIterator<'a, T: Scalar + Copy> { - nodes: &'a Vec>, + nodes: &'a [Node], pos: (usize, usize), } @@ -39,7 +39,7 @@ fn find_node( } impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> { - pub fn new(nodes: &'a Vec>) -> Self { + pub fn new(nodes: &'a [Node]) -> Self { Self { nodes, pos: (0, 0) } } } @@ -99,11 +99,7 @@ impl PolygonGraph { pub fn has_edge(&self, from: &Vec2, to: &Vec2) -> bool { // Binary search the starting and then the end node. if let Ok(from) = find_node(&self.nodes, from) { - if let Ok(_) = find_vec2(&self.nodes[from].adjacent, to) { - true - } else { - false - } + find_vec2(&self.nodes[from].adjacent, to).is_ok() } else { false } diff --git a/src/math/triangle.rs b/src/math/triangle.rs index 05e258d..5cf16e5 100644 --- a/src/math/triangle.rs +++ b/src/math/triangle.rs @@ -138,12 +138,10 @@ where let angle = ((ba * bc) / (ba.length() * bc.length())).acos(); // Make angle into a full circle angle by looking at the orientation of the triplet. - let angle = match orientation { + match orientation { TripletOrientation::Counterclockwise => T::pi() + (T::pi() - angle), _ => angle, - }; - - angle + } } #[cfg(test)] -- cgit v1.2.3-70-g09d2 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/mod.rs | 4 - src/math/polygon.rs | 169 -------------- src/math/polygon/mod.rs | 177 +++++++++++++++ src/math/polygon/polygon_graph.rs | 463 ++++++++++++++++++++++++++++++++++++++ src/math/polygon/triangulate.rs | 13 ++ src/math/polygon_graph.rs | 462 ------------------------------------- src/math/triangulate.rs | 12 - 7 files changed, 653 insertions(+), 647 deletions(-) delete mode 100644 src/math/polygon.rs create mode 100644 src/math/polygon/mod.rs create mode 100644 src/math/polygon/polygon_graph.rs create mode 100644 src/math/polygon/triangulate.rs delete mode 100644 src/math/polygon_graph.rs delete mode 100644 src/math/triangulate.rs (limited to 'src') diff --git a/src/math/mod.rs b/src/math/mod.rs index 07bc36b..e72a7a4 100644 --- a/src/math/mod.rs +++ b/src/math/mod.rs @@ -1,17 +1,13 @@ pub mod line_segment; pub mod polygon; -pub mod polygon_graph; pub mod rect; pub mod triangle; -pub mod triangulate; pub mod vec2; pub use self::line_segment::*; pub use self::polygon::*; -pub use self::polygon_graph::*; pub use self::rect::*; pub use self::triangle::*; -pub use self::triangulate::*; pub use self::vec2::*; use std::cmp::Ordering; diff --git a/src/math/polygon.rs b/src/math/polygon.rs deleted file mode 100644 index 5711049..0000000 --- a/src/math/polygon.rs +++ /dev/null @@ -1,169 +0,0 @@ -use super::{PolygonGraph, Vec2}; -use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; -use num_traits::Zero; -use std::ops::Neg; - -#[derive(Debug)] -// TODO: Support polygons with holes -pub struct Polygon { - pub corners: Vec>, -} - -impl Polygon { - pub fn new(corners: Vec>) -> 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. - pub fn contains_point(&self, p: Vec2) -> bool - where - T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, - { - 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 - } - - /// 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) -> Vec> - 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()] - } -} - -#[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 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()); - } -} diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs new file mode 100644 index 0000000..4530857 --- /dev/null +++ b/src/math/polygon/mod.rs @@ -0,0 +1,177 @@ +//! 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::Vec2; +use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; +use num_traits::Zero; +use std::ops::Neg; + +#[derive(Debug)] +// TODO: Support polygons with holes +pub struct Polygon { + pub corners: Vec>, +} + +impl Polygon { + pub fn new(corners: Vec>) -> 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. + pub fn contains_point(&self, p: Vec2) -> bool + where + T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, + { + 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 + } + + /// 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) -> Vec> + 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()] + } +} + +#[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 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()); + } +} diff --git a/src/math/polygon/polygon_graph.rs b/src/math/polygon/polygon_graph.rs new file mode 100644 index 0000000..9477fbc --- /dev/null +++ b/src/math/polygon/polygon_graph.rs @@ -0,0 +1,463 @@ +use super::Polygon; +use crate::math::{self, LineSegment, Vec2}; +use nalgebra::{RealField, Scalar}; +use std::cmp::{Ordering, PartialOrd}; + +#[derive(Debug)] +struct Node { + pub vec: Vec2, + pub adjacent: Vec>, +} + +struct EdgeIterator<'a, T: Scalar + Copy> { + nodes: &'a [Node], + pos: (usize, usize), +} + +/// An undirected graph, that is optimised for polygon edge operations. Since edges of a polygon +/// are an undirected graph, this structure also holds both directions. This makes it rather space +/// inefficient, but makes edge operations rather swift. ß +#[derive(Debug)] +pub struct PolygonGraph { + /// The nodes of the graph, together with their adjacency list. + nodes: Vec>, +} +// Helper functions to find nodes/vecs in sorted fields, so It doesn't always have to be written +// out. +#[inline] +fn find_vec2( + field: &[Vec2], + lookup: &Vec2, +) -> Result { + field.binary_search_by(|n| n.partial_cmp(lookup).unwrap_or(Ordering::Greater)) +} +#[inline] +fn find_node( + field: &[Node], + lookup: &Vec2, +) -> Result { + field.binary_search_by(|n| n.vec.partial_cmp(lookup).unwrap_or(Ordering::Greater)) +} + +impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> { + pub fn new(nodes: &'a [Node]) -> Self { + Self { nodes, pos: (0, 0) } + } +} + +impl<'a, T: Scalar + Copy> Iterator for EdgeIterator<'a, T> { + type Item = LineSegment; + + fn next(&mut self) -> Option { + // Try to find the element in the nodes vector, if it exists. + if let Some(node) = self.nodes.get(self.pos.0) { + let end = node.adjacent[self.pos.1]; + + // Advance the iterator to the next possible element + if self.pos.1 + 1 < node.adjacent.len() { + self.pos.1 += 1; + } else { + self.pos.1 = 0; + self.pos.0 += 1; + } + + Some(LineSegment::new(node.vec, end)) + } else { + None + } + } +} + +impl PolygonGraph { + /// Create a new, empty polygon graph. + pub fn new() -> Self { + Self { nodes: Vec::new() } + } + + /// Count the number of edges in the graph. Internally, for each two connected points there are + /// two edges, but this returns the amount of polygon edges. + pub fn num_edges(&self) -> usize { + let mut num_edges = 0; + for node in &self.nodes { + for _ in &node.adjacent { + num_edges += 1; + } + } + + assert!(num_edges % 2 == 0); + num_edges / 2 + } + + /// Count the number of nodes in this graph. If this graph consists of multiple polygons, this + /// can be different than the amount of corners, since corners with the same position are only + /// counted once. + pub fn num_nodes(&self) -> usize { + self.nodes.len() + } + + /// Checks if there is an edge between the two given vectors. Is commutative in respect to the + /// two arguments. + pub fn has_edge(&self, from: &Vec2, to: &Vec2) -> bool { + // Binary search the starting and then the end node. + if let Ok(from) = find_node(&self.nodes, from) { + find_vec2(&self.nodes[from].adjacent, to).is_ok() + } else { + false + } + } + + // Helper function to add the edge into the internal graph representation for one side only. + // Since to the outside the graph should always be undirected, this must be private. + fn add_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { + match find_node(&self.nodes, from) { + Ok(pos) => match find_vec2(&self.nodes[pos].adjacent, to) { + Ok(_) => return false, + Err(i) => self.nodes[pos].adjacent.insert(i, *to), + }, + Err(pos) => self.nodes.insert( + pos, + Node { + vec: *from, + adjacent: vec![*to], + }, + ), + } + + true + } + + /// Add an edge between the given vectors. If the edge already exists, it does nothing and + /// returns false, otherwise it returns true after addition. + pub fn add_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { + if !self.add_edge_onesided(from, to) { + return false; + } + + let back_edge_succ = self.add_edge_onesided(to, from); + assert!(back_edge_succ); + + true + } + + // Helper function to remove the edge in the internal graph representation for one side only. + // Since to the outside the graph should always be undirected, this must be private. + fn remove_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { + if let Ok(from) = find_node(&self.nodes, from) { + if let Ok(to) = find_vec2(&self.nodes[from].adjacent, to) { + // Remove the edge from the vector. + self.nodes[from].adjacent.remove(to); + + // If the node has no adjacent nodes anymore, remove it entirely. + if self.nodes[from].adjacent.is_empty() { + self.nodes.remove(from); + } + + true + } else { + false + } + } else { + false + } + } + + /// Remove an edge between the given vectors. If there is no edge between them, it does nothing + /// and returns false, otherwise it returns true after deletion. + pub fn remove_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { + if !self.remove_edge_onesided(from, to) { + return false; + } + + let back_edge_succ = self.remove_edge_onesided(to, from); + assert!(back_edge_succ); + + true + } + + /// Constructs a new PolygonGraph from the provided polygon. Adds a node for every corner and + /// an edge to all connected corners (which should be exactly two, for regular polygons) + pub fn from_polygon(polygon: &Polygon) -> Self { + let mut graph = PolygonGraph { + nodes: Vec::with_capacity(polygon.corners.len()), + }; + + graph.add_all(polygon); + graph + } + + /// Add all edges of the provided polygon into the graph. Requires roughly double as much space + /// as the normal polygon. + pub fn add_all(&mut self, polygon: &Polygon) { + for i in 0..polygon.corners.len() { + self.add_edge( + &polygon.corners[i], + &polygon.corners[(i + 1) % polygon.corners.len()], + ); + } + } + + /// Calculates all points where the graph edges intersect with one another. It then adds them + /// into the adjacency list such that the intersection point lies between the nodes of the + /// lines. + pub fn intersect_self(&mut self) + where + T: RealField, + { + // Find all intersections with all other edges. + let mut to_delete: Vec> = Vec::new(); + let mut to_add: Vec<(Vec2, Vec2)> = Vec::new(); + for segment in EdgeIterator::new(&self.nodes) { + /* Save all intersections of this line with any other line, and the line that it's + * intersecting with. + */ + let mut intersections: Vec> = Vec::new(); + for compare_segment in EdgeIterator::new(&self.nodes) { + if segment.eq_ignore_dir(&compare_segment) { + continue; + } + + if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) { + intersections.push(intersection); + } + } + + if intersections.is_empty() { + continue; + } + + to_delete.push(segment.clone()); + + // Safe, since at least the line segment itself is represented. + let segments = segment.segments(&intersections); + for i in 1..segments.len() { + to_add.push((segments[i - 1], segments[i])); + } + } + + for segment in to_delete { + self.remove_edge(&segment.start, &segment.end); + } + for (start, end) in to_add { + self.add_edge(&start, &end); + } + } + + /// Finds the minimal polygon that could hold this graph together, i.e. could contain the + /// entire graph, but with the minimal amount of space. It may however still contain extra + /// corner points, meaning an extra edge for three collinear points on this edge, that can be + /// cleaned up. + pub fn bounding_polygon(mut self) -> Polygon + where + T: RealField, + { + assert!(self.num_nodes() >= 3); + self.intersect_self(); + + /* Start with the top-left node. Since the nodes are always sorted by y over x from top to + * bottom and left to right, this is the very first element in the vector. This is also a + * corner, because for such a node to be enveloped, there would have to be a node further + * to the top, in which case that node would have been selected. + */ + let mut current_node = &self.nodes[0]; + // Pretend we're coming from the top to start in the right direction. + let mut last_vec = current_node.vec - Vec2::new(T::zero(), T::one()); + let mut bounding_polygon = Polygon::new(vec![current_node.vec]); + loop { + /* Find the next point by choosing the one with the greatest angle. This means we are + * "bending" to the leftmost edge at each step. Since we are going around the polygon + * in a clockwise direction, this yields the hull around the polygon. + * NOTE: Going left is just as viable, but we would have to handle the case where the + * algorithm would try to go back because the edge back has 0 degrees, which would be + * always preferred. Going right makes going back the absolute worst option. + */ + let next_corner = current_node + .adjacent + .iter() + .max_by(|&a, &b| { + math::triplet_angle(last_vec, current_node.vec, *a) + .partial_cmp(&math::triplet_angle(last_vec, current_node.vec, *b)) + .unwrap_or(Ordering::Equal) + }) + .expect("Adjacency list is empty. The polygon has an open edge (is broken)"); + + // When we have come back to the start, the traversal is completed + if *next_corner == bounding_polygon.corners[0] { + break; + } + + bounding_polygon.corners.push(*next_corner); + last_vec = current_node.vec; + current_node = &self.nodes[find_node(&self.nodes, &next_corner) + .expect("Failure to find node that should be inside list.")]; + } + + bounding_polygon + } +} + +impl Default for PolygonGraph { + fn default() -> Self { + Self::new() + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn from_polygon() { + let a = Vec2::new(0., 0.); + let b = Vec2::new(0., 1.); + let c = Vec2::new(0.5, 1.); + + let triangle = Polygon::new(vec![a, b, c]); + + let graph = PolygonGraph::from_polygon(&triangle); + assert_eq!(graph.num_edges(), 3); + + assert!(graph.has_edge(&a, &b)); + assert!(graph.has_edge(&b, &a)); + + assert!(graph.has_edge(&a, &c)); + assert!(graph.has_edge(&c, &a)); + + assert!(graph.has_edge(&b, &c)); + assert!(graph.has_edge(&c, &b)); + } + + #[test] + fn add_all() { + let top_left = Vec2::new(0., 0.); + let top_right = Vec2::new(1., 0.); + let bot_left = Vec2::new(0., 1.); + let bot_right = Vec2::new(1., 1.); + + let triangle = Polygon::new(vec![top_left, bot_right, top_right]); + + let square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]); + + let mut graph = PolygonGraph::new(); + graph.add_all(&triangle); + graph.add_all(&square); + + assert_eq!(graph.num_edges(), 5); + assert_eq!(graph.num_nodes(), 4); + + assert!(graph.has_edge(&top_left, &top_right)); + assert!(graph.has_edge(&top_right, &top_left)); + + assert!(graph.has_edge(&top_left, &bot_left)); + assert!(graph.has_edge(&bot_left, &top_left)); + + assert!(graph.has_edge(&bot_left, &bot_right)); + assert!(graph.has_edge(&bot_right, &bot_left)); + + assert!(graph.has_edge(&bot_right, &top_right)); + assert!(graph.has_edge(&top_right, &bot_right)); + + assert!(graph.has_edge(&top_left, &bot_right)); + assert!(graph.has_edge(&bot_right, &top_left)); + } + + #[test] + fn intersect_self() { + let first = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(3., 1.), + Vec2::new(2., 0.), + ]); + + let second = Polygon::new(vec![ + Vec2::new(2.5, -0.5), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(2., 0.5), + Vec2::new(2.5, 0.), + ]); + + let mut graph = PolygonGraph::from_polygon(&first); + graph.add_all(&second); + + graph.intersect_self(); + + println!("Intersected graph:"); + println!("{:#?}", &graph); + + assert_eq!(graph.num_nodes(), 9); + assert_eq!(graph.num_edges(), 12); + + assert!(graph.has_edge(&Vec2::new(2., 0.), &Vec2::new(2.25, 0.25))); + assert!(graph.has_edge(&Vec2::new(3., 1.), &Vec2::new(2.25, 0.25))); + assert!(!graph.has_edge(&Vec2::new(2., 0.), &Vec2::new(3., 1.))); + assert!(graph.has_edge(&Vec2::new(0., 2.), &Vec2::new(2., 2.))); + assert!(graph.has_edge(&Vec2::new(2., 2.), &Vec2::new(0., 2.))); + assert!(graph.has_edge(&Vec2::new(0., 2.), &Vec2::new(2., 0.))); + assert!(!graph.has_edge(&Vec2::new(0., 2.), &Vec2::new(2.5, -0.5))); + } + + #[test] + fn bounding_polygon() { + let first = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(3., 1.), + Vec2::new(2., 0.), + ]); + + let second = Polygon::new(vec![ + Vec2::new(2.5, -0.5), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(2., 0.5), + Vec2::new(2.5, 0.), + ]); + + let mut graph = PolygonGraph::from_polygon(&first); + graph.add_all(&second); + + let bounding = graph.bounding_polygon(); + + let num_corners = 8; + assert_eq!(bounding.corners.len(), num_corners); + + // Run around the polygon to see if it was constructed correctly. + let start_i = bounding + .corners + .iter() + .position(|&x| x == Vec2::new(0., 0.)) + .expect("Starting vector does not exist in polygon."); + + assert_eq!( + bounding.corners[(start_i + 1) % num_corners], + Vec2::new(2., 0.) + ); + assert_eq!( + bounding.corners[(start_i + 2) % num_corners], + Vec2::new(2.5, -0.5) + ); + assert_eq!( + bounding.corners[(start_i + 3) % num_corners], + Vec2::new(2.5, 0.0) + ); + assert_eq!( + bounding.corners[(start_i + 4) % num_corners], + Vec2::new(2.25, 0.25) + ); + assert_eq!( + bounding.corners[(start_i + 5) % num_corners], + Vec2::new(3., 1.) + ); + assert_eq!( + bounding.corners[(start_i + 6) % num_corners], + Vec2::new(2., 2.) + ); + assert_eq!( + bounding.corners[(start_i + 7) % num_corners], + Vec2::new(0., 2.) + ); + } +} 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!() +} diff --git a/src/math/polygon_graph.rs b/src/math/polygon_graph.rs deleted file mode 100644 index 14b2b0d..0000000 --- a/src/math/polygon_graph.rs +++ /dev/null @@ -1,462 +0,0 @@ -use super::{LineSegment, Polygon, Vec2}; -use nalgebra::{RealField, Scalar}; -use std::cmp::{Ordering, PartialOrd}; - -#[derive(Debug)] -struct Node { - pub vec: Vec2, - pub adjacent: Vec>, -} - -struct EdgeIterator<'a, T: Scalar + Copy> { - nodes: &'a [Node], - pos: (usize, usize), -} - -/// An undirected graph, that is optimised for polygon edge operations. Since edges of a polygon -/// are an undirected graph, this structure also holds both directions. This makes it rather space -/// inefficient, but makes edge operations rather swift. ß -#[derive(Debug)] -pub struct PolygonGraph { - /// The nodes of the graph, together with their adjacency list. - nodes: Vec>, -} -// Helper functions to find nodes/vecs in sorted fields, so It doesn't always have to be written -// out. -#[inline] -fn find_vec2( - field: &[Vec2], - lookup: &Vec2, -) -> Result { - field.binary_search_by(|n| n.partial_cmp(lookup).unwrap_or(Ordering::Greater)) -} -#[inline] -fn find_node( - field: &[Node], - lookup: &Vec2, -) -> Result { - field.binary_search_by(|n| n.vec.partial_cmp(lookup).unwrap_or(Ordering::Greater)) -} - -impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> { - pub fn new(nodes: &'a [Node]) -> Self { - Self { nodes, pos: (0, 0) } - } -} - -impl<'a, T: Scalar + Copy> Iterator for EdgeIterator<'a, T> { - type Item = LineSegment; - - fn next(&mut self) -> Option { - // Try to find the element in the nodes vector, if it exists. - if let Some(node) = self.nodes.get(self.pos.0) { - let end = node.adjacent[self.pos.1]; - - // Advance the iterator to the next possible element - if self.pos.1 + 1 < node.adjacent.len() { - self.pos.1 += 1; - } else { - self.pos.1 = 0; - self.pos.0 += 1; - } - - Some(LineSegment::new(node.vec, end)) - } else { - None - } - } -} - -impl PolygonGraph { - /// Create a new, empty polygon graph. - pub fn new() -> Self { - Self { nodes: Vec::new() } - } - - /// Count the number of edges in the graph. Internally, for each two connected points there are - /// two edges, but this returns the amount of polygon edges. - pub fn num_edges(&self) -> usize { - let mut num_edges = 0; - for node in &self.nodes { - for _ in &node.adjacent { - num_edges += 1; - } - } - - assert!(num_edges % 2 == 0); - num_edges / 2 - } - - /// Count the number of nodes in this graph. If this graph consists of multiple polygons, this - /// can be different than the amount of corners, since corners with the same position are only - /// counted once. - pub fn num_nodes(&self) -> usize { - self.nodes.len() - } - - /// Checks if there is an edge between the two given vectors. Is commutative in respect to the - /// two arguments. - pub fn has_edge(&self, from: &Vec2, to: &Vec2) -> bool { - // Binary search the starting and then the end node. - if let Ok(from) = find_node(&self.nodes, from) { - find_vec2(&self.nodes[from].adjacent, to).is_ok() - } else { - false - } - } - - // Helper function to add the edge into the internal graph representation for one side only. - // Since to the outside the graph should always be undirected, this must be private. - fn add_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { - match find_node(&self.nodes, from) { - Ok(pos) => match find_vec2(&self.nodes[pos].adjacent, to) { - Ok(_) => return false, - Err(i) => self.nodes[pos].adjacent.insert(i, *to), - }, - Err(pos) => self.nodes.insert( - pos, - Node { - vec: *from, - adjacent: vec![*to], - }, - ), - } - - true - } - - /// Add an edge between the given vectors. If the edge already exists, it does nothing and - /// returns false, otherwise it returns true after addition. - pub fn add_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { - if !self.add_edge_onesided(from, to) { - return false; - } - - let back_edge_succ = self.add_edge_onesided(to, from); - assert!(back_edge_succ); - - true - } - - // Helper function to remove the edge in the internal graph representation for one side only. - // Since to the outside the graph should always be undirected, this must be private. - fn remove_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { - if let Ok(from) = find_node(&self.nodes, from) { - if let Ok(to) = find_vec2(&self.nodes[from].adjacent, to) { - // Remove the edge from the vector. - self.nodes[from].adjacent.remove(to); - - // If the node has no adjacent nodes anymore, remove it entirely. - if self.nodes[from].adjacent.is_empty() { - self.nodes.remove(from); - } - - true - } else { - false - } - } else { - false - } - } - - /// Remove an edge between the given vectors. If there is no edge between them, it does nothing - /// and returns false, otherwise it returns true after deletion. - pub fn remove_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { - if !self.remove_edge_onesided(from, to) { - return false; - } - - let back_edge_succ = self.remove_edge_onesided(to, from); - assert!(back_edge_succ); - - true - } - - /// Constructs a new PolygonGraph from the provided polygon. Adds a node for every corner and - /// an edge to all connected corners (which should be exactly two, for regular polygons) - pub fn from_polygon(polygon: &Polygon) -> Self { - let mut graph = PolygonGraph { - nodes: Vec::with_capacity(polygon.corners.len()), - }; - - graph.add_all(polygon); - graph - } - - /// Add all edges of the provided polygon into the graph. Requires roughly double as much space - /// as the normal polygon. - pub fn add_all(&mut self, polygon: &Polygon) { - for i in 0..polygon.corners.len() { - self.add_edge( - &polygon.corners[i], - &polygon.corners[(i + 1) % polygon.corners.len()], - ); - } - } - - /// Calculates all points where the graph edges intersect with one another. It then adds them - /// into the adjacency list such that the intersection point lies between the nodes of the - /// lines. - pub fn intersect_self(&mut self) - where - T: RealField, - { - // Find all intersections with all other edges. - let mut to_delete: Vec> = Vec::new(); - let mut to_add: Vec<(Vec2, Vec2)> = Vec::new(); - for segment in EdgeIterator::new(&self.nodes) { - /* Save all intersections of this line with any other line, and the line that it's - * intersecting with. - */ - let mut intersections: Vec> = Vec::new(); - for compare_segment in EdgeIterator::new(&self.nodes) { - if segment.eq_ignore_dir(&compare_segment) { - continue; - } - - if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) { - intersections.push(intersection); - } - } - - if intersections.is_empty() { - continue; - } - - to_delete.push(segment.clone()); - - // Safe, since at least the line segment itself is represented. - let segments = segment.segments(&intersections); - for i in 1..segments.len() { - to_add.push((segments[i - 1], segments[i])); - } - } - - for segment in to_delete { - self.remove_edge(&segment.start, &segment.end); - } - for (start, end) in to_add { - self.add_edge(&start, &end); - } - } - - /// Finds the minimal polygon that could hold this graph together, i.e. could contain the - /// entire graph, but with the minimal amount of space. It may however still contain extra - /// corner points, meaning an extra edge for three collinear points on this edge, that can be - /// cleaned up. - pub fn bounding_polygon(mut self) -> Polygon - where - T: RealField, - { - assert!(self.num_nodes() >= 3); - self.intersect_self(); - - /* Start with the top-left node. Since the nodes are always sorted by y over x from top to - * bottom and left to right, this is the very first element in the vector. This is also a - * corner, because for such a node to be enveloped, there would have to be a node further - * to the top, in which case that node would have been selected. - */ - let mut current_node = &self.nodes[0]; - // Pretend we're coming from the top to start in the right direction. - let mut last_vec = current_node.vec - Vec2::new(T::zero(), T::one()); - let mut bounding_polygon = Polygon::new(vec![current_node.vec]); - loop { - /* Find the next point by choosing the one with the greatest angle. This means we are - * "bending" to the leftmost edge at each step. Since we are going around the polygon - * in a clockwise direction, this yields the hull around the polygon. - * NOTE: Going left is just as viable, but we would have to handle the case where the - * algorithm would try to go back because the edge back has 0 degrees, which would be - * always preferred. Going right makes going back the absolute worst option. - */ - let next_corner = current_node - .adjacent - .iter() - .max_by(|&a, &b| { - super::triplet_angle(last_vec, current_node.vec, *a) - .partial_cmp(&super::triplet_angle(last_vec, current_node.vec, *b)) - .unwrap_or(Ordering::Equal) - }) - .expect("Adjacency list is empty. The polygon has an open edge (is broken)"); - - // When we have come back to the start, the traversal is completed - if *next_corner == bounding_polygon.corners[0] { - break; - } - - bounding_polygon.corners.push(*next_corner); - last_vec = current_node.vec; - current_node = &self.nodes[find_node(&self.nodes, &next_corner) - .expect("Failure to find node that should be inside list.")]; - } - - bounding_polygon - } -} - -impl Default for PolygonGraph { - fn default() -> Self { - Self::new() - } -} - -#[cfg(test)] -mod test { - use super::*; - - #[test] - fn from_polygon() { - let a = Vec2::new(0., 0.); - let b = Vec2::new(0., 1.); - let c = Vec2::new(0.5, 1.); - - let triangle = Polygon::new(vec![a, b, c]); - - let graph = PolygonGraph::from_polygon(&triangle); - assert_eq!(graph.num_edges(), 3); - - assert!(graph.has_edge(&a, &b)); - assert!(graph.has_edge(&b, &a)); - - assert!(graph.has_edge(&a, &c)); - assert!(graph.has_edge(&c, &a)); - - assert!(graph.has_edge(&b, &c)); - assert!(graph.has_edge(&c, &b)); - } - - #[test] - fn add_all() { - let top_left = Vec2::new(0., 0.); - let top_right = Vec2::new(1., 0.); - let bot_left = Vec2::new(0., 1.); - let bot_right = Vec2::new(1., 1.); - - let triangle = Polygon::new(vec![top_left, bot_right, top_right]); - - let square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]); - - let mut graph = PolygonGraph::new(); - graph.add_all(&triangle); - graph.add_all(&square); - - assert_eq!(graph.num_edges(), 5); - assert_eq!(graph.num_nodes(), 4); - - assert!(graph.has_edge(&top_left, &top_right)); - assert!(graph.has_edge(&top_right, &top_left)); - - assert!(graph.has_edge(&top_left, &bot_left)); - assert!(graph.has_edge(&bot_left, &top_left)); - - assert!(graph.has_edge(&bot_left, &bot_right)); - assert!(graph.has_edge(&bot_right, &bot_left)); - - assert!(graph.has_edge(&bot_right, &top_right)); - assert!(graph.has_edge(&top_right, &bot_right)); - - assert!(graph.has_edge(&top_left, &bot_right)); - assert!(graph.has_edge(&bot_right, &top_left)); - } - - #[test] - fn intersect_self() { - let first = Polygon::new(vec![ - Vec2::new(0., 0.), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(3., 1.), - Vec2::new(2., 0.), - ]); - - let second = Polygon::new(vec![ - Vec2::new(2.5, -0.5), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(2., 0.5), - Vec2::new(2.5, 0.), - ]); - - let mut graph = PolygonGraph::from_polygon(&first); - graph.add_all(&second); - - graph.intersect_self(); - - println!("Intersected graph:"); - println!("{:#?}", &graph); - - assert_eq!(graph.num_nodes(), 9); - assert_eq!(graph.num_edges(), 12); - - assert!(graph.has_edge(&Vec2::new(2., 0.), &Vec2::new(2.25, 0.25))); - assert!(graph.has_edge(&Vec2::new(3., 1.), &Vec2::new(2.25, 0.25))); - assert!(!graph.has_edge(&Vec2::new(2., 0.), &Vec2::new(3., 1.))); - assert!(graph.has_edge(&Vec2::new(0., 2.), &Vec2::new(2., 2.))); - assert!(graph.has_edge(&Vec2::new(2., 2.), &Vec2::new(0., 2.))); - assert!(graph.has_edge(&Vec2::new(0., 2.), &Vec2::new(2., 0.))); - assert!(!graph.has_edge(&Vec2::new(0., 2.), &Vec2::new(2.5, -0.5))); - } - - #[test] - fn bounding_polygon() { - let first = Polygon::new(vec![ - Vec2::new(0., 0.), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(3., 1.), - Vec2::new(2., 0.), - ]); - - let second = Polygon::new(vec![ - Vec2::new(2.5, -0.5), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(2., 0.5), - Vec2::new(2.5, 0.), - ]); - - let mut graph = PolygonGraph::from_polygon(&first); - graph.add_all(&second); - - let bounding = graph.bounding_polygon(); - - let num_corners = 8; - assert_eq!(bounding.corners.len(), num_corners); - - // Run around the polygon to see if it was constructed correctly. - let start_i = bounding - .corners - .iter() - .position(|&x| x == Vec2::new(0., 0.)) - .expect("Starting vector does not exist in polygon."); - - assert_eq!( - bounding.corners[(start_i + 1) % num_corners], - Vec2::new(2., 0.) - ); - assert_eq!( - bounding.corners[(start_i + 2) % num_corners], - Vec2::new(2.5, -0.5) - ); - assert_eq!( - bounding.corners[(start_i + 3) % num_corners], - Vec2::new(2.5, 0.0) - ); - assert_eq!( - bounding.corners[(start_i + 4) % num_corners], - Vec2::new(2.25, 0.25) - ); - assert_eq!( - bounding.corners[(start_i + 5) % num_corners], - Vec2::new(3., 1.) - ); - assert_eq!( - bounding.corners[(start_i + 6) % num_corners], - Vec2::new(2., 2.) - ); - assert_eq!( - bounding.corners[(start_i + 7) % num_corners], - Vec2::new(0., 2.) - ); - } -} diff --git a/src/math/triangulate.rs b/src/math/triangulate.rs deleted file mode 100644 index 8ef92f1..0000000 --- a/src/math/triangulate.rs +++ /dev/null @@ -1,12 +0,0 @@ -//! Module for turning a polygon into a number of non-overlapping triangles. - -use super::{Polygon, 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 abf55d8d46fc7d5cfccc9f778da6fca10b33d0cd Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 20:55:47 +0100 Subject: Move containment of points/ lines into trait --- src/gui/tool_sidebar.rs | 4 +- src/math/line_segment.rs | 6 +-- src/math/mod.rs | 10 +++++ src/math/polygon/mod.rs | 53 ++++++++++++---------- src/math/rect.rs | 112 +++++++++++++++++++++++----------------------- src/tool/deletion_tool.rs | 6 +-- 6 files changed, 105 insertions(+), 86 deletions(-) (limited to 'src') diff --git a/src/gui/tool_sidebar.rs b/src/gui/tool_sidebar.rs index 46b53ea..7674c47 100644 --- a/src/gui/tool_sidebar.rs +++ b/src/gui/tool_sidebar.rs @@ -1,4 +1,4 @@ -use crate::math::{Rect, Vec2}; +use crate::math::{Rect, Surface, Vec2}; use crate::tool::ToolType; use crate::Editor; use raylib::core::texture::Texture2D; @@ -28,7 +28,7 @@ impl ToolSidebar { /// Check if the mouse is currently being captured by this GUI-element. In that case, /// everything else that might want to access the mouse will be blocked. pub fn mouse_captured(screen_height: u16, mouse_pos: Vec2) -> bool { - Self::panel_rect(screen_height).contains(mouse_pos) + Self::panel_rect(screen_height).contains_point(&mouse_pos) } pub fn draw(&self, screen_height: u16, rld: &mut impl RaylibDrawGui, editor: &mut Editor) { diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index 244b0af..94f58b2 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -1,4 +1,4 @@ -use super::{Rect, TripletOrientation, Vec2}; +use super::{Rect, Surface, TripletOrientation, Vec2}; use alga::general::{ClosedDiv, ClosedMul, ClosedSub}; use nalgebra::{RealField, Scalar}; use num_traits::Zero; @@ -118,8 +118,8 @@ impl LineSegment { * the segments. We know it's on the lines, so checking with the lines bounding box is * faster than checking where on the line exactly it would be. */ - if Rect::bounding_rect(line_a.start, line_a.end).contains(out) - && Rect::bounding_rect(line_b.start, line_b.end).contains(out) + if Rect::bounding_rect(line_a.start, line_a.end).contains_point(&out) + && Rect::bounding_rect(line_b.start, line_b.end).contains_point(&out) { Some(out) } else { diff --git a/src/math/mod.rs b/src/math/mod.rs index e72a7a4..6f83c98 100644 --- a/src/math/mod.rs +++ b/src/math/mod.rs @@ -10,8 +10,18 @@ pub use self::rect::*; pub use self::triangle::*; pub use self::vec2::*; +use nalgebra::Scalar; use std::cmp::Ordering; +/// Trait that describes an area in the vector space on the field of T +pub trait Surface { + /// Checks if a point lies on this surface. + fn contains_point(&self, point: &Vec2) -> bool; + + /// Checks if a line segment is entirely contained by this surface. + fn contains_line_segment(&self, line_segment: &LineSegment) -> bool; +} + /// Round a floating point number to the nearest step given by the step argument. For instance, if /// the step is 0.5, then all numbers from 0.0 to 0.24999... will be 0., while all numbers from /// 0.25 to 0.74999... will be 0.5 and so on. diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs index 4530857..d351ec7 100644 --- a/src/math/polygon/mod.rs +++ b/src/math/polygon/mod.rs @@ -6,7 +6,7 @@ pub mod triangulate; pub use polygon_graph::*; pub use triangulate::*; -use super::Vec2; +use super::{LineSegment, Surface, Vec2}; use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; use num_traits::Zero; use std::ops::Neg; @@ -24,10 +24,27 @@ impl Polygon { /// Check whether a point is inside a polygon or not. If a point lies on an edge, it also /// counts as inside the polygon. - pub fn contains_point(&self, p: Vec2) -> bool + + /// 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) -> Vec> where - T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, + 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 + PartialOrd + Zero, + > Surface for Polygon +{ + fn contains_point(&self, p: &Vec2) -> bool { let n = self.corners.len(); let a = self.corners[n - 1]; @@ -102,18 +119,8 @@ impl Polygon { (depth & 1) == 1 } - /// 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) -> Vec> - 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()] + fn contains_line_segment(&self, line_segment: &LineSegment) -> bool { + unimplemented!() } } @@ -133,14 +140,14 @@ mod test { 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.))); + 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] diff --git a/src/math/rect.rs b/src/math/rect.rs index 6988b2c..876e728 100644 --- a/src/math/rect.rs +++ b/src/math/rect.rs @@ -1,6 +1,6 @@ -use super::Vec2; +use super::{LineSegment, Surface, Vec2}; //use alga::general::{Additive, Identity}; -use nalgebra::{RealField, Scalar}; +use nalgebra::{ClosedAdd, RealField, Scalar}; use num_traits::identities::Zero; use serde::{Deserialize, Serialize}; use std::ops::{Add, AddAssign, Sub}; @@ -18,48 +18,6 @@ pub struct Rect { pub h: T, } -// This is sad, but also sadly necessary :/ -impl + Scalar + Copy> Into for Rect { - fn into(self) -> raylib::ffi::Rectangle { - raylib::ffi::Rectangle { - x: self.x.into(), - y: self.y.into(), - width: self.w.into(), - height: self.h.into(), - } - } -} -impl + Scalar + Copy> From for Rect { - fn from(r: raylib::ffi::Rectangle) -> Self { - Self { - x: T::from(r.x), - y: T::from(r.y), - w: T::from(r.width), - h: T::from(r.height), - } - } -} -impl + Scalar + Copy> Into for Rect { - fn into(self) -> raylib::math::Rectangle { - raylib::math::Rectangle { - x: self.x.into(), - y: self.y.into(), - width: self.w.into(), - height: self.h.into(), - } - } -} -impl + Scalar + Copy> From for Rect { - fn from(r: raylib::math::Rectangle) -> Self { - Self { - x: T::from(r.x), - y: T::from(r.y), - w: T::from(r.width), - h: T::from(r.height), - } - } -} - impl Rect { pub fn new(x: T, y: T, w: T, h: T) -> Self { Self { x, y, w, h } @@ -105,17 +63,6 @@ impl Rect { || this.y + this.h < other.y) } - /// Check if the point is inside this Rect and return true if so. - pub fn contains(&self, point: Vec2) -> bool - where - T: PartialOrd + Add, - { - point.x >= self.x - && point.x <= self.x + self.w - && point.y >= self.y - && point.y <= self.y + self.h - } - /// Returns true if the entire rect is contained inside this rectangle. pub fn contains_rect(&self, rect: Rect) -> bool where @@ -181,6 +128,61 @@ impl Rect { } } +impl Surface for Rect { + fn contains_point(&self, point: &Vec2) -> bool { + point.x >= self.x + && point.x <= self.x + self.w + && point.y >= self.y + && point.y <= self.y + self.h + } + + fn contains_line_segment(&self, line_segment: &LineSegment) -> bool { + self.contains_point(&line_segment.start) && self.contains_point(&line_segment.end) + } +} + +// This is sad, but also sadly necessary :/ +impl + Scalar + Copy> Into for Rect { + fn into(self) -> raylib::ffi::Rectangle { + raylib::ffi::Rectangle { + x: self.x.into(), + y: self.y.into(), + width: self.w.into(), + height: self.h.into(), + } + } +} +impl + Scalar + Copy> From for Rect { + fn from(r: raylib::ffi::Rectangle) -> Self { + Self { + x: T::from(r.x), + y: T::from(r.y), + w: T::from(r.width), + h: T::from(r.height), + } + } +} +impl + Scalar + Copy> Into for Rect { + fn into(self) -> raylib::math::Rectangle { + raylib::math::Rectangle { + x: self.x.into(), + y: self.y.into(), + width: self.w.into(), + height: self.h.into(), + } + } +} +impl + Scalar + Copy> From for Rect { + fn from(r: raylib::math::Rectangle) -> Self { + Self { + x: T::from(r.x), + y: T::from(r.y), + w: T::from(r.width), + h: T::from(r.height), + } + } +} + #[cfg(test)] mod test { use super::*; diff --git a/src/tool/deletion_tool.rs b/src/tool/deletion_tool.rs index c313574..5031f5d 100644 --- a/src/tool/deletion_tool.rs +++ b/src/tool/deletion_tool.rs @@ -2,7 +2,7 @@ use super::Tool; use crate::button::Button; use crate::config::{DeletionToolKeybindings, ToolKeybindings}; use crate::map_data::MapData; -use crate::math::{Rect, Vec2}; +use crate::math::{Rect, Surface, Vec2}; use crate::transform::Transform; use raylib::core::drawing::{RaylibDraw, RaylibDrawHandle}; use raylib::ffi::Color; @@ -28,10 +28,10 @@ impl DeletionTool { .retain(|&room| !rect.contains_rect(room)); map_data .walls_mut() - .retain(|&(pos1, pos2)| !rect.contains(pos1) || !rect.contains(pos2)); + .retain(|&(pos1, pos2)| !rect.contains_point(&pos1) || !rect.contains_point(&pos2)); map_data .icons_mut() - .retain(|icon| !rect.contains(icon.position)); + .retain(|icon| !rect.contains_point(&icon.position)); } } -- 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') 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 a6c141908ddb94a0ebb3a1ac95d3f8444e13e3b5 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Mon, 23 Nov 2020 22:40:12 +0100 Subject: Fix corner case not being handled Previously, the algorithm to check, if a line-segment is inside a polygon did not have a special case for when the start or end of the segment is on a polygon corner. In case this corner is reflexive, checking against one line between this corner and an adjacent one may not be enough. --- src/math/polygon/mod.rs | 64 +++++++++++++++++++++++++++++++++++++++++++++++-- src/math/triangle.rs | 35 +++++++++++++++++++++++++++ 2 files changed, 97 insertions(+), 2 deletions(-) (limited to 'src') diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs index baa1e6d..e19e097 100644 --- a/src/math/polygon/mod.rs +++ b/src/math/polygon/mod.rs @@ -130,11 +130,60 @@ impl< /* 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, c: usize| { + 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 + } + }; + + 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) { @@ -152,8 +201,13 @@ impl< /* 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 { + (TripletOrientation::Collinear, o) => { + if !start_looks_inside && o == TripletOrientation::Clockwise { + return false; + } + } + (o, TripletOrientation::Collinear) => { + if !end_looks_inside && o == TripletOrientation::Clockwise { return false; } } @@ -237,6 +291,12 @@ mod test { // 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.))) + ); } #[test] diff --git a/src/math/triangle.rs b/src/math/triangle.rs index 5cf16e5..35bdcec 100644 --- a/src/math/triangle.rs +++ b/src/math/triangle.rs @@ -4,6 +4,7 @@ use nalgebra::{RealField, Scalar}; use num_traits::Zero; /// Represents a triangle +#[derive(Debug)] pub struct Triangle { /// The three corners of the triangle. Internally, it is made sure that the corners are always /// ordered in a counterclockwise manner, to make operations like contains simpler. @@ -80,6 +81,25 @@ impl Into<[Vec2; 3]> for Triangle { } } +impl PartialEq for Triangle { + fn eq(&self, other: &Self) -> bool { + // The indexes of the elements are not important, so try all shifting options. + for shift in 0..=2 { + if self + .corners + .iter() + .enumerate() + .find(|(i, &c)| c != other.corners[(i + shift) % 3]) + .is_none() + { + return true; + } + } + + false + } +} + #[derive(PartialEq, Eq)] pub(crate) enum TripletOrientation { Clockwise, @@ -186,6 +206,21 @@ mod test { assert!(!triangle.contains_point(Vec2::new(-2., -2.))); } + #[test] + fn equality() { + let a = Vec2::new(0., 0.); + let b = Vec2::new(-1., -1.); + let c = Vec2::new(-2., 0.); + let d = Vec2::new(-3., 0.); + + let cmp = Triangle::new(a, b, c); + + assert_eq!(Triangle::new(a, b, c), cmp); + assert_eq!(Triangle::new(c, b, a), cmp); + assert_eq!(Triangle::new(b, a, c), cmp); + assert!(Triangle::new(a, b, d) != cmp); + } + #[test] fn triplet_angle() { assert_eq!( -- 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') 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