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.

1 files changed, 111 insertions, 83 deletions

diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
index 1577f63..bc145ed 100644
--- a/src/math/polygon/mod.rs
+++ b/src/math/polygon/mod.rs
@@ -6,12 +6,12 @@ pub mod triangulate;
 pub use polygon_graph::*;
 pub use triangulate::*;
 
-use super::{LineSegment, Rect, Surface, TripletOrientation, Vec2};
+use super::{ExactSurface, LineSegment, Rect, Surface, TripletOrientation, Vec2};
 use crate::math;
-use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar};
-use num_traits::Zero;
+use float_cmp::ApproxEq;
+use nalgebra::{RealField, Scalar};
 use serde::{Deserialize, Serialize};
-use std::ops::Neg;
+use std::fmt::Debug;
 use thiserror::Error;
 
 /// Describes errors that can happen when handling polygons, especially on creation.
@@ -41,13 +41,14 @@ impl<T: Scalar + Copy> Polygon<T> {
     /// be reversed to be left-turning.
     /// Checks if the corners make a valid polygon before creating it. If the check fails, an error
     /// will be returned.
-    pub fn new(corners: Vec<Vec2<T>>) -> Result<Self, PolygonError<T>>
+    pub fn new<M>(corners: Vec<Vec2<T>>, t_margin: M) -> Result<Self, PolygonError<T>>
     where
-        T: RealField,
+        T: RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
-        Self::check_validity(&corners)?;
+        Self::check_validity(&corners, t_margin)?;
 
-        let corners = if combined_angle(&corners) > T::zero() {
+        let corners = if combined_angle(&corners, t_margin) > T::zero() {
             corners
         } else {
             corners.into_iter().rev().collect()
@@ -57,13 +58,14 @@ impl<T: Scalar + Copy> Polygon<T> {
     }
 
     /// Like new, but does not perform any validity checks, so be careful when using this function.
-    pub fn new_unchecked(corners: Vec<Vec2<T>>) -> Self
+    pub fn new_unchecked<M>(corners: Vec<Vec2<T>>, t_margin: M) -> Self
     where
-        T: RealField,
+        T: RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
-        assert!(Polygon::check_validity(&corners).is_ok());
+        assert!(Polygon::check_validity(&corners, t_margin).is_ok());
 
-        let corners = if combined_angle(&corners) > T::zero() {
+        let corners = if combined_angle(&corners, t_margin) > T::zero() {
             corners
         } else {
             corners.into_iter().rev().collect()
@@ -74,9 +76,10 @@ impl<T: Scalar + Copy> Polygon<T> {
 
     /// Checks if a set of corners can be made into a polygon or not. Returns Ok if they can, or
     /// the reason they cannot in form of a PolygonError.
-    pub fn check_validity(corners: &[Vec2<T>]) -> Result<(), PolygonError<T>>
+    pub fn check_validity<M>(corners: &[Vec2<T>], t_margin: M) -> Result<(), PolygonError<T>>
     where
-        T: RealField,
+        T: RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
         if corners.len() < 3 {
             return Err(PolygonError::TooFewVertices(corners.len()));
@@ -105,7 +108,7 @@ impl<T: Scalar + Copy> Polygon<T> {
                     let next_j = (j + 1) % corners.len();
                     let line_j = LineSegment::new(corners[j], corners[next_j]);
 
-                    if LineSegment::intersect(&line_i, &line_j) {
+                    if LineSegment::intersect(&line_i, &line_j, t_margin) {
                         return Err(PolygonError::SelfIntersect(line_i, line_j));
                     }
                 }
@@ -170,31 +173,28 @@ impl<T: Scalar + Copy> Polygon<T> {
     /// 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>>
+    pub fn unite<M>(self, other: Polygon<T>, t_margin: M) -> Vec<Polygon<T>>
     where
-        T: RealField,
+        T: RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
         let mut graph = PolygonGraph::from_polygon(&self);
         graph.add_all(&other);
 
-        // TODO: Make bounding box support multiple polygons
-        vec![graph.bounding_polygon()]
+        // TODO: Make bounding polygon support multiple polygons
+        match graph.bounding_polygon(t_margin) {
+            Some(polygon) => vec![polygon],
+            None => vec![],
+        }
     }
 }
 
-impl<
-        T: Scalar
-            + Copy
-            + ClosedSub
-            + ClosedMul
-            + ClosedDiv
-            + Neg<Output = T>
-            + PartialOrd
-            + RealField
-            + Zero,
-    > Surface<T> for Polygon<T>
+impl<T, M> Surface<T, M> for Polygon<T>
+where
+    T: RealField + ApproxEq<Margin = M>,
+    M: Copy,
 {
-    fn contains_point(&self, p: &Vec2<T>) -> bool {
+    fn contains_point(&self, p: &Vec2<T>, margin: M) -> bool {
         let n = self.corners.len();
 
         let a = self.corners[n - 1];
@@ -247,7 +247,7 @@ impl<
             }
 
             let lx = ax + (((bx - ax) * -ay) / (by - ay));
-            if lx == T::zero() {
+            if lx.approx_eq(T::zero(), margin) {
                 // point on edge
                 return true;
             }
@@ -269,11 +269,13 @@ impl<
         (depth & 1) == 1
     }
 
-    fn contains_line_segment(&self, line_segment: &LineSegment<T>) -> bool {
+    fn contains_line_segment(&self, line_segment: &LineSegment<T>, margin: M) -> 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) {
+        if !self.contains_point(&line_segment.start, margin)
+            || !self.contains_point(&line_segment.end, margin)
+        {
             return false;
         }
 
@@ -294,9 +296,13 @@ impl<
             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);
+            let edge_angle = math::triplet_angle(
+                self.corners[prev],
+                self.corners[c],
+                self.corners[next],
+                margin,
+            );
+            let vec_angle = math::triplet_angle(self.corners[prev], self.corners[c], p, margin);
 
             vec_angle == T::zero() || vec_angle >= edge_angle
         };
@@ -328,16 +334,18 @@ impl<
 
             let current_edge = LineSegment::new(self.corners[c], self.corners[next]);
 
-            if LineSegment::intersect(&line_segment, &current_edge) {
+            if LineSegment::intersect(&line_segment, &current_edge, margin) {
                 let orientation_start = math::triplet_orientation(
                     current_edge.start,
                     current_edge.end,
                     line_segment.start,
+                    margin,
                 );
                 let orientation_end = math::triplet_orientation(
                     current_edge.start,
                     current_edge.end,
                     line_segment.end,
+                    margin,
                 );
                 match (orientation_start, orientation_end) {
                     /* If at least one of the points is on the edge, make sure, the line points
@@ -364,7 +372,7 @@ impl<
         true
     }
 
-    fn contains_rect(&self, rect: &Rect<T>) -> bool {
+    fn contains_rect(&self, rect: &Rect<T>, margin: M) -> bool {
         /* Turn the rectangle into a vector with its hull line segments. If all hull segments are
          * contained in the polygon, the rectangle is contained completely.
          */
@@ -393,18 +401,19 @@ impl<
 
         hull_edges
             .iter()
-            .all(|edge| self.contains_line_segment(edge))
+            .all(|edge| self.contains_line_segment(edge, margin))
     }
 
-    fn contains_polygon(&self, polygon: &Polygon<T>) -> bool {
+    fn contains_polygon(&self, polygon: &Polygon<T>, margin: M) -> bool {
         /* Check for all edges of the polygon that they are contained by the polygon. If they all
          * are, then the polygon itself must also be contained.
          */
         for i in 0..polygon.corners.len() {
             let next = (i + 1) % polygon.corners.len();
-            if !self
-                .contains_line_segment(&LineSegment::new(polygon.corners[i], polygon.corners[next]))
-            {
+            if !self.contains_line_segment(
+                &LineSegment::new(polygon.corners[i], polygon.corners[next]),
+                margin,
+            ) {
                 return false;
             }
         }
@@ -421,13 +430,17 @@ impl<
  * after another until finally connecting the last point to the first point in radians. Negative,
  * when the points in sum are right-turning, positive, when they are left-turning.
  */
-fn combined_angle<T: Scalar + Copy + RealField>(points: &[Vec2<T>]) -> T {
+fn combined_angle<T: Scalar + Copy + RealField, M>(points: &[Vec2<T>], margin: M) -> T
+where
+    T: ApproxEq<Margin = M>,
+    M: Copy,
+{
     let mut combined_angle = T::zero();
     for i in 0..points.len() {
         let prev = (i + points.len() - 1) % points.len();
         let next = (i + 1) % points.len();
 
-        let angle = math::triplet_angle(points[prev], points[i], points[next]);
+        let angle = math::triplet_angle(points[prev], points[i], points[next], margin);
         if angle == T::zero() || angle == T::two_pi() {
             continue;
         }
@@ -445,21 +458,27 @@ mod test {
 
     #[test]
     fn check_validity() {
-        Polygon::check_validity(&[Vec2::new(0., 0.), Vec2::new(1., 0.), Vec2::new(0., 1.)])
-            .expect("Simple triangle does not pass validity check");
+        Polygon::check_validity(
+            &[Vec2::new(0., 0.), Vec2::new(1., 0.), Vec2::new(0., 1.)],
+            (f64::EPSILON, 0),
+        )
+        .expect("Simple triangle does not pass validity check");
     }
 
     #[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.),
-        ])
+        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.),
+            ],
+            (f64::EPSILON, 0),
+        )
         .unwrap();
 
         assert!(!polygon.contains_point(&Vec2::new(1., -2.)));
@@ -474,18 +493,21 @@ mod test {
 
     #[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.),
-        ])
+        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();
 
         /* NOTE: From now on, inside means inside the polygon, but might be on an edge or on a
@@ -531,22 +553,28 @@ mod test {
 
     #[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 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.),
+            ],
+            (f64::EPSILON, 0),
+        )
         .unwrap();
 
-        let second = Polygon::new(vec![
-            Vec2::new(0., 0.),
-            Vec2::new(-2., 2.),
-            Vec2::new(3., 2.),
-            Vec2::new(1.5, 0.),
-        ])
+        let second = Polygon::new(
+            vec![
+                Vec2::new(0., 0.),
+                Vec2::new(-2., 2.),
+                Vec2::new(3., 2.),
+                Vec2::new(1.5, 0.),
+            ],
+            (f64::EPSILON, 0),
+        )
         .unwrap();
 
         let union = first.unite(second);