From 58ca374fab6dd90c4d7415bdcc98add002274894 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Sat, 21 Nov 2020 11:23:16 +0100 Subject: Move polygon functions into own mod The math module was starting to be mostly polygon files and functions, so those got their own subfolder to make the math module less of a mess. --- src/math/mod.rs | 4 - src/math/polygon.rs | 169 -------------- src/math/polygon/mod.rs | 177 +++++++++++++++ src/math/polygon/polygon_graph.rs | 463 ++++++++++++++++++++++++++++++++++++++ src/math/polygon/triangulate.rs | 13 ++ src/math/polygon_graph.rs | 462 ------------------------------------- src/math/triangulate.rs | 12 - 7 files changed, 653 insertions(+), 647 deletions(-) delete mode 100644 src/math/polygon.rs create mode 100644 src/math/polygon/mod.rs create mode 100644 src/math/polygon/polygon_graph.rs create mode 100644 src/math/polygon/triangulate.rs delete mode 100644 src/math/polygon_graph.rs delete mode 100644 src/math/triangulate.rs (limited to 'src') diff --git a/src/math/mod.rs b/src/math/mod.rs index 07bc36b..e72a7a4 100644 --- a/src/math/mod.rs +++ b/src/math/mod.rs @@ -1,17 +1,13 @@ pub mod line_segment; pub mod polygon; -pub mod polygon_graph; pub mod rect; pub mod triangle; -pub mod triangulate; pub mod vec2; pub use self::line_segment::*; pub use self::polygon::*; -pub use self::polygon_graph::*; pub use self::rect::*; pub use self::triangle::*; -pub use self::triangulate::*; pub use self::vec2::*; use std::cmp::Ordering; diff --git a/src/math/polygon.rs b/src/math/polygon.rs deleted file mode 100644 index 5711049..0000000 --- a/src/math/polygon.rs +++ /dev/null @@ -1,169 +0,0 @@ -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>, -} - -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_point(&self, p: Vec2) -> bool - where - T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, - { - 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; - } - lup = by > ay; - } - - 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; - } - - if ay == by && (if ax < bx { ax } else { bx }) <= T::zero() { - return true; - } - if ay == by { - continue; - } - - 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; - } - - lup = by > ay; - } - - (depth & 1) == 1 - } - - /// 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 - 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()] - } -} - -#[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_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(), 11); - assert!(union - .corners - .iter() - .find(|&p| p.x == 0. && p.y == 0.) - .is_some()); - } -} diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs new file mode 100644 index 0000000..4530857 --- /dev/null +++ b/src/math/polygon/mod.rs @@ -0,0 +1,177 @@ +//! Contains functions and structures to help with operations on polygons. + +pub mod polygon_graph; +pub mod triangulate; + +pub use polygon_graph::*; +pub use triangulate::*; + +use super::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>, +} + +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_point(&self, p: Vec2) -> bool + where + T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg + PartialOrd, + { + 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; + } + lup = by > ay; + } + + 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; + } + + if ay == by && (if ax < bx { ax } else { bx }) <= T::zero() { + return true; + } + if ay == by { + continue; + } + + 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; + } + + lup = by > ay; + } + + (depth & 1) == 1 + } + + /// 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 + 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()] + } +} + +#[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_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(), 11); + assert!(union + .corners + .iter() + .find(|&p| p.x == 0. && p.y == 0.) + .is_some()); + } +} diff --git a/src/math/polygon/polygon_graph.rs b/src/math/polygon/polygon_graph.rs new file mode 100644 index 0000000..9477fbc --- /dev/null +++ b/src/math/polygon/polygon_graph.rs @@ -0,0 +1,463 @@ +use super::Polygon; +use crate::math::{self, LineSegment, Vec2}; +use nalgebra::{RealField, Scalar}; +use std::cmp::{Ordering, PartialOrd}; + +#[derive(Debug)] +struct Node { + pub vec: Vec2, + pub adjacent: Vec>, +} + +struct EdgeIterator<'a, T: Scalar + Copy> { + nodes: &'a [Node], + pos: (usize, usize), +} + +/// 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)] +pub struct PolygonGraph { + /// The nodes of the graph, together with their adjacency list. + nodes: Vec>, +} +// Helper functions to find nodes/vecs in sorted fields, so It doesn't always have to be written +// out. +#[inline] +fn find_vec2( + field: &[Vec2], + lookup: &Vec2, +) -> Result { + field.binary_search_by(|n| n.partial_cmp(lookup).unwrap_or(Ordering::Greater)) +} +#[inline] +fn find_node( + field: &[Node], + lookup: &Vec2, +) -> Result { + field.binary_search_by(|n| n.vec.partial_cmp(lookup).unwrap_or(Ordering::Greater)) +} + +impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> { + pub fn new(nodes: &'a [Node]) -> Self { + Self { nodes, pos: (0, 0) } + } +} + +impl<'a, T: Scalar + Copy> Iterator for EdgeIterator<'a, T> { + type Item = LineSegment; + + fn next(&mut self) -> Option { + // Try to find the element in the nodes vector, if it exists. + if let Some(node) = self.nodes.get(self.pos.0) { + let end = node.adjacent[self.pos.1]; + + // Advance the iterator to the next possible element + if self.pos.1 + 1 < node.adjacent.len() { + self.pos.1 += 1; + } else { + self.pos.1 = 0; + self.pos.0 += 1; + } + + Some(LineSegment::new(node.vec, end)) + } else { + None + } + } +} + +impl PolygonGraph { + /// Create a new, empty polygon graph. + pub fn new() -> Self { + Self { nodes: Vec::new() } + } + + /// Count the number of edges in the graph. Internally, for each two connected points there are + /// two edges, but this returns the amount of polygon edges. + pub fn num_edges(&self) -> usize { + let mut num_edges = 0; + for node in &self.nodes { + for _ in &node.adjacent { + num_edges += 1; + } + } + + assert!(num_edges % 2 == 0); + num_edges / 2 + } + + /// Count the number of nodes in this graph. If this graph consists of multiple polygons, this + /// can be different than the amount of corners, since corners with the same position are only + /// counted once. + pub fn num_nodes(&self) -> usize { + self.nodes.len() + } + + /// Checks if there is an edge between the two given vectors. Is commutative in respect to the + /// two arguments. + pub fn has_edge(&self, from: &Vec2, to: &Vec2) -> bool { + // Binary search the starting and then the end node. + if let Ok(from) = find_node(&self.nodes, from) { + find_vec2(&self.nodes[from].adjacent, to).is_ok() + } else { + false + } + } + + // 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 { + match find_node(&self.nodes, from) { + Ok(pos) => match find_vec2(&self.nodes[pos].adjacent, to) { + Ok(_) => return false, + Err(i) => self.nodes[pos].adjacent.insert(i, *to), + }, + Err(pos) => self.nodes.insert( + pos, + Node { + vec: *from, + adjacent: vec![*to], + }, + ), + } + + 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. + pub fn add_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { + if !self.add_edge_onesided(from, to) { + return false; + } + + let back_edge_succ = self.add_edge_onesided(to, from); + assert!(back_edge_succ); + + true + } + + // Helper function to remove the edge in the internal graph representation for one side only. + // Since to the outside the graph should always be undirected, this must be private. + fn remove_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { + if let Ok(from) = find_node(&self.nodes, from) { + if let Ok(to) = find_vec2(&self.nodes[from].adjacent, to) { + // Remove the edge from the vector. + self.nodes[from].adjacent.remove(to); + + // If the node has no adjacent nodes anymore, remove it entirely. + if self.nodes[from].adjacent.is_empty() { + self.nodes.remove(from); + } + + true + } else { + false + } + } else { + false + } + } + + /// Remove an edge between the given vectors. If there is no edge between them, it does nothing + /// and returns false, otherwise it returns true after deletion. + pub fn remove_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { + if !self.remove_edge_onesided(from, to) { + return false; + } + + let back_edge_succ = self.remove_edge_onesided(to, from); + assert!(back_edge_succ); + + true + } + + /// Constructs a new PolygonGraph from the provided polygon. Adds a node for every corner and + /// an edge to all connected corners (which should be exactly two, for regular polygons) + pub fn from_polygon(polygon: &Polygon) -> Self { + let mut graph = PolygonGraph { + nodes: Vec::with_capacity(polygon.corners.len()), + }; + + graph.add_all(polygon); + graph + } + + /// Add all edges of the provided polygon into the graph. Requires roughly double as much space + /// as the normal polygon. + pub fn add_all(&mut self, polygon: &Polygon) { + for i in 0..polygon.corners.len() { + self.add_edge( + &polygon.corners[i], + &polygon.corners[(i + 1) % polygon.corners.len()], + ); + } + } + + /// 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) + where + T: RealField, + { + // Find all intersections with all other edges. + let mut to_delete: Vec> = Vec::new(); + let mut to_add: Vec<(Vec2, Vec2)> = Vec::new(); + for segment in EdgeIterator::new(&self.nodes) { + /* Save all intersections of this line with any other line, and the line that it's + * intersecting with. + */ + let mut intersections: Vec> = Vec::new(); + for compare_segment in EdgeIterator::new(&self.nodes) { + if segment.eq_ignore_dir(&compare_segment) { + continue; + } + + if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) { + intersections.push(intersection); + } + } + + if intersections.is_empty() { + continue; + } + + to_delete.push(segment.clone()); + + // Safe, since at least the line segment itself is represented. + let segments = segment.segments(&intersections); + for i in 1..segments.len() { + to_add.push((segments[i - 1], segments[i])); + } + } + + for segment in to_delete { + self.remove_edge(&segment.start, &segment.end); + } + for (start, end) in to_add { + self.add_edge(&start, &end); + } + } + + /// 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 + 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| { + math::triplet_angle(last_vec, current_node.vec, *a) + .partial_cmp(&math::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 + } +} + +impl Default for PolygonGraph { + fn default() -> Self { + Self::new() + } +} + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn from_polygon() { + let a = Vec2::new(0., 0.); + let b = Vec2::new(0., 1.); + let c = Vec2::new(0.5, 1.); + + let triangle = Polygon::new(vec![a, b, c]); + + let graph = PolygonGraph::from_polygon(&triangle); + assert_eq!(graph.num_edges(), 3); + + assert!(graph.has_edge(&a, &b)); + assert!(graph.has_edge(&b, &a)); + + assert!(graph.has_edge(&a, &c)); + assert!(graph.has_edge(&c, &a)); + + assert!(graph.has_edge(&b, &c)); + assert!(graph.has_edge(&c, &b)); + } + + #[test] + fn add_all() { + let top_left = Vec2::new(0., 0.); + let top_right = Vec2::new(1., 0.); + 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 square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]); + + let mut graph = PolygonGraph::new(); + graph.add_all(&triangle); + graph.add_all(&square); + + assert_eq!(graph.num_edges(), 5); + assert_eq!(graph.num_nodes(), 4); + + assert!(graph.has_edge(&top_left, &top_right)); + assert!(graph.has_edge(&top_right, &top_left)); + + assert!(graph.has_edge(&top_left, &bot_left)); + assert!(graph.has_edge(&bot_left, &top_left)); + + assert!(graph.has_edge(&bot_left, &bot_right)); + assert!(graph.has_edge(&bot_right, &bot_left)); + + assert!(graph.has_edge(&bot_right, &top_right)); + assert!(graph.has_edge(&top_right, &bot_right)); + + assert!(graph.has_edge(&top_left, &bot_right)); + assert!(graph.has_edge(&bot_right, &top_left)); + } + + #[test] + fn intersect_self() { + let first = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(3., 1.), + Vec2::new(2., 0.), + ]); + + let second = Polygon::new(vec![ + Vec2::new(2.5, -0.5), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(2., 0.5), + Vec2::new(2.5, 0.), + ]); + + let mut graph = PolygonGraph::from_polygon(&first); + graph.add_all(&second); + + graph.intersect_self(); + + println!("Intersected graph:"); + println!("{:#?}", &graph); + + assert_eq!(graph.num_nodes(), 9); + assert_eq!(graph.num_edges(), 12); + + assert!(graph.has_edge(&Vec2::new(2., 0.), &Vec2::new(2.25, 0.25))); + 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))); + } + + #[test] + fn bounding_polygon() { + let first = Polygon::new(vec![ + Vec2::new(0., 0.), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(3., 1.), + Vec2::new(2., 0.), + ]); + + let second = Polygon::new(vec![ + Vec2::new(2.5, -0.5), + Vec2::new(0., 2.), + Vec2::new(2., 2.), + Vec2::new(2., 0.5), + Vec2::new(2.5, 0.), + ]); + + let mut graph = PolygonGraph::from_polygon(&first); + graph.add_all(&second); + + let bounding = graph.bounding_polygon(); + + let num_corners = 8; + assert_eq!(bounding.corners.len(), num_corners); + + // Run around the polygon to see if it was constructed correctly. + let start_i = bounding + .corners + .iter() + .position(|&x| x == Vec2::new(0., 0.)) + .expect("Starting vector does not exist in polygon."); + + assert_eq!( + bounding.corners[(start_i + 1) % num_corners], + Vec2::new(2., 0.) + ); + assert_eq!( + bounding.corners[(start_i + 2) % num_corners], + Vec2::new(2.5, -0.5) + ); + assert_eq!( + bounding.corners[(start_i + 3) % num_corners], + Vec2::new(2.5, 0.0) + ); + assert_eq!( + bounding.corners[(start_i + 4) % num_corners], + Vec2::new(2.25, 0.25) + ); + assert_eq!( + bounding.corners[(start_i + 5) % num_corners], + Vec2::new(3., 1.) + ); + assert_eq!( + bounding.corners[(start_i + 6) % num_corners], + Vec2::new(2., 2.) + ); + assert_eq!( + bounding.corners[(start_i + 7) % num_corners], + Vec2::new(0., 2.) + ); + } +} diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs new file mode 100644 index 0000000..4860518 --- /dev/null +++ b/src/math/polygon/triangulate.rs @@ -0,0 +1,13 @@ +//! Module for turning a polygon into a number of non-overlapping triangles. + +use super::Polygon; +use crate::math::Triangle; +use nalgebra::Scalar; + +/// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) +/// to find an explanation of what exactly is happening. +/// Currently only handles simple polygons, but once the polygon struct supports holes must be +/// extended to also support those. +pub fn triangulate(_polygon: &Polygon) -> Vec> { + unimplemented!() +} diff --git a/src/math/polygon_graph.rs b/src/math/polygon_graph.rs deleted file mode 100644 index 14b2b0d..0000000 --- a/src/math/polygon_graph.rs +++ /dev/null @@ -1,462 +0,0 @@ -use super::{LineSegment, Polygon, Vec2}; -use nalgebra::{RealField, Scalar}; -use std::cmp::{Ordering, PartialOrd}; - -#[derive(Debug)] -struct Node { - pub vec: Vec2, - pub adjacent: Vec>, -} - -struct EdgeIterator<'a, T: Scalar + Copy> { - nodes: &'a [Node], - pos: (usize, usize), -} - -/// 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)] -pub struct PolygonGraph { - /// The nodes of the graph, together with their adjacency list. - nodes: Vec>, -} -// Helper functions to find nodes/vecs in sorted fields, so It doesn't always have to be written -// out. -#[inline] -fn find_vec2( - field: &[Vec2], - lookup: &Vec2, -) -> Result { - field.binary_search_by(|n| n.partial_cmp(lookup).unwrap_or(Ordering::Greater)) -} -#[inline] -fn find_node( - field: &[Node], - lookup: &Vec2, -) -> Result { - field.binary_search_by(|n| n.vec.partial_cmp(lookup).unwrap_or(Ordering::Greater)) -} - -impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> { - pub fn new(nodes: &'a [Node]) -> Self { - Self { nodes, pos: (0, 0) } - } -} - -impl<'a, T: Scalar + Copy> Iterator for EdgeIterator<'a, T> { - type Item = LineSegment; - - fn next(&mut self) -> Option { - // Try to find the element in the nodes vector, if it exists. - if let Some(node) = self.nodes.get(self.pos.0) { - let end = node.adjacent[self.pos.1]; - - // Advance the iterator to the next possible element - if self.pos.1 + 1 < node.adjacent.len() { - self.pos.1 += 1; - } else { - self.pos.1 = 0; - self.pos.0 += 1; - } - - Some(LineSegment::new(node.vec, end)) - } else { - None - } - } -} - -impl PolygonGraph { - /// Create a new, empty polygon graph. - pub fn new() -> Self { - Self { nodes: Vec::new() } - } - - /// Count the number of edges in the graph. Internally, for each two connected points there are - /// two edges, but this returns the amount of polygon edges. - pub fn num_edges(&self) -> usize { - let mut num_edges = 0; - for node in &self.nodes { - for _ in &node.adjacent { - num_edges += 1; - } - } - - assert!(num_edges % 2 == 0); - num_edges / 2 - } - - /// Count the number of nodes in this graph. If this graph consists of multiple polygons, this - /// can be different than the amount of corners, since corners with the same position are only - /// counted once. - pub fn num_nodes(&self) -> usize { - self.nodes.len() - } - - /// Checks if there is an edge between the two given vectors. Is commutative in respect to the - /// two arguments. - pub fn has_edge(&self, from: &Vec2, to: &Vec2) -> bool { - // Binary search the starting and then the end node. - if let Ok(from) = find_node(&self.nodes, from) { - find_vec2(&self.nodes[from].adjacent, to).is_ok() - } else { - false - } - } - - // 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 { - match find_node(&self.nodes, from) { - Ok(pos) => match find_vec2(&self.nodes[pos].adjacent, to) { - Ok(_) => return false, - Err(i) => self.nodes[pos].adjacent.insert(i, *to), - }, - Err(pos) => self.nodes.insert( - pos, - Node { - vec: *from, - adjacent: vec![*to], - }, - ), - } - - 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. - pub fn add_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { - if !self.add_edge_onesided(from, to) { - return false; - } - - let back_edge_succ = self.add_edge_onesided(to, from); - assert!(back_edge_succ); - - true - } - - // Helper function to remove the edge in the internal graph representation for one side only. - // Since to the outside the graph should always be undirected, this must be private. - fn remove_edge_onesided(&mut self, from: &Vec2, to: &Vec2) -> bool { - if let Ok(from) = find_node(&self.nodes, from) { - if let Ok(to) = find_vec2(&self.nodes[from].adjacent, to) { - // Remove the edge from the vector. - self.nodes[from].adjacent.remove(to); - - // If the node has no adjacent nodes anymore, remove it entirely. - if self.nodes[from].adjacent.is_empty() { - self.nodes.remove(from); - } - - true - } else { - false - } - } else { - false - } - } - - /// Remove an edge between the given vectors. If there is no edge between them, it does nothing - /// and returns false, otherwise it returns true after deletion. - pub fn remove_edge(&mut self, from: &Vec2, to: &Vec2) -> bool { - if !self.remove_edge_onesided(from, to) { - return false; - } - - let back_edge_succ = self.remove_edge_onesided(to, from); - assert!(back_edge_succ); - - true - } - - /// Constructs a new PolygonGraph from the provided polygon. Adds a node for every corner and - /// an edge to all connected corners (which should be exactly two, for regular polygons) - pub fn from_polygon(polygon: &Polygon) -> Self { - let mut graph = PolygonGraph { - nodes: Vec::with_capacity(polygon.corners.len()), - }; - - graph.add_all(polygon); - graph - } - - /// Add all edges of the provided polygon into the graph. Requires roughly double as much space - /// as the normal polygon. - pub fn add_all(&mut self, polygon: &Polygon) { - for i in 0..polygon.corners.len() { - self.add_edge( - &polygon.corners[i], - &polygon.corners[(i + 1) % polygon.corners.len()], - ); - } - } - - /// 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) - where - T: RealField, - { - // Find all intersections with all other edges. - let mut to_delete: Vec> = Vec::new(); - let mut to_add: Vec<(Vec2, Vec2)> = Vec::new(); - for segment in EdgeIterator::new(&self.nodes) { - /* Save all intersections of this line with any other line, and the line that it's - * intersecting with. - */ - let mut intersections: Vec> = Vec::new(); - for compare_segment in EdgeIterator::new(&self.nodes) { - if segment.eq_ignore_dir(&compare_segment) { - continue; - } - - if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) { - intersections.push(intersection); - } - } - - if intersections.is_empty() { - continue; - } - - to_delete.push(segment.clone()); - - // Safe, since at least the line segment itself is represented. - let segments = segment.segments(&intersections); - for i in 1..segments.len() { - to_add.push((segments[i - 1], segments[i])); - } - } - - for segment in to_delete { - self.remove_edge(&segment.start, &segment.end); - } - for (start, end) in to_add { - self.add_edge(&start, &end); - } - } - - /// 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 - 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 - } -} - -impl Default for PolygonGraph { - fn default() -> Self { - Self::new() - } -} - -#[cfg(test)] -mod test { - use super::*; - - #[test] - fn from_polygon() { - let a = Vec2::new(0., 0.); - let b = Vec2::new(0., 1.); - let c = Vec2::new(0.5, 1.); - - let triangle = Polygon::new(vec![a, b, c]); - - let graph = PolygonGraph::from_polygon(&triangle); - assert_eq!(graph.num_edges(), 3); - - assert!(graph.has_edge(&a, &b)); - assert!(graph.has_edge(&b, &a)); - - assert!(graph.has_edge(&a, &c)); - assert!(graph.has_edge(&c, &a)); - - assert!(graph.has_edge(&b, &c)); - assert!(graph.has_edge(&c, &b)); - } - - #[test] - fn add_all() { - let top_left = Vec2::new(0., 0.); - let top_right = Vec2::new(1., 0.); - 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 square = Polygon::new(vec![bot_left, bot_right, top_right, top_left]); - - let mut graph = PolygonGraph::new(); - graph.add_all(&triangle); - graph.add_all(&square); - - assert_eq!(graph.num_edges(), 5); - assert_eq!(graph.num_nodes(), 4); - - assert!(graph.has_edge(&top_left, &top_right)); - assert!(graph.has_edge(&top_right, &top_left)); - - assert!(graph.has_edge(&top_left, &bot_left)); - assert!(graph.has_edge(&bot_left, &top_left)); - - assert!(graph.has_edge(&bot_left, &bot_right)); - assert!(graph.has_edge(&bot_right, &bot_left)); - - assert!(graph.has_edge(&bot_right, &top_right)); - assert!(graph.has_edge(&top_right, &bot_right)); - - assert!(graph.has_edge(&top_left, &bot_right)); - assert!(graph.has_edge(&bot_right, &top_left)); - } - - #[test] - fn intersect_self() { - let first = Polygon::new(vec![ - Vec2::new(0., 0.), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(3., 1.), - Vec2::new(2., 0.), - ]); - - let second = Polygon::new(vec![ - Vec2::new(2.5, -0.5), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(2., 0.5), - Vec2::new(2.5, 0.), - ]); - - let mut graph = PolygonGraph::from_polygon(&first); - graph.add_all(&second); - - graph.intersect_self(); - - println!("Intersected graph:"); - println!("{:#?}", &graph); - - assert_eq!(graph.num_nodes(), 9); - assert_eq!(graph.num_edges(), 12); - - assert!(graph.has_edge(&Vec2::new(2., 0.), &Vec2::new(2.25, 0.25))); - 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))); - } - - #[test] - fn bounding_polygon() { - let first = Polygon::new(vec![ - Vec2::new(0., 0.), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(3., 1.), - Vec2::new(2., 0.), - ]); - - let second = Polygon::new(vec![ - Vec2::new(2.5, -0.5), - Vec2::new(0., 2.), - Vec2::new(2., 2.), - Vec2::new(2., 0.5), - Vec2::new(2.5, 0.), - ]); - - let mut graph = PolygonGraph::from_polygon(&first); - graph.add_all(&second); - - let bounding = graph.bounding_polygon(); - - let num_corners = 8; - assert_eq!(bounding.corners.len(), num_corners); - - // Run around the polygon to see if it was constructed correctly. - let start_i = bounding - .corners - .iter() - .position(|&x| x == Vec2::new(0., 0.)) - .expect("Starting vector does not exist in polygon."); - - assert_eq!( - bounding.corners[(start_i + 1) % num_corners], - Vec2::new(2., 0.) - ); - assert_eq!( - bounding.corners[(start_i + 2) % num_corners], - Vec2::new(2.5, -0.5) - ); - assert_eq!( - bounding.corners[(start_i + 3) % num_corners], - Vec2::new(2.5, 0.0) - ); - assert_eq!( - bounding.corners[(start_i + 4) % num_corners], - Vec2::new(2.25, 0.25) - ); - assert_eq!( - bounding.corners[(start_i + 5) % num_corners], - Vec2::new(3., 1.) - ); - assert_eq!( - bounding.corners[(start_i + 6) % num_corners], - Vec2::new(2., 2.) - ); - assert_eq!( - bounding.corners[(start_i + 7) % num_corners], - Vec2::new(0., 2.) - ); - } -} diff --git a/src/math/triangulate.rs b/src/math/triangulate.rs deleted file mode 100644 index 8ef92f1..0000000 --- a/src/math/triangulate.rs +++ /dev/null @@ -1,12 +0,0 @@ -//! Module for turning a polygon into a number of non-overlapping triangles. - -use super::{Polygon, Triangle}; -use nalgebra::Scalar; - -/// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf) -/// to find an explanation of what exactly is happening. -/// Currently only handles simple polygons, but once the polygon struct supports holes must be -/// extended to also support those. -pub fn triangulate(_polygon: &Polygon) -> Vec> { - unimplemented!() -} -- cgit v1.2.3-70-g09d2