aboutsummaryrefslogtreecommitdiff
path: root/src/math/polygon
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/polygon')
-rw-r--r--src/math/polygon/mod.rs341
-rw-r--r--src/math/polygon/polygon_graph.rs463
-rw-r--r--src/math/polygon/triangulate.rs149
3 files changed, 953 insertions, 0 deletions
diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
new file mode 100644
index 0000000..cda1f2a
--- /dev/null
+++ b/src/math/polygon/mod.rs
@@ -0,0 +1,341 @@
+//! 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::{LineSegment, Surface, TripletOrientation, Vec2};
+use crate::math;
+use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar};
+use num_traits::Zero;
+use serde::{Deserialize, Serialize};
+use std::ops::Neg;
+
+#[derive(Debug, Deserialize, Serialize)]
+// 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.
+
+ /// 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()]
+ }
+}
+
+impl<
+ T: Scalar
+ + Copy
+ + ClosedSub
+ + ClosedMul
+ + ClosedDiv
+ + Neg<Output = T>
+ + PartialOrd
+ + RealField
+ + Zero,
+ > Surface<T> for Polygon<T>
+{
+ fn contains_point(&self, p: &Vec2<T>) -> bool {
+ 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
+ }
+
+ fn contains_line_segment(&self, line_segment: &LineSegment<T>) -> bool {
+ /* In case at least one of the points is not contained by the polygon, the line cannot lie
+ * inside of the polygon in its entirety.
+ */
+ if !self.contains_point(&line_segment.start) || !self.contains_point(&line_segment.end) {
+ return false;
+ }
+
+ /* Both end-points are inside the polygon. */
+
+ /* In case the an endpoint of the line segment is equal to a corner of the polygon, it's
+ * not enough to merely check one edge, since if the corner is reflex, the segment may
+ * still be inside, eventhough its similar to the outwards pointing normal of one edge, but
+ * may be to the inside of the other edge.
+ */
+ let mut start_looks_inside = false;
+ let mut end_looks_inside = false;
+ /* Helper function that checks if a point p, when starting from the given corner c is in a
+ * direction so that considering both edges that are connected to c, the point is in the
+ * direction of the inside of the polygon.
+ */
+ let corner_vec_pointing_inside = |p: Vec2<T>, c: usize| {
+ let prev = (c + self.corners.len() - 1) % self.corners.len();
+ let next = (c + 1) % self.corners.len();
+
+ let edge_angle =
+ math::triplet_angle(self.corners[prev], self.corners[c], self.corners[next]);
+ let vec_angle = math::triplet_angle(self.corners[prev], self.corners[c], p);
+
+ vec_angle == T::zero() || vec_angle >= edge_angle
+ };
+
+ for c in 0..self.corners.len() {
+ if line_segment.start == self.corners[c] {
+ start_looks_inside = corner_vec_pointing_inside(line_segment.end, c);
+ if !start_looks_inside {
+ return false;
+ }
+ }
+ if line_segment.end == self.corners[c] {
+ end_looks_inside = corner_vec_pointing_inside(line_segment.start, c);
+ if !end_looks_inside {
+ return false;
+ }
+ }
+ }
+
+ if start_looks_inside && end_looks_inside {
+ return true;
+ }
+
+ /* Check the intersections of the line segment with all polygon edges and see if it is
+ * piercing through any of them.
+ */
+ for c in 0..self.corners.len() {
+ let next = (c + 1) % self.corners.len();
+
+ let current_edge = LineSegment::new(self.corners[c], self.corners[next]);
+
+ if LineSegment::intersect(&line_segment, &current_edge) {
+ let orientation_start = math::triplet_orientation(
+ current_edge.start,
+ current_edge.end,
+ line_segment.start,
+ );
+ let orientation_end = math::triplet_orientation(
+ current_edge.start,
+ current_edge.end,
+ line_segment.end,
+ );
+ match (orientation_start, orientation_end) {
+ /* If at least one of the points is on the edge, make sure, the line points
+ * inside of the polygon, not to the outside.
+ */
+ (TripletOrientation::Collinear, o) => {
+ if !start_looks_inside && o == TripletOrientation::Clockwise {
+ return false;
+ }
+ }
+ (o, TripletOrientation::Collinear) => {
+ if !end_looks_inside && o == TripletOrientation::Clockwise {
+ return false;
+ }
+ }
+ /* Start and endpoint are on different sides of the edge, therefore the line
+ * must be partially outside.
+ */
+ _ => return false,
+ }
+ }
+ }
+
+ true
+ }
+}
+
+#[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 contains_line_segment() {
+ let polygon = Polygon::new(vec![
+ Vec2::new(0., 0.),
+ Vec2::new(0., 4.5),
+ Vec2::new(6.5, 4.5),
+ Vec2::new(5.5, 0.),
+ Vec2::new(5.5, 3.),
+ Vec2::new(1.5, 3.),
+ Vec2::new(1.5, 1.),
+ Vec2::new(2., 0.5),
+ Vec2::new(4., 2.),
+ Vec2::new(4., 0.),
+ ]);
+
+ /* 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.
+ */
+
+ // Start point really inside, end point really inside. Line not completely inside.
+ assert!(!polygon
+ .contains_line_segment(&LineSegment::new(Vec2::new(2.5, 0.5), Vec2::new(0.5, 2.5))));
+
+ // Start point on edge, end point on corner, line completely outside.
+ assert!(!polygon
+ .contains_line_segment(&LineSegment::new(Vec2::new(1.5, 2.), Vec2::new(4., 2.))));
+
+ // Start point on edge, end point on edge, line inside.
+ assert!(polygon
+ .contains_line_segment(&LineSegment::new(Vec2::new(3.5, 3.), Vec2::new(3.5, 4.5))));
+
+ // Start point on corner, end point on corner, line inside.
+ assert!(polygon
+ .contains_line_segment(&LineSegment::new(Vec2::new(5.5, 3.), Vec2::new(6.5, 4.5))));
+
+ // Start point really inside, end point on edge. Line not inside.
+ assert!(!polygon
+ .contains_line_segment(&LineSegment::new(Vec2::new(3.5, 0.5), Vec2::new(5.5, 0.5))));
+
+ // Start point and endpoint outside. Line completely outside.
+ assert!(!polygon
+ .contains_line_segment(&LineSegment::new(Vec2::new(7.0, 0.), Vec2::new(7.5, 1.))));
+
+ // Start point on vertex, pointing in same dir as one of the adjacent edge normals,
+ // completely inside.
+ assert!(
+ polygon.contains_line_segment(&LineSegment::new(Vec2::new(2., 0.5), Vec2::new(4., 0.)))
+ );
+
+ // Start and end point on vertex, not pointing in the dir of adjacent edge normals,
+ // not completely inside.
+ assert!(
+ !polygon.contains_line_segment(&LineSegment::new(Vec2::new(4., 2.), Vec2::new(0., 0.)))
+ );
+ }
+
+ #[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..78dfa03
--- /dev/null
+++ b/src/math/polygon/triangulate.rs
@@ -0,0 +1,149 @@
+//! Module for turning a polygon into a number of non-overlapping triangles.
+
+use super::Polygon;
+use crate::math::{self, LineSegment, Surface, Triangle};
+use nalgebra::{RealField, Scalar};
+
+/// Type that saves the flags that match a corner in a space efficient manner.
+type Flags = u8;
+
+/// Tells the algorithm that this corner of the polygon is an ear. An ear means the adjacent corners
+/// form a triangle with this corner of which the area is entirely contained by the polygon itself.
+const FLAG_EAR: Flags = 0b0000_0001;
+/// Tells the algorithm that this corner is convex, meaning its internal angle is less than Pi.
+/// Useful, because this is a necessary condition for earness. False if the vertex is reflex.
+// TODO: The convex flag is a remnant from the previous algorithm, but currently it's not being
+// used. Consider removing it entirely.
+const FLAG_CONVEX: Flags = 0b0000_0010;
+
+fn flag_corner<T: Scalar + Copy>(polygon: &Polygon<T>, corner: usize) -> Flags
+where
+ T: RealField,
+{
+ // First, check if it is convex. If it is not, it can also not be an ear.
+ let prev = (corner + polygon.corners.len() - 1) % polygon.corners.len();
+ let next = (corner + 1) % polygon.corners.len();
+
+ /* Since the angle is also in counterclockwise direction, like the polygon itself, the corner
+ * is convex if and only if the angle is **not**.
+ */
+ if math::triplet_angle(
+ polygon.corners[prev],
+ polygon.corners[corner],
+ polygon.corners[next],
+ ) < T::pi()
+ {
+ // The corner is reflex.
+ return 0b0;
+ }
+
+ // The corner is convex, check if it is also an ear.
+ if polygon.contains_line_segment(&LineSegment::new(
+ polygon.corners[prev],
+ polygon.corners[next],
+ )) {
+ // Corner is an ear.
+ FLAG_EAR | FLAG_CONVEX
+ } else {
+ // Corner is not an ear.
+ FLAG_CONVEX
+ }
+}
+
+/// 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>(mut polygon: Polygon<T>) -> Vec<Triangle<T>>
+where
+ T: RealField,
+{
+ assert!(polygon.corners.len() >= 3);
+ /* Information about the corner of the polygon. See the flags constant for information about
+ * what the bits mean.
+ */
+ let mut flags = Vec::with_capacity(polygon.corners.len());
+ for c in 0..polygon.corners.len() {
+ flags.push(flag_corner(&polygon, c));
+ }
+
+ let mut triangles = Vec::with_capacity(polygon.corners.len() - 2);
+ // Clip ears until there's only the last triangle left.
+ /* NOTE: This could be changed to > 2 and the last triangle would be pushed inside the loop,
+ * because it is also detected as an ear, however this is more logical to the original idea
+ * imo.
+ */
+ while polygon.corners.len() > 3 {
+ // Find the ear with the highest index.
+ let ear = flags
+ .iter()
+ .rposition(|&x| (x & FLAG_EAR) != 0)
+ .expect("Polygon has more than three vertices, but no ear.");
+
+ // Add the ear's triangle to the list.
+ {
+ let prev = (ear + polygon.corners.len() - 1) % polygon.corners.len();
+ let next = (ear + 1) % polygon.corners.len();
+ triangles.push(Triangle::new(
+ polygon.corners[prev],
+ polygon.corners[ear],
+ polygon.corners[next],
+ ));
+
+ // Remove the ear from the polygon and the flag list.
+ polygon.corners.remove(ear);
+ flags.remove(ear);
+ }
+
+ // Reassess the status of the two adjacent points. Notice that since the ear was removed,
+ // their array positions have changed.
+ let prev = if ear == 0 || ear == polygon.corners.len() {
+ polygon.corners.len() - 1
+ } else {
+ ear - 1
+ };
+ let next = if ear == polygon.corners.len() { 0 } else { ear };
+
+ flags[prev] = flag_corner(&polygon, prev);
+ flags[next] = flag_corner(&polygon, next);
+ }
+
+ // Push the remaining triangle into the list.
+ triangles.push(Triangle::new(
+ polygon.corners[0],
+ polygon.corners[1],
+ polygon.corners[2],
+ ));
+
+ triangles
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+ use crate::math::Vec2;
+
+ #[test]
+ fn triangulate() {
+ let polygon = Polygon::new(vec![
+ Vec2::new(0., 0.),
+ Vec2::new(0., 4.5),
+ Vec2::new(6.5, 4.5),
+ Vec2::new(5.5, 0.),
+ Vec2::new(5.5, 3.),
+ Vec2::new(1.5, 3.),
+ Vec2::new(1.5, 1.),
+ Vec2::new(2., 0.5),
+ Vec2::new(4., 2.),
+ Vec2::new(4., 0.),
+ ]);
+
+ let triangles = super::triangulate(polygon);
+
+ assert_eq!(triangles.len(), 8);
+ assert_eq!(
+ triangles[0],
+ (Triangle::new(Vec2::new(2., 0.5), Vec2::new(4., 2.), Vec2::new(4., 0.)))
+ );
+ }
+}
generated by cgit v1.2.3-70-g09d2 (git 2.51.1) at 2025-12-06 09:41:54 +0000