1 files changed, 48 insertions, 19 deletions
diff --git a/src/math/polygon/polygon_graph.rs b/src/math/polygon/polygon_graph.rs
index fd373dd..5e3a576 100644
--- a/src/math/polygon/polygon_graph.rs
+++ b/src/math/polygon/polygon_graph.rs
@@ -5,16 +5,18 @@
 
 use super::Polygon;
 use crate::math::{self, LineSegment, Vec2};
+use float_cmp::ApproxEq;
 use nalgebra::{RealField, Scalar};
 use std::cmp::{Ordering, PartialOrd};
 
-#[derive(Debug)]
-struct Node<T: Scalar + Copy> {
+#[derive(Debug, Clone)]
+pub(super) struct Node<T: Scalar + Copy> {
     pub vec: Vec2<T>,
     pub adjacent: Vec<Vec2<T>>,
 }
 
-struct EdgeIterator<'a, T: Scalar + Copy> {
+/// An iterator over the graph edges. These are not in a particular order.
+pub struct EdgeIterator<'a, T: Scalar + Copy> {
     nodes: &'a [Node<T>],
     pos: (usize, usize),
 }
@@ -22,7 +24,7 @@ struct EdgeIterator<'a, T: Scalar + Copy> {
 /// An undirected graph, that is optimised for polygon edge operations. Since edges of a polygon
 /// are an undirected graph, this structure also holds both directions. This makes it rather space
 /// inefficient, but makes edge operations rather swift.
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct PolygonGraph<T: Scalar + Copy + PartialOrd> {
     /// The nodes of the graph, together with their adjacency list.
     nodes: Vec<Node<T>>,
@@ -45,7 +47,7 @@ fn find_node<T: Scalar + Copy + PartialOrd>(
 }
 
 impl<'a, T: Scalar + Copy> EdgeIterator<'a, T> {
-    pub fn new(nodes: &'a [Node<T>]) -> Self {
+    pub(super) fn new(nodes: &'a [Node<T>]) -> Self {
         Self { nodes, pos: (0, 0) }
     }
 }
@@ -114,6 +116,11 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
     // 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 {
+        // Cannot add self-referential edges.
+        if from == to {
+            return false;
+        }
+
         match find_node(&self.nodes, from) {
             Ok(pos) => match find_vec2(&self.nodes[pos].adjacent, to) {
                 Ok(_) => return false,
@@ -131,8 +138,10 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
         true
     }
 
-    /// Add an edge between the given vectors. If the edge already exists, it does nothing and
-    /// returns false, otherwise it returns true after addition.
+    /// Add an edge between the given vectors. If the edge already exists or the starting and end
+    /// point are the same, it does nothing and returns false, otherwise it returns true after
+    /// addition. Note, that in a normal graph adding a self-referential edge would be perfectly fine,
+    /// but in a graph representing a polygon this does not really make sense.
     pub fn add_edge(&mut self, from: &Vec2<T>, to: &Vec2<T>) -> bool {
         if !self.add_edge_onesided(from, to) {
             return false;
@@ -204,9 +213,10 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
     /// 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<M>(&mut self, margin: M)
     where
-        T: RealField,
+        T: RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
         // Find all intersections with all other edges.
         let mut to_delete: Vec<LineSegment<T>> = Vec::new();
@@ -216,12 +226,14 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
              * intersecting with.
              */
             let mut intersections: Vec<Vec2<T>> = Vec::new();
-            for compare_segment in EdgeIterator::new(&self.nodes) {
+            for compare_segment in self.edge_iter() {
                 if segment.eq_ignore_dir(&compare_segment) {
                     continue;
                 }
 
-                if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) {
+                if let Some(intersection) =
+                    LineSegment::intersection(&segment, &compare_segment, margin)
+                {
                     intersections.push(intersection);
                 }
             }
@@ -233,7 +245,7 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
             to_delete.push(segment.clone());
 
             // Safe, since at least the line segment itself is represented.
-            let segments = segment.segments(&intersections);
+            let segments = segment.segments(&intersections, margin);
             for i in 1..segments.len() {
                 to_add.push((segments[i - 1], segments[i]));
             }
@@ -247,16 +259,32 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
         }
     }
 
+    /// Get an iterator over all edges in the graph.
+    pub fn edge_iter(&self) -> EdgeIterator<T> {
+        EdgeIterator::new(&self.nodes)
+    }
+
+    /// Check if the the graph has a vertex (node) at the given position. Returns true if so.
+    /// A point that lies on an edge, but is not registered as a node will not count.
+    pub fn has_node(&self, at: &Vec2<T>) -> bool {
+        find_node(&self.nodes, at).is_ok()
+    }
+
     /// Finds the minimal polygon that could hold this graph together, i.e. could contain the
     /// entire graph, but with the minimal amount of space. It may however still contain extra
     /// corner points, meaning an extra edge for three collinear points on this edge, that can be
     /// cleaned up.
-    pub fn bounding_polygon(mut self) -> Polygon<T>
+    /// If the graph cannot be turned into a polygon, it will return `None`
+    pub fn bounding_polygon<M>(mut self, margin: M) -> Option<Polygon<T>>
     where
-        T: RealField,
+        T: RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
-        assert!(self.num_nodes() >= 3);
-        self.intersect_self();
+        if self.num_nodes() < 3 {
+            return None;
+        }
+
+        self.intersect_self(margin);
 
         /* Start with the top-left node. Since the nodes are always sorted by y over x from top to
          * bottom and left to right, this is the very first element in the vector. This is also a
@@ -279,8 +307,8 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
                 .adjacent
                 .iter()
                 .max_by(|&a, &b| {
-                    math::triplet_angle(last_vec, current_node.vec, *a)
-                        .partial_cmp(&math::triplet_angle(last_vec, current_node.vec, *b))
+                    math::triplet_angle(last_vec, current_node.vec, *a, margin)
+                        .partial_cmp(&math::triplet_angle(last_vec, current_node.vec, *b, margin))
                         .unwrap_or(Ordering::Equal)
                 })
                 .expect("Adjacency list is empty. The polygon has an open edge (is broken)");
@@ -296,7 +324,8 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
                 .expect("Failure to find node that should be inside list.")];
         }
 
-        Polygon::new(bounding_corners).expect("PolygonGraph produced invalid polygon")
+        // Try to create a polygon from the corners and return it.
+        Polygon::new(bounding_corners, margin).ok()
     }
 }