From 77f2d35cb52d9443e9a0e9250aa941fc3d7610b6 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Wed, 25 Nov 2020 21:38:38 +0100 Subject: Add polygon rooms that can actually kind of be used It's still kind of strange to use the polygon tool, but at least it seems stable enough so I'm confident enough (and sick enough of it) to release it into the wild. --- src/math/polygon/mod.rs | 133 +++++++++++++++++++++++++++++++------- src/math/polygon/polygon_graph.rs | 20 +++--- src/math/polygon/triangulate.rs | 3 +- 3 files changed, 122 insertions(+), 34 deletions(-) (limited to 'src/math/polygon') diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs index 90d46bb..e1f15c5 100644 --- a/src/math/polygon/mod.rs +++ b/src/math/polygon/mod.rs @@ -12,6 +12,21 @@ use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar}; use num_traits::Zero; use serde::{Deserialize, Serialize}; use std::ops::Neg; +use thiserror::Error; + +/// Describes errors that can happen when handling polygons, especially on creation. +#[derive(Debug, Error)] +pub enum PolygonError { + /// Since the polygon is not allowed to be complex, self intersection is an error. + #[error("the polygon intersects with itself with edges `{0:?}` and `{1:?}`")] + SelfIntersect(LineSegment, LineSegment), + #[error("polygons need at least 3 vertices to be valid, `{0}` where provided")] + TooFewVertices(usize), + #[error("vertex `{0:?}` with corner id `{1}` is or would be in the polygon twice")] + VertexDoubling(Vec2, usize), + #[error("line `{0:?}` is not a polygon edge")] + EdgeNotFound(LineSegment), +} #[derive(Clone, Debug, Deserialize, Serialize)] // TODO: Support polygons with holes @@ -22,17 +37,29 @@ pub struct Polygon { impl Polygon { /// Create a new polygon from the provided corners. If the corners are right-turning, they will /// be reversed to be left-turning. - /// - /// # Panics - /// If one tries to create a polygon with less than three corners, it will fail. Zero area - /// polygons however are allowed at the moment. - pub fn new(corners: Vec>) -> Self + /// Checks if the corners make a valid polygon before creating it. If the check fails, an error + /// will be returned. + pub fn new(corners: Vec>) -> Result> where T: RealField, { - if corners.len() < 3 { - panic!("Cannot create polygon with less than three corners."); - } + Self::check_validity(&corners)?; + + let corners = if combined_angle(&corners) > T::zero() { + corners + } else { + corners.into_iter().rev().collect() + }; + + Ok(Self { corners }) + } + + /// Like new, but does not perform any validity checks, so be careful when using this function. + pub fn new_unchecked(corners: Vec>) -> Self + where + T: RealField, + { + assert!(Polygon::check_validity(&corners).is_ok()); let corners = if combined_angle(&corners) > T::zero() { corners @@ -43,22 +70,67 @@ impl Polygon { Self { corners } } + /// Checks if a set of corners can be made into a polygon or not. Returns Ok if they can, or + /// the reason they cannot in form of a PolygonError. + pub fn check_validity(corners: &[Vec2]) -> Result<(), PolygonError> + where + T: RealField, + { + if corners.len() < 3 { + return Err(PolygonError::TooFewVertices(corners.len())); + } + + // Check that all vertices are in the slice only once. + for i in 0..corners.len() { + for j in (i + 1)..corners.len() { + if corners[i] == corners[j] { + return Err(PolygonError::VertexDoubling(corners[i], i)); + } + } + } + + // Check that no edges cross paths, except the edges that are right next to each other, + // which must intersect with each other on the common vertex. + if corners.len() > 3 { + for i in 0..corners.len() - 2 { + let line_i = LineSegment::new(corners[i], corners[i + 1]); + let end_j = if i == 0 { + corners.len() - 1 + } else { + corners.len() + }; + for j in (i + 2)..end_j { + let next_j = (j + 1) % corners.len(); + let line_j = LineSegment::new(corners[j], corners[next_j]); + + if LineSegment::intersect(&line_i, &line_j) { + return Err(PolygonError::SelfIntersect(line_i, line_j)); + } + } + } + } + + Ok(()) + } + /// Add a vertex as a corner between the two provided neighbours. The direction of the /// neighbours is not relevant. The edge between the two will be replaced with two edges to the - /// new corner from each of the neighbours respectively. - /// If there already is a point `corner` in the polygon, this function will fail and return - /// `false`. It will do nothing and return `false` if the provided neighbours are not actually - /// neighbours in the polygon already. - /// Otherwise it will perform the addition and return `true`. + /// new corner from each of the neighbours respectively. On success, the method returns the + /// position of the corner in the corners list. + /// + /// # Failures + /// If the corner is already present in the polygon's vertex list, the method will throw a + /// VertexDoubling-Error. If no matching neighbour-pair can be found, an EdgeNotFound-Error + /// will be thrown. pub fn add_corner( &mut self, corner: Vec2, neighbour1: &Vec2, neighbour2: &Vec2, - ) -> bool { + ) -> Result> { // Check that the corners do not contain the corner vector already. - if self.corners.iter().find(|&c| *c == corner).is_some() { - return false; + if let Some(pos) = self.corners.iter().position(|&c| c == corner) { + return Err(PolygonError::VertexDoubling(corner, pos)); } for i in 0..self.corners.len() { @@ -66,16 +138,19 @@ impl Polygon { if self.corners[i] == *neighbour1 && self.corners[next] == *neighbour2 { self.corners.insert(next, corner); - return true; + return Ok(next); } if self.corners[i] == *neighbour2 && self.corners[next] == *neighbour1 { self.corners.insert(next, corner); - return true; + return Ok(next); } } // No matching neighbour pair can be found. - false + Err(PolygonError::EdgeNotFound(LineSegment::new( + *neighbour1, + *neighbour2, + ))) } /// Get the corners of this polygon in left-turning direction. @@ -307,8 +382,6 @@ fn combined_angle(points: &Vec>) -> T { combined_angle += angle - T::pi(); } - println!("Calculated combined angle: {} Pi", combined_angle / T::pi()); - combined_angle } @@ -316,6 +389,12 @@ fn combined_angle(points: &Vec>) -> T { mod test { use super::*; + #[test] + fn check_validity() { + Polygon::check_validity(&[Vec2::new(0., 0.), Vec2::new(1., 0.), Vec2::new(0., 1.)]) + .expect("Simple triangle does not pass validity check"); + } + #[test] fn polygon_contains() { let polygon = Polygon::new(vec![ @@ -326,7 +405,8 @@ mod test { Vec2::new(3., 1.5), Vec2::new(2., 0.), Vec2::new(1., 1.), - ]); + ]) + .unwrap(); assert!(!polygon.contains_point(&Vec2::new(1., -2.))); assert!(!polygon.contains_point(&Vec2::new(-1., 0.5))); @@ -351,7 +431,8 @@ mod test { Vec2::new(2., 0.5), Vec2::new(4., 2.), Vec2::new(4., 0.), - ]); + ]) + .unwrap(); /* 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. @@ -403,14 +484,16 @@ mod test { Vec2::new(0.5, 1.5), Vec2::new(1., 0.), Vec2::new(-0.5, 1.), - ]); + ]) + .unwrap(); let second = Polygon::new(vec![ Vec2::new(0., 0.), Vec2::new(-2., 2.), Vec2::new(3., 2.), Vec2::new(1.5, 0.), - ]); + ]) + .unwrap(); let union = first.unite(second); assert_eq!(union.len(), 1); diff --git a/src/math/polygon/polygon_graph.rs b/src/math/polygon/polygon_graph.rs index 6fdb6cd..5a730b0 100644 --- a/src/math/polygon/polygon_graph.rs +++ b/src/math/polygon/polygon_graph.rs @@ -291,7 +291,7 @@ impl PolygonGraph { .expect("Failure to find node that should be inside list.")]; } - Polygon::new(bounding_corners) + Polygon::new(bounding_corners).expect("PolygonGraph produced invalid polygon") } } @@ -311,7 +311,7 @@ mod test { let b = Vec2::new(0., 1.); let c = Vec2::new(0.5, 1.); - let triangle = Polygon::new(vec![a, b, c]); + let triangle = Polygon::new(vec![a, b, c]).unwrap(); let graph = PolygonGraph::from_polygon(&triangle); assert_eq!(graph.num_edges(), 3); @@ -333,9 +333,9 @@ mod test { 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 triangle = Polygon::new(vec![top_left, bot_right, top_right]).unwrap(); - let square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]); + let square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]).unwrap(); let mut graph = PolygonGraph::new(); graph.add_all(&triangle); @@ -368,7 +368,8 @@ mod test { Vec2::new(2., 2.), Vec2::new(3., 1.), Vec2::new(2., 0.), - ]); + ]) + .unwrap(); let second = Polygon::new(vec![ Vec2::new(2.5, -0.5), @@ -376,7 +377,8 @@ mod test { Vec2::new(2., 2.), Vec2::new(2., 0.5), Vec2::new(2.5, 0.), - ]); + ]) + .unwrap(); let mut graph = PolygonGraph::from_polygon(&first); graph.add_all(&second); @@ -406,7 +408,8 @@ mod test { Vec2::new(2., 2.), Vec2::new(3., 1.), Vec2::new(2., 0.), - ]); + ]) + .unwrap(); let second = Polygon::new(vec![ Vec2::new(2.5, -0.5), @@ -414,7 +417,8 @@ mod test { Vec2::new(2., 2.), Vec2::new(2., 0.5), Vec2::new(2.5, 0.), - ]); + ]) + .unwrap(); let mut graph = PolygonGraph::from_polygon(&first); graph.add_all(&second); diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs index 78dfa03..4c7d952 100644 --- a/src/math/polygon/triangulate.rs +++ b/src/math/polygon/triangulate.rs @@ -136,7 +136,8 @@ mod test { Vec2::new(2., 0.5), Vec2::new(4., 2.), Vec2::new(4., 0.), - ]); + ]) + .unwrap(); let triangles = super::triangulate(polygon); -- cgit v1.2.3-70-g09d2