From a22faae428f7ff51a0b2eaea902e5b5ed1a7c8a5 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Wed, 11 Nov 2020 21:36:44 +0100 Subject: Add polygon that can check if a point is inside ..except for one super super edgy edge case, but I wanted to get this algorithm out into a commit before I ruin it completely (probably) --- src/math/polygon.rs | 112 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 112 insertions(+) create mode 100644 src/math/polygon.rs (limited to 'src/math/polygon.rs') diff --git a/src/math/polygon.rs b/src/math/polygon.rs new file mode 100644 index 0000000..e70cd2c --- /dev/null +++ b/src/math/polygon.rs @@ -0,0 +1,112 @@ +use super::{LineSegment, TripletOrientation, Vec2}; +use alga::general::{ClosedMul, ClosedSub}; +use nalgebra::Scalar; +use num_traits::Zero; + +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(&self, point: Vec2) -> bool + where + T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero, + { + // Must be at least a triangle to contain anything + if self.corners.len() < 3 { + return false; + } + + /* What's happening here: + * + * This algorithm creates a horizontal line for the point that should be checked. It goes + * to infinity (since infinite lines are not possible, it just goes to the maximum x value + * of all corner points). Then, the times the line crosses a polygon edge is counted. If + * the times it hit a polygon edge is uneven, it must have been inside, otherwise outside. + * + * There is an edge case however (pun not intended); When the line from the point is collinear + * to a polygon edge. it might hit this edge once and no other (it's at the top y or bottom y + * of the polygon), but may still not be inside the polygon. In this case, it's checked + * whether the point is in between the corner points of this polygon edge or not. If it is + * in between, it is still inside the polygon, otherwise outside. + */ + + // Get the maximum x for the horizontal lines for "Infinity". + let mut max_x = self.corners[0].x; + for corner in self.corners.iter().skip(1) { + max_x = super::partial_max(corner.x, max_x); + } + println!("Max x is {:?}", max_x); + // The horizontally "infinite" point of the test point. + let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y)); + + // Check for intersection for all the polygon edges. + let mut num_intersects = 0; + for i in 0..self.corners.len() { + // Wrap around for the edge that returns to the start. + let j = (i + 1) % self.corners.len(); + let current_edge = LineSegment::new(self.corners[i], self.corners[j]); + + if LineSegment::intersect(¤t_edge, &line_to_infinity) { + /* Check for the edge case, where the point might lie right on an edge of the + * polygon. + */ + if super::triplet_orientation(current_edge.start, current_edge.end, point) + == TripletOrientation::Collinear + { + // The point is right on an edge + if current_edge.contains_collinear(point) { + return true; + } + } else { + num_intersects += 1; + } + } + } + + num_intersects % 2 == 1 + } + + /// Join this polygon with another, ensuring the area of the two stays the same, minus the + /// overlap. + /// + /// # Panics + /// If the two polygons do not intersect, it is impossible to unite them into a single polygon, + /// in which case this function is bound to fail. + // TODO: Create a function that only tries to join the polygons. + pub fn unite(&mut self, mut _other: Polygon) { + unimplemented!() + } +} + +#[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(Vec2::new(1., -2.))); + assert!(!polygon.contains(Vec2::new(-1., 0.5))); + assert!(polygon.contains(Vec2::new(0., 0.5))); + assert!(polygon.contains(Vec2::new(0.5, 1.))); + assert!(polygon.contains(Vec2::new(0.5, 1.5))); + assert!(!polygon.contains(Vec2::new(-2., 1.9))); + assert!(!polygon.contains(Vec2::new(0., 3.))); + } +} -- cgit v1.2.3-70-g09d2 From 8ae528e9a2b219c5ac2f0b967c0cb91e79921e21 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Thu, 12 Nov 2020 23:37:43 +0100 Subject: Fix the polygon point containment algorithm The algorithm before was really not working for a lot of edge cases and very difficult to adapt. This version is definitely not the be-all and end-all, but it should work for most (well, hopefully all) cases. After refactoring and hopefully simplifying and straightening out the logic a little more, it should be verifiable. --- src/math/line_segment.rs | 1 + src/math/polygon.rs | 111 ++++++++++++++++++++++++++++++++++------------- 2 files changed, 83 insertions(+), 29 deletions(-) (limited to 'src/math/polygon.rs') diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index d7bcdb1..338a681 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -3,6 +3,7 @@ use alga::general::{ClosedMul, ClosedSub}; use nalgebra::Scalar; use num_traits::Zero; +#[derive(Debug)] pub struct LineSegment { pub start: Vec2, pub end: Vec2, diff --git a/src/math/polygon.rs b/src/math/polygon.rs index e70cd2c..2af669a 100644 --- a/src/math/polygon.rs +++ b/src/math/polygon.rs @@ -23,54 +23,106 @@ impl Polygon { return false; } - /* What's happening here: - * - * This algorithm creates a horizontal line for the point that should be checked. It goes - * to infinity (since infinite lines are not possible, it just goes to the maximum x value - * of all corner points). Then, the times the line crosses a polygon edge is counted. If - * the times it hit a polygon edge is uneven, it must have been inside, otherwise outside. - * - * There is an edge case however (pun not intended); When the line from the point is collinear - * to a polygon edge. it might hit this edge once and no other (it's at the top y or bottom y - * of the polygon), but may still not be inside the polygon. In this case, it's checked - * whether the point is in between the corner points of this polygon edge or not. If it is - * in between, it is still inside the polygon, otherwise outside. - */ - // Get the maximum x for the horizontal lines for "Infinity". let mut max_x = self.corners[0].x; - for corner in self.corners.iter().skip(1) { + for corner in self.corners.iter() { + /* Handle the edge case where the point is on a polygon corner, so we don't have to + * worry about it later. + */ + if point == *corner { + return true; + } + max_x = super::partial_max(corner.x, max_x); } - println!("Max x is {:?}", max_x); + // The horizontally "infinite" point of the test point. let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y)); - // Check for intersection for all the polygon edges. - let mut num_intersects = 0; + // The number of times the point line to infinity pierced through the polygon hull. + let mut num_pierced = 0; + + /* Find edges that should be ignored. These are all edges, where the straight line passes + * right through a corner of the edge. It might still be counted as piercing the polygon, + * if the next corners lie below and the previous corner lies above the line or vice + * versa, but not if both points lie above it or below. The corners are exempted from the + * run through the edges. The edges that should be ignored are saved by their starting + * corner's index. + */ + let mut ignore_edge = vec![false; self.corners.len()]; for i in 0..self.corners.len() { - // Wrap around for the edge that returns to the start. - let j = (i + 1) % self.corners.len(); - let current_edge = LineSegment::new(self.corners[i], self.corners[j]); + if point.y == self.corners[i].y { + // The previous corner index + let prev_i = (i + self.corners.len() - 1) % self.corners.len(); + + // Make sure the edges containing this corner will be ignored. + ignore_edge[i] = true; + ignore_edge[prev_i] = true; + + /* Make sure we don't count a pierce double because of consecutive collinear + * points. (Although the polygon really should be sanitised, but you know) + */ + if self.corners[prev_i].y == point.y { + continue; + } + + /* Ignore coming collinear points, since we are only interested in when the + * y-coordinate finally changes + */ + let mut j = (i + 1) % self.corners.len(); + while i != j { + if self.corners[j].y != point.y { + if (self.corners[prev_i].y < point.y && self.corners[j].y > point.y) + || (self.corners[prev_i].y > point.y && self.corners[j].y < point.y) + { + /* Only count as pierced when it would be right of the point, otherwise + * it would be like checking to the left of the line that is drawn to + * infinity, which is incorrect + */ + if self.corners[i].x >= point.x { + //println!("Pierced through corner {:?}", self.corners[i]); + num_pierced += 1; + } + } + + break; + } + + j = (j + 1) % self.corners.len(); + } + } + } + + // Find the points where the x-line may actually collide with a proper line.. ^^ + for (i, edge_start) in self.corners.iter().enumerate() { + if ignore_edge[i] { + continue; + } + + let next = (i + 1) % self.corners.len(); + let current_edge = LineSegment::new(*edge_start, self.corners[next]); if LineSegment::intersect(¤t_edge, &line_to_infinity) { + num_pierced += 1; + //println!("Pierced through edge: {:?}", ¤t_edge); + /* Check for the edge case, where the point might lie right on an edge of the * polygon. */ - if super::triplet_orientation(current_edge.start, current_edge.end, point) + if super::triplet_orientation(*edge_start, current_edge.end, point) == TripletOrientation::Collinear { - // The point is right on an edge - if current_edge.contains_collinear(point) { - return true; - } - } else { - num_intersects += 1; + // The point should be right on an edge. + // XXX: Should this not just be an assertion? It seems that this always has to + // be the case when reaching this part. + return current_edge.contains_collinear(point); } } } - num_intersects % 2 == 1 + //println!("Num pierced is: {}", num_pierced); + + num_pierced % 2 == 1 } /// Join this polygon with another, ensuring the area of the two stays the same, minus the @@ -108,5 +160,6 @@ mod test { assert!(polygon.contains(Vec2::new(0.5, 1.5))); assert!(!polygon.contains(Vec2::new(-2., 1.9))); assert!(!polygon.contains(Vec2::new(0., 3.))); + assert!(polygon.contains(Vec2::new(1., 3.))); } } -- cgit v1.2.3-70-g09d2 From 63f292010e51ad8622cccc4d4b6da887e4eaec47 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sun, 15 Nov 2020 20:38:14 +0100 Subject: Add intersection point algorithm --- src/math/line_segment.rs | 43 ++++++++- src/math/polygon.rs | 228 +++++++++++++++++++++++------------------------ 2 files changed, 153 insertions(+), 118 deletions(-) (limited to 'src/math/polygon.rs') diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index 338a681..7dacf54 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -1,6 +1,6 @@ -use super::Vec2; -use alga::general::{ClosedMul, ClosedSub}; -use nalgebra::Scalar; +use super::{Rect, Vec2}; +use alga::general::{ClosedDiv, ClosedMul, ClosedSub}; +use nalgebra::{RealField, Scalar}; use num_traits::Zero; #[derive(Debug)] @@ -89,6 +89,43 @@ impl LineSegment { false } + + pub fn intersection(line_a: &LineSegment, line_b: &LineSegment) -> Option> + where + T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField, + { + // Calculate the differences of each line value from starting point to end point + // coordinate. + let dax = line_a.end.x - line_a.start.x; + let dbx = line_b.end.x - line_b.start.x; + let day = line_a.end.y - line_a.start.y; + let dby = line_b.end.y - line_b.start.y; + + // Calculate determinant to see, if the lines are parallel or not + // TODO: Collinearity check? + let d = (dax * dby) - (day * dbx); + if d == T::zero() { + None + } else { + let ad = (line_a.start.x * line_a.end.y) - (line_a.start.y * line_a.end.x); + let bd = (line_b.start.x * line_b.end.y) - (line_b.start.y * line_b.end.x); + + let out = Vec2::new(((ad * dbx) - (dax * bd)) / d, ((ad * dby) - (day * bd)) / d); + + /* Since the line intersection, not the line segment intersection is calculated, a + * bounding check is necessary, to see if the intersection still lies inside both of + * 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) + { + Some(out) + } else { + None + } + } + } } #[derive(PartialEq, Eq)] diff --git a/src/math/polygon.rs b/src/math/polygon.rs index 2af669a..e761136 100644 --- a/src/math/polygon.rs +++ b/src/math/polygon.rs @@ -1,8 +1,9 @@ -use super::{LineSegment, TripletOrientation, Vec2}; -use alga::general::{ClosedMul, ClosedSub}; -use nalgebra::Scalar; +use super::Vec2; +use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, Scalar}; use num_traits::Zero; +use std::ops::Neg; +#[derive(Debug)] pub struct Polygon { pub corners: Vec>, } @@ -14,125 +15,90 @@ 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(&self, point: Vec2) -> bool + pub fn contains_point(&self, p: Vec2) -> bool where - T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero, + T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, { - // Must be at least a triangle to contain anything - if self.corners.len() < 3 { - return false; - } - - // Get the maximum x for the horizontal lines for "Infinity". - let mut max_x = self.corners[0].x; - for corner in self.corners.iter() { - /* Handle the edge case where the point is on a polygon corner, so we don't have to - * worry about it later. - */ - if point == *corner { - return true; + 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; } - - max_x = super::partial_max(corner.x, max_x); + lup = by > ay; } - // The horizontally "infinite" point of the test point. - let line_to_infinity = LineSegment::new(point, Vec2::new(max_x, point.y)); - - // The number of times the point line to infinity pierced through the polygon hull. - let mut num_pierced = 0; - - /* Find edges that should be ignored. These are all edges, where the straight line passes - * right through a corner of the edge. It might still be counted as piercing the polygon, - * if the next corners lie below and the previous corner lies above the line or vice - * versa, but not if both points lie above it or below. The corners are exempted from the - * run through the edges. The edges that should be ignored are saved by their starting - * corner's index. - */ - let mut ignore_edge = vec![false; self.corners.len()]; - for i in 0..self.corners.len() { - if point.y == self.corners[i].y { - // The previous corner index - let prev_i = (i + self.corners.len() - 1) % self.corners.len(); - - // Make sure the edges containing this corner will be ignored. - ignore_edge[i] = true; - ignore_edge[prev_i] = true; - - /* Make sure we don't count a pierce double because of consecutive collinear - * points. (Although the polygon really should be sanitised, but you know) - */ - if self.corners[prev_i].y == point.y { - continue; - } - - /* Ignore coming collinear points, since we are only interested in when the - * y-coordinate finally changes - */ - let mut j = (i + 1) % self.corners.len(); - while i != j { - if self.corners[j].y != point.y { - if (self.corners[prev_i].y < point.y && self.corners[j].y > point.y) - || (self.corners[prev_i].y > point.y && self.corners[j].y < point.y) - { - /* Only count as pierced when it would be right of the point, otherwise - * it would be like checking to the left of the line that is drawn to - * infinity, which is incorrect - */ - if self.corners[i].x >= point.x { - //println!("Pierced through corner {:?}", self.corners[i]); - num_pierced += 1; - } - } - - break; - } - - j = (j + 1) % self.corners.len(); - } + 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; } - } - // Find the points where the x-line may actually collide with a proper line.. ^^ - for (i, edge_start) in self.corners.iter().enumerate() { - if ignore_edge[i] { + if ay == by && (if ax < bx { ax } else { bx }) <= T::zero() { + return true; + } + if ay == by { continue; } - let next = (i + 1) % self.corners.len(); - let current_edge = LineSegment::new(*edge_start, self.corners[next]); - - if LineSegment::intersect(¤t_edge, &line_to_infinity) { - num_pierced += 1; - //println!("Pierced through edge: {:?}", ¤t_edge); - - /* Check for the edge case, where the point might lie right on an edge of the - * polygon. - */ - if super::triplet_orientation(*edge_start, current_edge.end, point) - == TripletOrientation::Collinear - { - // The point should be right on an edge. - // XXX: Should this not just be an assertion? It seems that this always has to - // be the case when reaching this part. - return current_edge.contains_collinear(point); - } + 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; } - } - //println!("Num pierced is: {}", num_pierced); + lup = by > ay; + } - num_pierced % 2 == 1 + (depth & 1) == 1 } - /// Join this polygon with another, ensuring the area of the two stays the same, minus the - /// overlap. - /// - /// # Panics - /// If the two polygons do not intersect, it is impossible to unite them into a single polygon, - /// in which case this function is bound to fail. - // TODO: Create a function that only tries to join the polygons. - pub fn unite(&mut self, mut _other: Polygon) { + /// Join this polygon with another, ensuring the area of the two stays the same, but the + /// overlap is not doubled, but instead joined into one. + /// Returns the Polygons themselves, if there is no overlap + // TODO: At the moment, counts holes in the middle as a different polygon. These should be + // attached to the polygon they are inside of. + pub fn unite(self, _other: Polygon) -> Vec> { unimplemented!() } } @@ -153,13 +119,45 @@ mod test { Vec2::new(1., 1.), ]); - assert!(!polygon.contains(Vec2::new(1., -2.))); - assert!(!polygon.contains(Vec2::new(-1., 0.5))); - assert!(polygon.contains(Vec2::new(0., 0.5))); - assert!(polygon.contains(Vec2::new(0.5, 1.))); - assert!(polygon.contains(Vec2::new(0.5, 1.5))); - assert!(!polygon.contains(Vec2::new(-2., 1.9))); - assert!(!polygon.contains(Vec2::new(0., 3.))); - assert!(polygon.contains(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] + 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(), 10); + assert!(union + .corners + .iter() + .find(|&p| p.x == 0. && p.y == 0.) + .is_some()); } } -- cgit v1.2.3-70-g09d2 From 8d99501918393ea0c046d721e6fa6015fe43b70f Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Wed, 18 Nov 2020 21:54:41 +0100 Subject: Implement bounding box function --- src/math/line_segment.rs | 74 +++++++++++++++++++++++++++++++++++++++++++++-- src/math/polygon.rs | 20 ++++++++----- src/math/polygon_graph.rs | 65 +++++++++++++++++++++++++++++++++-------- 3 files changed, 138 insertions(+), 21 deletions(-) (limited to 'src/math/polygon.rs') diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index 2b67783..e6ca70f 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -192,15 +192,57 @@ where * 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::Clockwise, - q if q < T::zero() => TripletOrientation::Counterclockwise, + 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() { @@ -214,4 +256,32 @@ 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/polygon.rs b/src/math/polygon.rs index e761136..5711049 100644 --- a/src/math/polygon.rs +++ b/src/math/polygon.rs @@ -1,9 +1,10 @@ -use super::Vec2; -use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, Scalar}; +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>, } @@ -96,10 +97,15 @@ impl Polygon { /// Join this polygon with another, ensuring the area of the two stays the same, but the /// overlap is not doubled, but instead joined into one. /// Returns the Polygons themselves, if there is no overlap - // TODO: At the moment, counts holes in the middle as a different polygon. These should be - // attached to the polygon they are inside of. - pub fn unite(self, _other: Polygon) -> Vec> { - unimplemented!() + 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()] } } @@ -153,7 +159,7 @@ mod test { println!("Union of the two polygons: {:?}", union); - assert_eq!(union.corners.len(), 10); + assert_eq!(union.corners.len(), 11); assert!(union .corners .iter() diff --git a/src/math/polygon_graph.rs b/src/math/polygon_graph.rs index 43c3bc4..7721cbf 100644 --- a/src/math/polygon_graph.rs +++ b/src/math/polygon_graph.rs @@ -220,10 +220,6 @@ impl PolygonGraph { } if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) { - println!( - "Found intersection between {:?} and {:?}: {:?}", - &segment, &compare_segment, &intersection - ); intersections.push(intersection); } } @@ -253,8 +249,52 @@ impl PolygonGraph { /// 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(&self) -> Polygon { - unimplemented!() + 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 } } @@ -356,6 +396,7 @@ mod test { 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))); } @@ -395,15 +436,15 @@ mod test { assert_eq!( bounding.corners[(start_i + 1) % num_corners], - Vec2::new(0., 2.) + Vec2::new(2., 0.) ); assert_eq!( bounding.corners[(start_i + 2) % num_corners], - Vec2::new(2., 2.) + Vec2::new(2.5, -0.5) ); assert_eq!( bounding.corners[(start_i + 3) % num_corners], - Vec2::new(3., 1.) + Vec2::new(2.5, 0.0) ); assert_eq!( bounding.corners[(start_i + 4) % num_corners], @@ -411,15 +452,15 @@ mod test { ); assert_eq!( bounding.corners[(start_i + 5) % num_corners], - Vec2::new(2.5, 0.0) + Vec2::new(3., 1.) ); assert_eq!( bounding.corners[(start_i + 6) % num_corners], - Vec2::new(2.5, -0.5) + Vec2::new(2., 2.) ); assert_eq!( bounding.corners[(start_i + 7) % num_corners], - Vec2::new(2., 0.) + Vec2::new(0., 2.) ); } } -- cgit v1.2.3-70-g09d2