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 +- src/tool/polygon_room_tool.rs | 184 ++++++++++++++++++++++++++++++-------- 4 files changed, 271 insertions(+), 69 deletions(-) (limited to 'src') 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); 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>, + pub working_corner: Vec2, +} + pub struct PolygonRoomTool { keybindings: PolygonRoomToolKeybindings, - unfinished_polygon: Option>>, + unfinished_polygon: Option, dimension_indicator: DimensionIndicator, } +impl UnfinishedPolygon { + // Check the validity of the already completed corners only + pub fn check_validity_completed(&self) -> Result<(), PolygonError> { + 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> { + // 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> { + 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> { + 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> { + 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; 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; 3] = triangle.into(); @@ -140,6 +253,7 @@ impl Tool for PolygonRoomTool { } } } + self.dimension_indicator.draw(rld, transform); } } -- cgit v1.2.3-70-g09d2