diff options
| -rw-r--r-- | Cargo.lock | 21 | ||||
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/math/polygon/mod.rs | 133 | ||||
| -rw-r--r-- | src/math/polygon/polygon_graph.rs | 20 | ||||
| -rw-r--r-- | src/math/polygon/triangulate.rs | 3 | ||||
| -rw-r--r-- | src/tool/polygon_room_tool.rs | 184 |
6 files changed, 293 insertions, 69 deletions
@@ -147,6 +147,7 @@ dependencies = [ "ron", "serde", "svgtypes", + "thiserror", "xmltree", ] @@ -501,6 +502,26 @@ dependencies = [ ] [[package]] +name = "thiserror" +version = "1.0.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "0e9ae34b84616eedaaf1e9dd6026dbe00dcafa92aa0c8077cb69df1fcfe5e53e" +dependencies = [ + "thiserror-impl", +] + +[[package]] +name = "thiserror-impl" +version = "1.0.22" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9ba20f23e85b10754cd195504aebf6a27e2e6cbe28c17778a0c930724628dd56" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] name = "thread_local" version = "1.0.1" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -15,3 +15,4 @@ svgtypes = "*" xmltree = "*" pretty_env_logger = "*" log = "*" +thiserror = "*" 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<T: Scalar + Copy> { + /// 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<T>, LineSegment<T>), + #[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<T>, usize), + #[error("line `{0:?}` is not a polygon edge")] + EdgeNotFound(LineSegment<T>), +} #[derive(Clone, Debug, Deserialize, Serialize)] // TODO: Support polygons with holes @@ -22,17 +37,29 @@ pub struct Polygon<T: Scalar + Copy> { impl<T: Scalar + Copy> Polygon<T> { /// 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<Vec2<T>>) -> 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<Vec2<T>>) -> Result<Self, PolygonError<T>> 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<Vec2<T>>) -> 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<T: Scalar + Copy> Polygon<T> { 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<T>]) -> Result<(), PolygonError<T>> + 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<T>, neighbour1: &Vec2<T>, neighbour2: &Vec2<T>, - ) -> bool { + ) -> Result<usize, PolygonError<T>> { // 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<T: Scalar + Copy> Polygon<T> { 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<T: Scalar + Copy + RealField>(points: &Vec<Vec2<T>>) -> T { combined_angle += angle - T::pi(); } - println!("Calculated combined angle: {} Pi", combined_angle / T::pi()); - combined_angle } @@ -317,6 +390,12 @@ 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![ Vec2::new(0., 0.), @@ -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<T: Scalar + Copy + PartialOrd> PolygonGraph<T> { .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); diff --git a/src/tool/polygon_room_tool.rs b/src/tool/polygon_room_tool.rs index b37774b..58f326f 100644 --- a/src/tool/polygon_room_tool.rs +++ b/src/tool/polygon_room_tool.rs @@ -4,18 +4,85 @@ use crate::config::{PolygonRoomToolKeybindings, ToolKeybindings}; use crate::dimension_indicator::DimensionIndicator; use crate::grid::{snap_to_grid, SNAP_SIZE}; use crate::map_data::MapData; -use crate::math::{self, Polygon, Vec2}; +use crate::math::{self, Polygon, PolygonError, Vec2}; use crate::transform::Transform; use raylib::core::drawing::{RaylibDraw, RaylibDrawHandle}; use raylib::ffi::Color; use raylib::RaylibHandle; +struct UnfinishedPolygon { + pub corners: Vec<Vec2<f32>>, + pub working_corner: Vec2<f32>, +} + pub struct PolygonRoomTool { keybindings: PolygonRoomToolKeybindings, - unfinished_polygon: Option<Vec<Vec2<f32>>>, + unfinished_polygon: Option<UnfinishedPolygon>, dimension_indicator: DimensionIndicator, } +impl UnfinishedPolygon { + // Check the validity of the already completed corners only + pub fn check_validity_completed(&self) -> Result<(), PolygonError<f32>> { + Polygon::check_validity(&self.corners) + } + + // Check the validity of the already completed corners, but with the working corner wedged + // between the last and first corner (making it the new last corner). + pub fn check_validity_all(&self) -> Result<(), PolygonError<f32>> { + // TODO: Is this possible without changing the mutability of self and without reallocation? + let mut corners = self.corners.clone(); + corners.push(self.working_corner); + let res = Polygon::check_validity(&corners); + + res + } + + pub fn try_into_completed(&mut self) -> Option<Polygon<f32>> { + match self.check_validity_completed() { + Ok(()) => Some(Polygon::new_unchecked(self.corners.drain(..).collect())), + Err(e) => { + warn!("Cannot turn placed corners into a polygon: {}", e); + None + } + } + } + + pub fn try_into_all(&mut self) -> Option<Polygon<f32>> { + match self.check_validity_all() { + Ok(()) => { + self.corners.push(self.working_corner); + Some(Polygon::new_unchecked(self.corners.drain(..).collect())) + } + Err(e) => { + warn!( + "Cannot turn corners with newest corner into a polygon: {}", + e + ); + None + } + } + } + + pub fn try_push_working(&mut self) -> Result<(), PolygonError<f32>> { + assert!(self.corners.len() >= 1); + + if self.corners.len() == 1 { + return if self.corners[0] != self.working_corner { + self.corners.push(self.working_corner); + Ok(()) + } else { + Err(PolygonError::VertexDoubling(self.corners[0], 0)) + }; + } + + self.check_validity_all()?; + self.corners.push(self.working_corner); + + Ok(()) + } +} + impl PolygonRoomTool { pub fn new(keybindings: PolygonRoomToolKeybindings) -> Self { Self { @@ -42,40 +109,55 @@ impl Tool for PolygonRoomTool { ) { let mouse_pos_m = transform.point_px_to_m(rl.get_mouse_position().into()); let snapped_mouse_pos_m = snap_to_grid(mouse_pos_m, SNAP_SIZE); + // Update the position of the node that would be placed into the polygon next. - if let Some(ref mut corners) = &mut self.unfinished_polygon { - let last_element = corners.len() - 1; - corners[last_element] = snapped_mouse_pos_m; - self.dimension_indicator.update_dimensions(&corners); + if let Some(ref mut polygon) = &mut self.unfinished_polygon { + polygon.working_corner = snapped_mouse_pos_m; + + polygon.corners.push(polygon.working_corner); + self.dimension_indicator.update_dimensions(&polygon.corners); + polygon.working_corner = polygon.corners.pop().unwrap(); } - if self.keybindings.finish.is_pressed(rl, mouse_blocked) - && self.unfinished_polygon.is_some() - { - // Make sure the polygon is at least a triangle, so it can be drawn. - if self.unfinished_polygon.as_ref().unwrap().len() >= 3 { - let polygon = Polygon::new(self.unfinished_polygon.take().unwrap()); - self.dimension_indicator.clear_dimensions(); - map.polygons_mut().push(polygon); + /* Check if the finishing keybinding has been pressed. If so, try to turn the part of the + * polygon that is already completed into a proper polygon and push it into the map data. + */ + if self.keybindings.finish.is_pressed(rl, mouse_blocked) { + if let Some(ref mut polygon) = self.unfinished_polygon { + if let Some(polygon) = polygon.try_into_completed() { + self.dimension_indicator.clear_dimensions(); + map.polygons_mut().push(polygon); + self.unfinished_polygon = None; + } } } + /* Handle placing a new corner of the polygon. If the corner is placed on the first node, + * the polygon will be created. + */ if self.keybindings.place_node.is_pressed(rl, mouse_blocked) { - if let Some(ref mut corners) = self.unfinished_polygon.as_mut() { - if snapped_mouse_pos_m == corners[0] { - // Make sure the polygon is at least a triangle, so it can be drawn. - if corners.len() >= 3 { - // The last corner is redundant. - corners.pop(); - let polygon = Polygon::new(self.unfinished_polygon.take().unwrap()); + if let Some(ref mut polygon) = &mut self.unfinished_polygon { + if polygon.working_corner == polygon.corners[0] { + /* The working corner will be ignored, since it would double the vertex at the + * polygon starting position. + */ + if let Some(polygon) = polygon.try_into_completed() { self.dimension_indicator.clear_dimensions(); map.polygons_mut().push(polygon); + self.unfinished_polygon = None; } } else { - corners.push(snapped_mouse_pos_m); + // Check if we can add the corner to the polygon without ruining it. + if let Err(e) = polygon.try_push_working() { + error!("Cannot add corner to polygon: {}", e); + } } } else { - self.unfinished_polygon = Some(vec![snapped_mouse_pos_m, snapped_mouse_pos_m]); + // Start a new unfinished polygon + self.unfinished_polygon = Some(UnfinishedPolygon { + corners: vec![snapped_mouse_pos_m], + working_corner: snapped_mouse_pos_m, + }); } } @@ -104,15 +186,12 @@ impl Tool for PolygonRoomTool { } } - // Draw the current polygon - if let Some(corners) = &self.unfinished_polygon { - let mut corners = corners.clone(); - corners.dedup(); - match corners.len() { - 0 | 1 => {} - 2 => rld.draw_line_ex( - transform.point_m_to_px(corners[0]), - transform.point_m_to_px(corners[1]), + if let Some(polygon) = &self.unfinished_polygon { + // The first corner is guaranteed to be set, so we can at least draw a line. + if polygon.corners.len() == 1 { + rld.draw_line_ex( + transform.point_m_to_px(polygon.corners[0]), + transform.point_m_to_px(polygon.working_corner), transform.length_m_to_px(0.1), Color { r: 150, @@ -120,9 +199,43 @@ impl Tool for PolygonRoomTool { b: 150, a: 255, }, - ), - _ => { - let polygon = Polygon::new(corners); + ); + } else if polygon.corners.len() == 2 { + // We have three valid corners, so we can draw a triangle. + rld.draw_triangle( + transform.point_m_to_px(polygon.corners[0]), + transform.point_m_to_px(polygon.corners[1]), + transform.point_m_to_px(polygon.working_corner), + Color { + r: 150, + g: 200, + b: 150, + a: 255, + }, + ) + } else { + // A proper polygon can be drawn. + if polygon.check_validity_all().is_ok() { + let mut corners = polygon.corners.clone(); + corners.push(polygon.working_corner); + let polygon = Polygon::new_unchecked(corners); + let triangles = math::triangulate(polygon); + for triangle in triangles { + let triangle: [Vec2<f32>; 3] = triangle.into(); + rld.draw_triangle( + transform.point_m_to_px(triangle[0]), + transform.point_m_to_px(triangle[1]), + transform.point_m_to_px(triangle[2]), + Color { + r: 150, + g: 200, + b: 150, + a: 255, + }, + ) + } + } else if polygon.check_validity_completed().is_ok() { + let polygon = Polygon::new_unchecked(polygon.corners.clone()); let triangles = math::triangulate(polygon); for triangle in triangles { let triangle: [Vec2<f32>; 3] = triangle.into(); @@ -140,6 +253,7 @@ impl Tool for PolygonRoomTool { } } } + self.dimension_indicator.draw(rld, transform); } } |