From 53d376eaeef991850d35318b147f75c8f103319d Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sun, 27 Dec 2020 21:54:31 +0100 Subject: Change to polygongraph instead of polygon in roomtool The polygon room tool used a convoluted process for determining what the user actually wants to draw. I have changed to the polygon graph instead, which makes the checks easier and restricts the user a bit less. In the process however I found a serious problem with my handling float, so everything needed to change to margin compares (which I of course should have done in the beginning. Guys, take the warning seriously and don't ignore it for ten years like I did. It will come back to haunt you.. apparently) instead of direct equality. --- src/math/polygon/polygon_graph.rs | 67 ++++++++++++++++++++++++++++----------- 1 file changed, 48 insertions(+), 19 deletions(-) (limited to 'src/math/polygon/polygon_graph.rs') diff --git a/src/math/polygon/polygon_graph.rs b/src/math/polygon/polygon_graph.rs index fd373dd..5e3a576 100644 --- a/src/math/polygon/polygon_graph.rs +++ b/src/math/polygon/polygon_graph.rs @@ -5,16 +5,18 @@ use super::Polygon; use crate::math::{self, LineSegment, Vec2}; +use float_cmp::ApproxEq; use nalgebra::{RealField, Scalar}; use std::cmp::{Ordering, PartialOrd}; -#[derive(Debug)] -struct Node { +#[derive(Debug, Clone)] +pub(super) struct Node { pub vec: Vec2, pub adjacent: Vec>, } -struct EdgeIterator<'a, T: Scalar + Copy> { +/// An iterator over the graph edges. These are not in a particular order. +pub struct EdgeIterator<'a, T: Scalar + Copy> { nodes: &'a [Node], pos: (usize, usize), } @@ -22,7 +24,7 @@ struct EdgeIterator<'a, T: Scalar + Copy> { /// An undirected graph, that is optimised for polygon edge operations. Since edges of a polygon /// are an undirected graph, this structure also holds both directions. This makes it rather space /// inefficient, but makes edge operations rather swift. -#[derive(Debug)] +#[derive(Debug, Clone)] pub struct PolygonGraph { /// The nodes of the graph, together with their adjacency list. nodes: Vec>, @@ -45,7 +47,7 @@ fn find_node( } impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> { - pub fn new(nodes: &'a [Node]) -> Self { + pub(super) fn new(nodes: &'a [Node]) -> Self { Self { nodes, pos: (0, 0) } } } @@ -114,6 +116,11 @@ impl PolygonGraph { // Helper function to add the edge into the internal graph representation for one side only. // Since to the outside the graph should always be undirected, this must be private. fn add_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { + // Cannot add self-referential edges. + if from == to { + return false; + } + match find_node(&self.nodes, from) { Ok(pos) => match find_vec2(&self.nodes[pos].adjacent, to) { Ok(_) => return false, @@ -131,8 +138,10 @@ impl PolygonGraph { true } - /// Add an edge between the given vectors. If the edge already exists, it does nothing and - /// returns false, otherwise it returns true after addition. + /// Add an edge between the given vectors. If the edge already exists or the starting and end + /// point are the same, it does nothing and returns false, otherwise it returns true after + /// addition. Note, that in a normal graph adding a self-referential edge would be perfectly fine, + /// but in a graph representing a polygon this does not really make sense. pub fn add_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { if !self.add_edge_onesided(from, to) { return false; @@ -204,9 +213,10 @@ impl PolygonGraph { /// Calculates all points where the graph edges intersect with one another. It then adds them /// into the adjacency list such that the intersection point lies between the nodes of the /// lines. - pub fn intersect_self(&mut self) + pub fn intersect_self(&mut self, margin: M) where - T: RealField, + T: RealField + ApproxEq, + M: Copy, { // Find all intersections with all other edges. let mut to_delete: Vec> = Vec::new(); @@ -216,12 +226,14 @@ impl PolygonGraph { * intersecting with. */ let mut intersections: Vec> = Vec::new(); - for compare_segment in EdgeIterator::new(&self.nodes) { + for compare_segment in self.edge_iter() { if segment.eq_ignore_dir(&compare_segment) { continue; } - if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) { + if let Some(intersection) = + LineSegment::intersection(&segment, &compare_segment, margin) + { intersections.push(intersection); } } @@ -233,7 +245,7 @@ impl PolygonGraph { to_delete.push(segment.clone()); // Safe, since at least the line segment itself is represented. - let segments = segment.segments(&intersections); + let segments = segment.segments(&intersections, margin); for i in 1..segments.len() { to_add.push((segments[i - 1], segments[i])); } @@ -247,16 +259,32 @@ impl PolygonGraph { } } + /// Get an iterator over all edges in the graph. + pub fn edge_iter(&self) -> EdgeIterator { + EdgeIterator::new(&self.nodes) + } + + /// Check if the the graph has a vertex (node) at the given position. Returns true if so. + /// A point that lies on an edge, but is not registered as a node will not count. + pub fn has_node(&self, at: &Vec2) -> bool { + find_node(&self.nodes, at).is_ok() + } + /// Finds the minimal polygon that could hold this graph together, i.e. could contain the /// 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(mut self) -> Polygon + /// If the graph cannot be turned into a polygon, it will return `None` + pub fn bounding_polygon(mut self, margin: M) -> Option> where - T: RealField, + T: RealField + ApproxEq, + M: Copy, { - assert!(self.num_nodes() >= 3); - self.intersect_self(); + if self.num_nodes() < 3 { + return None; + } + + self.intersect_self(margin); /* 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 @@ -279,8 +307,8 @@ impl PolygonGraph { .adjacent .iter() .max_by(|&a, &b| { - math::triplet_angle(last_vec, current_node.vec, *a) - .partial_cmp(&math::triplet_angle(last_vec, current_node.vec, *b)) + math::triplet_angle(last_vec, current_node.vec, *a, margin) + .partial_cmp(&math::triplet_angle(last_vec, current_node.vec, *b, margin)) .unwrap_or(Ordering::Equal) }) .expect("Adjacency list is empty. The polygon has an open edge (is broken)"); @@ -296,7 +324,8 @@ impl PolygonGraph { .expect("Failure to find node that should be inside list.")]; } - Polygon::new(bounding_corners).expect("PolygonGraph produced invalid polygon") + // Try to create a polygon from the corners and return it. + Polygon::new(bounding_corners, margin).ok() } } -- cgit v1.2.3-70-g09d2