aboutsummaryrefslogtreecommitdiff
path: root/src/math/polygon
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/polygon')
-rw-r--r--src/math/polygon/mod.rs177
-rw-r--r--src/math/polygon/polygon_graph.rs463
-rw-r--r--src/math/polygon/triangulate.rs13
3 files changed, 653 insertions, 0 deletions
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<T: Scalar + Copy> {
+ pub corners: Vec<Vec2<T>>,
+}
+
+impl<T: Scalar + Copy> Polygon<T> {
+ pub fn new(corners: Vec<Vec2<T>>) -> 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<T>) -> bool
+ where
+ T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg<Output = T> + 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<T>) -> Vec<Polygon<T>>
+ 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<T: Scalar + Copy> {
+ pub vec: Vec2<T>,
+ pub adjacent: Vec<Vec2<T>>,
+}
+
+struct EdgeIterator<'a, T: Scalar + Copy> {
+ nodes: &'a [Node<T>],
+ 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<T: Scalar + Copy + PartialOrd> {
+ /// The nodes of the graph, together with their adjacency list.
+ nodes: Vec<Node<T>>,
+}
+// Helper functions to find nodes/vecs in sorted fields, so It doesn't always have to be written
+// out.
+#[inline]
+fn find_vec2<T: Scalar + Copy + PartialOrd>(
+ field: &[Vec2<T>],
+ lookup: &Vec2<T>,
+) -> Result<usize, usize> {
+ field.binary_search_by(|n| n.partial_cmp(lookup).unwrap_or(Ordering::Greater))
+}
+#[inline]
+fn find_node<T: Scalar + Copy + PartialOrd>(
+ field: &[Node<T>],
+ lookup: &Vec2<T>,
+) -> Result<usize, usize> {
+ 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<T>]) -> Self {
+ Self { nodes, pos: (0, 0) }
+ }
+}
+
+impl<'a, T: Scalar + Copy> Iterator for EdgeIterator<'a, T> {
+ type Item = LineSegment<T>;
+
+ fn next(&mut self) -> Option<Self::Item> {
+ // 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<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
+ /// 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<T>, to: &Vec2<T>) -> 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<T>, to: &Vec2<T>) -> 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<T>, to: &Vec2<T>) -> 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<T>, to: &Vec2<T>) -> 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<T>, to: &Vec2<T>) -> 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<T>) -> 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<T>) {
+ 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<LineSegment<T>> = Vec::new();
+ let mut to_add: Vec<(Vec2<T>, Vec2<T>)> = 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<Vec2<T>> = 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<T>
+ 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<T: Scalar + Copy + PartialOrd> Default for PolygonGraph<T> {
+ 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<T: Scalar + Copy>(_polygon: &Polygon<T>) -> Vec<Triangle<T>> {
+ unimplemented!()
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.1) at 2025-12-06 10:31:43 +0000