From 53d376eaeef991850d35318b147f75c8f103319d Mon Sep 17 00:00:00 2001
From: Arne Dußin
Date: Sun, 27 Dec 2020 21:54:31 +0100
Subject: Change to polygongraph instead of polygon in roomtool

The polygon room tool used a convoluted process for determining what the
user actually wants to draw. I have changed to the polygon graph
instead, which makes the checks easier and restricts the user a bit
less. In the process however I found a serious problem with my handling
float, so everything needed to change to margin compares (which I of
course should have done in the beginning. Guys, take the warning
seriously and don't ignore it for ten years like I did. It will come
back to haunt you.. apparently) instead of direct equality.
---
 src/math/polygon/triangulate.rs | 59 ++++++++++++++++++++++++-----------------
 1 file changed, 34 insertions(+), 25 deletions(-)

(limited to 'src/math/polygon/triangulate.rs')

diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs
index 8a18cd7..4106095 100644
--- a/src/math/polygon/triangulate.rs
+++ b/src/math/polygon/triangulate.rs
@@ -2,7 +2,8 @@
 
 use super::Polygon;
 use crate::math::{self, LineSegment, Surface, Triangle};
-use nalgebra::{RealField, Scalar};
+use float_cmp::ApproxEq;
+use nalgebra::RealField;
 
 /// Type that saves the flags that match a corner in a space efficient manner.
 type Flags = u8;
@@ -16,9 +17,10 @@ const FLAG_EAR: Flags = 0b0000_0001;
 // used. Consider removing it entirely.
 const FLAG_CONVEX: Flags = 0b0000_0010;
 
-fn flag_corner<T: Scalar + Copy>(polygon: &Polygon<T>, corner: usize) -> Flags
+fn flag_corner<T: RealField, M>(polygon: &Polygon<T>, corner: usize, margin: M) -> Flags
 where
-    T: RealField,
+    T: ApproxEq<Margin = M>,
+    M: Copy,
 {
     // 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();
@@ -31,6 +33,7 @@ where
         polygon.corners[prev],
         polygon.corners[corner],
         polygon.corners[next],
+        margin,
     ) < T::pi()
     {
         // The corner is reflex.
@@ -38,10 +41,10 @@ where
     }
 
     // The corner is convex, check if it is also an ear.
-    if polygon.contains_line_segment(&LineSegment::new(
-        polygon.corners[prev],
-        polygon.corners[next],
-    )) {
+    if polygon.contains_line_segment(
+        &LineSegment::new(polygon.corners[prev], polygon.corners[next]),
+        margin,
+    ) {
         // Corner is an ear.
         FLAG_EAR | FLAG_CONVEX
     } else {
@@ -50,13 +53,14 @@ where
     }
 }
 
-/// Uses earclipping algorithm (see https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf)
+/// 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>>
+pub fn triangulate<T: RealField, M>(mut polygon: Polygon<T>, margin: M) -> Vec<Triangle<T>>
 where
-    T: RealField,
+    T: ApproxEq<Margin = M>,
+    M: Copy,
 {
     assert!(polygon.corners.len() >= 3);
     /* Information about the corner of the polygon. See the flags constant for information about
@@ -64,7 +68,7 @@ where
      */
     let mut flags = Vec::with_capacity(polygon.corners.len());
     for c in 0..polygon.corners.len() {
-        flags.push(flag_corner(&polygon, c));
+        flags.push(flag_corner(&polygon, c, margin));
     }
 
     let mut triangles = Vec::with_capacity(polygon.corners.len() - 2);
@@ -91,6 +95,7 @@ where
                 polygon.corners[prev],
                 polygon.corners[ear],
                 polygon.corners[next],
+                margin,
             ));
 
             // Remove the ear from the polygon and the flag list.
@@ -107,8 +112,8 @@ where
         };
         let next = if ear == polygon.corners.len() { 0 } else { ear };
 
-        flags[prev] = flag_corner(&polygon, prev);
-        flags[next] = flag_corner(&polygon, next);
+        flags[prev] = flag_corner(&polygon, prev, margin);
+        flags[next] = flag_corner(&polygon, next, margin);
     }
 
     // Push the remaining triangle into the list.
@@ -116,6 +121,7 @@ where
         polygon.corners[0],
         polygon.corners[1],
         polygon.corners[2],
+        margin,
     ));
 
     triangles
@@ -128,18 +134,21 @@ mod test {
 
     #[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 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.),
+            ],
+            (f64::EPSILON, 0),
+        )
         .unwrap();
 
         let triangles = super::triangulate(polygon);
-- 
cgit v1.2.3-70-g09d2