From 8d99501918393ea0c046d721e6fa6015fe43b70f Mon Sep 17 00:00:00 2001
From: Arne Dußin
Date: Wed, 18 Nov 2020 21:54:41 +0100
Subject: Implement bounding box function

---
 src/math/polygon_graph.rs | 65 ++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 53 insertions(+), 12 deletions(-)

(limited to 'src/math/polygon_graph.rs')

diff --git a/src/math/polygon_graph.rs b/src/math/polygon_graph.rs
index 43c3bc4..7721cbf 100644
--- a/src/math/polygon_graph.rs
+++ b/src/math/polygon_graph.rs
@@ -220,10 +220,6 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
                 }
 
                 if let Some(intersection) = LineSegment::intersection(&segment, &compare_segment) {
-                    println!(
-                        "Found intersection between {:?} and {:?}: {:?}",
-                        &segment, &compare_segment, &intersection
-                    );
                     intersections.push(intersection);
                 }
             }
@@ -253,8 +249,52 @@ impl<T: Scalar + Copy + PartialOrd> PolygonGraph<T> {
     /// 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(&self) -> Polygon<T> {
-        unimplemented!()
+    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| {
+                    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
     }
 }
 
@@ -356,6 +396,7 @@ mod test {
         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)));
     }
@@ -395,15 +436,15 @@ mod test {
 
         assert_eq!(
             bounding.corners[(start_i + 1) % num_corners],
-            Vec2::new(0., 2.)
+            Vec2::new(2., 0.)
         );
         assert_eq!(
             bounding.corners[(start_i + 2) % num_corners],
-            Vec2::new(2., 2.)
+            Vec2::new(2.5, -0.5)
         );
         assert_eq!(
             bounding.corners[(start_i + 3) % num_corners],
-            Vec2::new(3., 1.)
+            Vec2::new(2.5, 0.0)
         );
         assert_eq!(
             bounding.corners[(start_i + 4) % num_corners],
@@ -411,15 +452,15 @@ mod test {
         );
         assert_eq!(
             bounding.corners[(start_i + 5) % num_corners],
-            Vec2::new(2.5, 0.0)
+            Vec2::new(3., 1.)
         );
         assert_eq!(
             bounding.corners[(start_i + 6) % num_corners],
-            Vec2::new(2.5, -0.5)
+            Vec2::new(2., 2.)
         );
         assert_eq!(
             bounding.corners[(start_i + 7) % num_corners],
-            Vec2::new(2., 0.)
+            Vec2::new(0., 2.)
         );
     }
 }
-- 
cgit v1.2.3-70-g09d2