From af4f4b91d013384a4af82f48d768ac041662eb20 Mon Sep 17 00:00:00 2001 From: Arne Dußin Date: Wed, 18 Nov 2020 13:01:10 +0100 Subject: Add self intersection for polygon graphs --- src/math/line_segment.rs | 69 ++++++++++++++++++++++++++++++---- src/math/polygon_graph.rs | 95 ++++++++++++++++++++++++++++++++++++++++------- 2 files changed, 143 insertions(+), 21 deletions(-) (limited to 'src/math') diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs index 1c2c01c..2b67783 100644 --- a/src/math/line_segment.rs +++ b/src/math/line_segment.rs @@ -2,8 +2,9 @@ use super::{Rect, Vec2}; use alga::general::{ClosedDiv, ClosedMul, ClosedSub}; use nalgebra::{RealField, Scalar}; use num_traits::Zero; +use std::cmp::Ordering; -#[derive(Debug)] +#[derive(Debug, Clone)] pub struct LineSegment { pub start: Vec2, pub end: Vec2, @@ -23,8 +24,8 @@ impl LineSegment { T: PartialOrd, { point.x <= super::partial_max(self.start.x, self.end.x) - && point.x >= super::partial_max(self.start.x, self.end.x) - && point.y <= super::partial_min(self.start.y, self.end.y) + && point.x >= super::partial_min(self.start.x, self.end.x) + && point.y <= super::partial_max(self.start.y, self.end.y) && point.y >= super::partial_min(self.start.y, self.end.y) } @@ -96,10 +97,10 @@ impl LineSegment { { // Calculate the differences of each line value from starting point to end point // coordinate. - let dax = line_a.end.x - line_a.start.x; - let dbx = line_b.end.x - line_b.start.x; - let day = line_a.end.y - line_a.start.y; - let dby = line_b.end.y - line_b.start.y; + let dax = line_a.start.x - line_a.end.x; + let dbx = line_b.start.x - line_b.end.x; + let day = line_a.start.y - line_a.end.y; + let dby = line_b.start.y - line_b.end.y; // Calculate determinant to see, if the lines are parallel or not // TODO: Collinearity check? @@ -127,6 +128,42 @@ impl LineSegment { } } + /// Find all segments, into which this LineSegment would be splitted, when the points provided + /// would cut the segment. The points must be on the line, otherwise this does not make sense. + /// Also, no segments of length zero (start point = end point) will be created. + pub fn segments(&self, split_points: &[Vec2]) -> Vec> + where + T: ClosedSub + ClosedMul + PartialOrd + Zero, + { + // Make sure all segments are collinear with the segment and actually on it + assert_eq!( + split_points + .iter() + .find(|&p| triplet_orientation(self.start, self.end, *p) + != TripletOrientation::Collinear), + None + ); + assert_eq!( + split_points.iter().find(|&p| !self.contains_collinear(*p)), + None + ); + + let mut segments = Vec::with_capacity(split_points.len() + 2); + segments.push(self.start); + segments.push(self.end); + for point in split_points { + segments.push(*point); + } + + segments.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap_or(Ordering::Greater)); + segments.dedup(); + if self.start > self.end { + segments.reverse(); + } + + segments + } + /// Checks if this line segment and the other line segment are the same, ignoring the direction /// in which the lines are going, in other words, which of the vectors the line starts at and which /// vector the line ends at is irrelevant. @@ -160,3 +197,21 @@ where _ => TripletOrientation::Collinear, } } + +#[cfg(test)] +mod test { + use super::*; + + #[test] + fn contains_collinear() { + let segment = LineSegment::new(Vec2::new(0., 0.), Vec2::new(2., 2.)); + + assert!(segment.contains_collinear(Vec2::new(0., 0.))); + assert!(segment.contains_collinear(Vec2::new(1., 1.))); + assert!(segment.contains_collinear(Vec2::new(2., 2.))); + + assert!(!segment.contains_collinear(Vec2::new(-1., -1.))); + assert!(!segment.contains_collinear(Vec2::new(3., 3.))); + assert!(!segment.contains_collinear(Vec2::new(-1., 0.))); + } +} diff --git a/src/math/polygon_graph.rs b/src/math/polygon_graph.rs index 3acd46f..43c3bc4 100644 --- a/src/math/polygon_graph.rs +++ b/src/math/polygon_graph.rs @@ -1,20 +1,26 @@ use super::{LineSegment, Polygon, Vec2}; -use nalgebra::Scalar; +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 Vec>, + 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] @@ -32,6 +38,35 @@ fn find_node( 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 Vec>) -> 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 { @@ -167,22 +202,51 @@ 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) + where + T: RealField, + { // Find all intersections with all other edges. - for node in &self.nodes { - for to in &node.adjacent { - let current_segment = LineSegment::new(node.vec, *to); - - for node in &self.nodes { - for to in &node.adjacent { - let compare_segment = LineSegment::new(node.vec, *to); - if current_segment.eq_ignore_dir(&compare_segment) { - continue; - } - } + 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) { + println!( + "Found intersection between {:?} and {:?}: {:?}", + &segment, &compare_segment, &intersection + ); + 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 @@ -282,6 +346,9 @@ mod test { graph.intersect_self(); + println!("Intersected graph:"); + println!("{:#?}", &graph); + assert_eq!(graph.num_nodes(), 9); assert_eq!(graph.num_edges(), 12); -- cgit v1.2.3-70-g09d2