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/triangle.rs | 161 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 161 insertions(+) create mode 100644 src/math/triangle.rs (limited to 'src/math/triangle.rs') 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 + ); + } +} -- 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/math/triangle.rs') 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/math/triangle.rs') 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 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/math/triangle.rs') 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