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.

20 files changed, 441 insertions, 333 deletions

diff --git a/Cargo.lock b/Cargo.lock
index b715f73..d36d039 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -106,6 +106,9 @@ name = "float-cmp"
 version = "0.5.3"
 source = "registry+https://github.com/rust-lang/crates.io-index"
 checksum = "75224bec9bfe1a65e2d34132933f2de7fe79900c96a0174307554244ece8150e"
+dependencies = [
+ "num-traits",
+]
 
 [[package]]
 name = "fs_extra"
@@ -139,6 +142,7 @@ name = "graf_karto"
 version = "0.1.1"
 dependencies = [
  "alga",
+ "float-cmp",
  "log",
  "nalgebra",
  "num-traits",
diff --git a/Cargo.toml b/Cargo.toml
index 23c17be..0a8e040 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -15,4 +15,5 @@ svgtypes = "*"
 xmltree = "*"
 pretty_env_logger = "*"
 log = "*"
-thiserror = "*"
\ No newline at end of file
+thiserror = "*"
+float-cmp = "*"
\ No newline at end of file
diff --git a/src/gui/dimension_indicator.rs b/src/gui/dimension_indicator.rs
index e8848fe..57f5bcc 100644
--- a/src/gui/dimension_indicator.rs
+++ b/src/gui/dimension_indicator.rs
@@ -41,22 +41,28 @@ impl Default for State {
     }
 }
 
+impl Default for DimensionIndicator {
+    fn default() -> Self {
+        Self {
+            state: State::default(),
+            bounds: Rect::new(0., 0., 0., 0.),
+        }
+    }
+}
+
 impl DimensionIndicator {
     /// Create a new dimension indicator. While it is possible to have multiple instances, this is
     /// not generally recommended, since they will need to be managed carefully or otherwise steal
     /// keystrokes from each other.
     pub fn new() -> Self {
-        Self {
-            state: State::default(),
-            bounds: Rect::new(0., 0., 0., 0.),
-        }
+        Self::default()
     }
 
     /// Update whatever is selected on the map according to the dimension indicator rules and rulers.
     pub fn update(&mut self, map: &mut Map, rl: &mut RaylibHandle) {
-        match &self.state {
-            &State::Watching => self.update_watching(map, rl),
-            &State::Ruling { .. } => self.update_ruling(map, rl),
+        match self.state {
+            State::Watching => self.update_watching(map, rl),
+            State::Ruling { .. } => self.update_ruling(map, rl),
         };
     }
 
diff --git a/src/gui/tool_sidebar.rs b/src/gui/tool_sidebar.rs
index e6b8867..b7618e0 100644
--- a/src/gui/tool_sidebar.rs
+++ b/src/gui/tool_sidebar.rs
@@ -3,7 +3,7 @@
 // TODO: Currently, the keyboard shortcuts for tools are handled by the editor, but a lot speaks for
 // them being handled by the ToolSidebar instead.
 
-use crate::math::{Rect, Surface, Vec2};
+use crate::math::{ExactSurface, Rect, Vec2};
 use crate::tool::ToolType;
 use crate::Editor;
 use raylib::core::texture::Texture2D;
diff --git a/src/main.rs b/src/main.rs
index 8c1d63e..16afe1f 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -36,6 +36,7 @@ pub mod transformable;
 
 use config::Config;
 use editor::Editor;
+use float_cmp::F64Margin;
 use gui::{DimensionIndicator, ToolSidebar};
 use raylib::prelude::*;
 use std::ffi::CString;
@@ -47,6 +48,14 @@ pub const GUI_STYLE: &str = "assets/style/cyber.rgs";
 /// Location of the graf karto configuration options file.
 pub const CONFIG_FILE: &str = "config.ron";
 
+/// The acceptable error that is used throughout the project for two floats to be considered equal.
+/// If it is set too low, the editor might not work properly, if set too high, the granularity may
+/// become too low for certain purposes.
+pub const FLOAT_MARGIN: F64Margin = F64Margin {
+    epsilon: 10000. * f64::EPSILON,
+    ulps: 0,
+};
+
 fn main() {
     pretty_env_logger::init();
 
diff --git a/src/map/polygon_room.rs b/src/map/polygon_room.rs
index fd4122e..ead4e76 100644
--- a/src/map/polygon_room.rs
+++ b/src/map/polygon_room.rs
@@ -6,6 +6,7 @@ use crate::colours::DEFAULT_COLOURS;
 use crate::math::{self, Polygon, Rect, Triangle};
 use crate::transform::Transform;
 use crate::transformable::NonRigidTransformable;
+use crate::FLOAT_MARGIN;
 use nalgebra::{Matrix3, Point2};
 use raylib::drawing::{RaylibDraw, RaylibDrawHandle};
 
@@ -25,7 +26,7 @@ impl PolygonRoom {
     pub fn from_data(data: PolygonRoomData) -> Self {
         Self {
             data: data.clone(),
-            triangulated: math::triangulate(data),
+            triangulated: math::triangulate(data, FLOAT_MARGIN),
             selected: false,
         }
     }
@@ -33,7 +34,7 @@ impl PolygonRoom {
     // When the internal polygon changes, it must be retriangulated to be drawn on the screen
     // properly, so this function must be called any time that happens.
     fn retriangulate(&mut self) {
-        self.triangulated = math::triangulate(self.data.clone());
+        self.triangulated = math::triangulate(self.data.clone(), FLOAT_MARGIN);
     }
 }
 
diff --git a/src/map/rect_room.rs b/src/map/rect_room.rs
index 6ed3ed6..ae10327 100644
--- a/src/map/rect_room.rs
+++ b/src/map/rect_room.rs
@@ -49,7 +49,7 @@ impl Mappable for RectRoom {
     }
 
     fn bounding_rect(&self) -> Rect<f64> {
-        self.data.clone()
+        self.data
     }
 }
 
diff --git a/src/math/line_segment.rs b/src/math/line_segment.rs
index 204cf0c..738f56a 100644
--- a/src/math/line_segment.rs
+++ b/src/math/line_segment.rs
@@ -1,8 +1,9 @@
 //! A line segment is like a line, but with a start and an end, with the line only being between
 //! those two.
 
-use super::{Rect, Surface, TripletOrientation, Vec2};
+use super::{ExactSurface, Rect, TripletOrientation, Vec2};
 use alga::general::{ClosedDiv, ClosedMul, ClosedSub};
+use float_cmp::ApproxEq;
 use nalgebra::{RealField, Scalar};
 use num_traits::Zero;
 use serde::{Deserialize, Serialize};
@@ -37,9 +38,9 @@ impl<T: Scalar + Copy> LineSegment<T> {
 
     /// Checks if two segments intersect. This is much more efficient than trying to find the exact
     /// point of intersection, so it should be used if it is not strictly necessary to know it.
-    pub fn intersect(ls1: &LineSegment<T>, ls2: &LineSegment<T>) -> bool
+    pub fn intersect<M: Copy>(ls1: &LineSegment<T>, ls2: &LineSegment<T>, margin: M) -> bool
     where
-        T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
+        T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
     {
         /* This algorithm works by checking the triplet orientation of the first lines points with the
          * first point of the second line. After that it does the same for the second point of the
@@ -56,10 +57,14 @@ impl<T: Scalar + Copy> LineSegment<T> {
          */
 
         // Cache the necessary orientations.
-        let ls1_ls2start_orientation = super::triplet_orientation(ls1.start, ls1.end, ls2.start);
-        let ls1_ls2end_orientation = super::triplet_orientation(ls1.start, ls1.end, ls2.end);
-        let ls2_ls1start_orientation = super::triplet_orientation(ls2.start, ls2.end, ls1.start);
-        let ls2_ls1end_orientation = super::triplet_orientation(ls2.start, ls2.end, ls1.end);
+        let ls1_ls2start_orientation =
+            super::triplet_orientation(ls1.start, ls1.end, ls2.start, margin);
+        let ls1_ls2end_orientation =
+            super::triplet_orientation(ls1.start, ls1.end, ls2.end, margin);
+        let ls2_ls1start_orientation =
+            super::triplet_orientation(ls2.start, ls2.end, ls1.start, margin);
+        let ls2_ls1end_orientation =
+            super::triplet_orientation(ls2.start, ls2.end, ls1.end, margin);
 
         // Check for the first case that wase described (general case).
         if ls1_ls2start_orientation != ls1_ls2end_orientation
@@ -100,9 +105,14 @@ impl<T: Scalar + Copy> LineSegment<T> {
     /// Try to find the the point where the two line segments intersect. If they do not intersect,
     /// `None` is returned. If the lines are parallel and intersect (at least part of a line is on
     /// a part of the other line), inside that region is returned.
-    pub fn intersection(line_a: &LineSegment<T>, line_b: &LineSegment<T>) -> Option<Vec2<T>>
+    pub fn intersection<M>(
+        line_a: &LineSegment<T>,
+        line_b: &LineSegment<T>,
+        margin: M,
+    ) -> Option<Vec2<T>>
     where
-        T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField,
+        T: ClosedSub + ClosedMul + ClosedDiv + Zero + RealField + ApproxEq<Margin = M>,
+        M: Copy,
     {
         // Calculate the differences of each line value from starting point to end point
         // coordinate.
@@ -115,8 +125,10 @@ impl<T: Scalar + Copy> LineSegment<T> {
         let d = (dax * dby) - (day * dbx);
         if d == T::zero() {
             // The two line segments are parallel, check if one may be on the other.
-            if super::triplet_orientation(line_a.start, line_a.end, line_b.start) == TripletOrientation::Collinear
-                && super::triplet_orientation(line_a.start, line_a.end, line_b.end) == TripletOrientation::Collinear
+            if super::triplet_orientation(line_a.start, line_a.end, line_b.start, margin)
+                == TripletOrientation::Collinear
+                && super::triplet_orientation(line_a.start, line_a.end, line_b.end, margin)
+                    == TripletOrientation::Collinear
             {
                 if line_a.contains_collinear(line_b.start) {
                     Some(line_b.start)
@@ -156,16 +168,16 @@ impl<T: Scalar + Copy> LineSegment<T> {
     /// Find all segments, into which this LineSegment would be splitted, when the points provided
     /// would cut the segment. The points must be on the line, otherwise this does not make sense.
     /// Also, no segments of length zero (start point = end point) will be created.
-    pub fn segments(&self, split_points: &[Vec2<T>]) -> Vec<Vec2<T>>
+    pub fn segments<M>(&self, split_points: &[Vec2<T>], margin: M) -> Vec<Vec2<T>>
     where
-        T: ClosedSub + ClosedMul + PartialOrd + Zero,
+        T: ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
+        M: Copy,
     {
         // Make sure all segments are collinear with the segment and actually on it
         assert_eq!(
-            split_points
-                .iter()
-                .find(|&p| super::triplet_orientation(self.start, self.end, *p)
-                    != TripletOrientation::Collinear),
+            split_points.iter().find(|&p| super::triplet_orientation(
+                self.start, self.end, *p, margin
+            ) != TripletOrientation::Collinear),
             None
         );
         assert_eq!(
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);
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()
     }
 }
 
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);
diff --git a/src/math/rect.rs b/src/math/rect.rs
index 6f993d1..b019ad5 100644
--- a/src/math/rect.rs
+++ b/src/math/rect.rs
@@ -1,9 +1,8 @@
 //! Rectangles where the sides are parallel to the x and y-axes.
 
-use super::{LineSegment, Polygon, Surface, Vec2};
+use super::{ExactSurface, LineSegment, Polygon, Vec2};
 //use alga::general::{Additive, Identity};
-use nalgebra::{ClosedAdd, ClosedSub, RealField, Scalar};
-use num_traits::identities::Zero;
+use nalgebra::{RealField, Scalar};
 use num_traits::{NumCast, ToPrimitive};
 use serde::{Deserialize, Serialize};
 use std::ops::{Add, AddAssign};
@@ -150,7 +149,7 @@ impl<T: Scalar + Copy> Rect<T> {
     }
 }
 
-impl<T: Scalar + Copy + PartialOrd + ClosedAdd + ClosedSub + Zero> Surface<T> for Rect<T> {
+impl<T: RealField> ExactSurface<T> for Rect<T> {
     fn contains_point(&self, point: &Vec2<T>) -> bool {
         point.x >= self.x
             && point.x <= self.x + self.w
diff --git a/src/math/surface.rs b/src/math/surface.rs
index ab1c703..088ac47 100644
--- a/src/math/surface.rs
+++ b/src/math/surface.rs
@@ -1,10 +1,34 @@
 //! Surfaces, which are areas at a certain position in a vector space.
 
 use super::{LineSegment, Polygon, Rect, Vec2};
-use nalgebra::Scalar;
+use float_cmp::ApproxEq;
+use nalgebra::RealField;
 
-/// Trait that describes an area in the vector space on the field of T
-pub trait Surface<T: Scalar + Copy> {
+/// Trait that describes an area in the vector space on the field of T, with T unable to be
+/// used without rounding.
+pub trait Surface<T: RealField, M>
+where
+    T: ApproxEq<Margin = M>,
+{
+    /// Checks if a point lies on this surface.
+    fn contains_point(&self, point: &Vec2<T>, margin: M) -> bool;
+
+    /// Checks if a line segment is entirely contained by this surface.
+    fn contains_line_segment(&self, line_segment: &LineSegment<T>, margin: M) -> bool;
+
+    /// Checks if a rectangle is entirely contained inside this surface.
+    fn contains_rect(&self, rect: &Rect<T>, margin: M) -> bool;
+
+    /// Checks if a polygon is contained wholly by this surface.
+    fn contains_polygon(&self, polygon: &Polygon<T>, margin: M) -> bool;
+
+    /// Checks if this surface is contained by the rect in it's entirety. Think of it as the reverse
+    /// operation for contains_... on a rectangle.
+    fn is_inside_rect(&self, rect: &Rect<T>) -> bool;
+}
+
+/// The same as Surface, but the vector space will be assumed to be perfectly divideable or checkable.
+pub trait ExactSurface<T: RealField> {
     /// Checks if a point lies on this surface.
     fn contains_point(&self, point: &Vec2<T>) -> bool;
 
@@ -21,3 +45,28 @@ pub trait Surface<T: Scalar + Copy> {
     /// operation for contains_... on a rectangle.
     fn is_inside_rect(&self, rect: &Rect<T>) -> bool;
 }
+
+/*
+// Every exact surface must also be an approximate surface, with margin 0 to be exact.
+impl<T, S> Surface<T> for S where S: ExactSurface<T> {
+    fn contains_point<M>(&self, point: &Vec2<T>, _margin: M) -> bool {
+        ExactSurface::contains_point(&self, point)
+    }
+
+    fn contains_line_segment<M>(&self, line_segment: &LineSegment<T>, margin: M) -> bool {
+        ExactSurface::contains_line_segment(&self, line_segment)
+    }
+
+    fn contains_rect<M>(&self, rect: &Rect<T>, margin: M) -> bool {
+        ExactSurface::contains_rect(&self, rect)
+    }
+
+    fn contains_polygon<M>(&self, polygon: &Polygon<T>, margin: M) -> bool {
+        ExactSurface::contains_polygon(&self, polygon)
+    }
+
+    fn is_inside_rect(&self, rect: &Rect<T>) -> bool {
+        ExactSurface::is_inside_rect(&self, rect)
+    }
+}
+*/
diff --git a/src/math/triangle.rs b/src/math/triangle.rs
index b5c1bda..2b0b9ac 100644
--- a/src/math/triangle.rs
+++ b/src/math/triangle.rs
@@ -2,6 +2,7 @@
 
 use super::{LineSegment, Vec2};
 use alga::general::{ClosedMul, ClosedSub};
+use float_cmp::ApproxEq;
 use nalgebra::{RealField, Scalar};
 use num_traits::Zero;
 
@@ -15,12 +16,13 @@ pub struct Triangle<T: Scalar + Copy> {
 
 impl<T: Scalar + Copy> Triangle<T> {
     /// Create a new Triangle as defined by its three corner points
-    pub fn new(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> Self
+    pub fn new<M>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>, margin: M) -> Self
     where
-        T: ClosedSub + ClosedMul + PartialOrd + Zero,
+        T: ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
+        M: Copy,
     {
         // Make sure the three points are in counterclockwise order.
-        match triplet_orientation(a, b, c) {
+        match triplet_orientation(a, b, c, margin) {
             TripletOrientation::Counterclockwise => Self { corners: [a, b, c] },
             TripletOrientation::Clockwise => Self { corners: [a, c, b] },
             TripletOrientation::Collinear => {
@@ -40,24 +42,26 @@ impl<T: Scalar + Copy> Triangle<T> {
 
     /// Create a new Triangle from a three-point slice, instead of the three points one after
     /// another.
-    pub fn from_slice(corners: [Vec2<T>; 3]) -> Self
+    pub fn from_slice<M>(corners: [Vec2<T>; 3], margin: M) -> Self
     where
-        T: ClosedSub + ClosedMul + PartialOrd + Zero,
+        T: ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
+        M: Copy,
     {
-        Self::new(corners[0], corners[1], corners[2])
+        Self::new(corners[0], corners[1], corners[2], margin)
     }
 
     /// Check if the triangle contains a given point. If the point is right on an edge, it still
     /// counts as inside it.
-    pub fn contains_point(&self, point: Vec2<T>) -> bool
+    pub fn contains_point<M>(&self, point: Vec2<T>, margin: M) -> bool
     where
-        T: ClosedSub + ClosedMul + PartialOrd + Zero,
+        T: ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
+        M: Copy,
     {
         // Since the points are ordered counterclockwise, check if the point is to the left of all
         // edges (or on an edge) from one point to the next. When the point is to the left of all
         // edges, it must be inside the triangle.
         for i in 0..3 {
-            if triplet_orientation(self.corners[i], self.corners[(i + 1) % 3], point)
+            if triplet_orientation(self.corners[i], self.corners[(i + 1) % 3], point, margin)
                 == TripletOrientation::Clockwise
             {
                 return false;
@@ -69,11 +73,13 @@ impl<T: Scalar + Copy> Triangle<T> {
 }
 
 /// Convert a three-point-slice into a triangle
-impl<T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero> From<[Vec2<T>; 3]>
-    for Triangle<T>
+impl<T, M> From<([Vec2<T>; 3], M)> for Triangle<T>
+where
+    T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
+    M: Copy,
 {
-    fn from(corners: [Vec2<T>; 3]) -> Self {
-        Self::new(corners[0], corners[1], corners[2])
+    fn from((corners, margin): ([Vec2<T>; 3], M)) -> Self {
+        Self::new(corners[0], corners[1], corners[2], margin)
     }
 }
 /// Convert a triangle into a three-point-slice. The corners are in counterclockwise order.
@@ -112,18 +118,26 @@ pub(crate) enum TripletOrientation {
 /// Helper function to determine which direction one would turn to traverse from the first point
 /// over the second to the third point. The third option is collinear, in which case the three points
 /// are on the same line.
-pub(crate) fn triplet_orientation<T>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> TripletOrientation
+pub(crate) fn triplet_orientation<T, M>(
+    a: Vec2<T>,
+    b: Vec2<T>,
+    c: Vec2<T>,
+    margin: M,
+) -> TripletOrientation
 where
-    T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero,
+    T: Scalar + Copy + ClosedSub + ClosedMul + PartialOrd + Zero + ApproxEq<Margin = M>,
 {
     /* Check the slopes of the vector from a to b and b to c. If the slope of ab is greater than
      * that of bc, the rotation is clockwise. If ab is smaller than bc it's counterclockwise. If
      * they are the same it follows that the three points are collinear.
      */
-    match (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y) {
-        q if q > T::zero() => TripletOrientation::Counterclockwise,
-        q if q < T::zero() => TripletOrientation::Clockwise,
-        _ => TripletOrientation::Collinear,
+    let slope_diff = (b.y - a.y) * (c.x - b.x) - (b.x - a.x) * (c.y - b.y);
+    if slope_diff.approx_eq(T::zero(), margin) {
+        TripletOrientation::Collinear
+    } else if slope_diff > T::zero() {
+        TripletOrientation::Counterclockwise
+    } else {
+        TripletOrientation::Clockwise
     }
 }
 
@@ -133,15 +147,15 @@ where
 ///
 /// # Panics
 /// If the length from a to b or the length from b to c is zero.
-pub(crate) fn triplet_angle<T>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>) -> T
+pub(crate) fn triplet_angle<T, M>(a: Vec2<T>, b: Vec2<T>, c: Vec2<T>, margin: M) -> T
 where
-    T: Scalar + Copy + ClosedSub + RealField + Zero,
+    T: Scalar + Copy + ClosedSub + RealField + Zero + ApproxEq<Margin = M>,
 {
     assert!(a != b);
     assert!(b != c);
 
     // Handle the extreme 0 and 180 degree cases
-    let orientation = triplet_orientation(a, b, c);
+    let orientation = triplet_orientation(a, b, c, margin);
     if orientation == TripletOrientation::Collinear {
         if LineSegment::new(a, b).contains_collinear(c)
             || LineSegment::new(b, c).contains_collinear(a)
diff --git a/src/tool/deletion_tool.rs b/src/tool/deletion_tool.rs
index afd916a..da2090b 100644
--- a/src/tool/deletion_tool.rs
+++ b/src/tool/deletion_tool.rs
@@ -9,7 +9,7 @@
 use super::Tool;
 use crate::colours::DEFAULT_COLOURS;
 use crate::map::Map;
-use crate::math::{Rect, Surface, Vec2};
+use crate::math::{ExactSurface, Rect, Vec2};
 use crate::transform::Transform;
 use raylib::core::drawing::{RaylibDraw, RaylibDrawHandle};
 
@@ -21,6 +21,7 @@ pub struct DeletionTool {
 impl DeletionTool {
     /// Create a new deletion tool, there should only be one deletion tool and it should be created
     /// by the editor.
+    #[allow(clippy::new_without_default)]
     pub fn new() -> Self {
         Self {
             deletion_rect: None,
diff --git a/src/tool/mod.rs b/src/tool/mod.rs
index 70534ac..4130244 100644
--- a/src/tool/mod.rs
+++ b/src/tool/mod.rs
@@ -31,17 +31,17 @@ use raylib::core::drawing::RaylibDrawHandle;
 /// The types of tools available in graf karto. For information about the tool itself, please see the
 /// referenced Tool's documentation.
 pub enum ToolType {
-    /// See [super::RectRoomTool] for information on this tool.
+    /// See [RectRoomTool] for information on this tool.
     RectRoomTool,
-    /// See [super::PolygonRoomTool] for information on this tool.
+    /// See [PolygonRoomTool] for information on this tool.
     PolygonRoomTool,
-    /// See [super::WallTool] for information on this tool.
+    /// See [WallTool] for information on this tool.
     WallTool,
-    /// See [super::IconTool] for information on this tool.
+    /// See [IconTool] for information on this tool.
     IconTool,
-    /// See [super::DeletionTool] for information on this tool.
+    /// See [DeletionTool] for information on this tool.
     DeletionTool,
-    /// See [super::SelectionTool] for information on this tool.
+    /// See [SelectionTool] for information on this tool.
     SelectionTool,
     /// Not a real tool but used to know how many tools are available. New tools must be added
     /// above this variant.
diff --git a/src/tool/polygon_room_tool.rs b/src/tool/polygon_room_tool.rs
index 33daaf5..d181669 100644
--- a/src/tool/polygon_room_tool.rs
+++ b/src/tool/polygon_room_tool.rs
@@ -3,189 +3,132 @@
 use super::Tool;
 use crate::colours::DEFAULT_COLOURS;
 use crate::map::Map;
-use crate::math::{self, Polygon, PolygonError, Vec2};
+use crate::math::{self, PolygonGraph, Vec2};
 use crate::transform::Transform;
+use crate::FLOAT_MARGIN;
 use raylib::core::drawing::{RaylibDraw, RaylibDrawHandle};
 
-struct UnfinishedPolygon {
-    pub corners: Vec<Vec2<f64>>,
-    pub working_corner: Vec2<f64>,
-}
-
 /// The tool itself.
 pub struct PolygonRoomTool {
-    unfinished_polygon: Option<UnfinishedPolygon>,
-}
-
-impl UnfinishedPolygon {
-    // Check the validity of the already completed corners only
-    pub fn check_validity_completed(&self) -> Result<(), PolygonError<f64>> {
-        Polygon::check_validity(&self.corners)
-    }
-
-    // Check the validity of the already completed corners, but with the working corner wedged
-    // between the last and first corner (making it the new last corner).
-    pub fn check_validity_all(&self) -> Result<(), PolygonError<f64>> {
-        // TODO: Is this possible without changing the mutability of self and without reallocation?
-        let mut corners = self.corners.clone();
-        corners.push(self.working_corner);
-
-        Polygon::check_validity(&corners)
-    }
-
-    pub fn try_into_completed(&mut self) -> Option<Polygon<f64>> {
-        match self.check_validity_completed() {
-            Ok(()) => Some(Polygon::new_unchecked(self.corners.drain(..).collect())),
-            Err(e) => {
-                warn!("Cannot turn placed corners into a polygon: {}", e);
-                None
-            }
-        }
-    }
-
-    pub fn try_into_all(&mut self) -> Option<Polygon<f64>> {
-        match self.check_validity_all() {
-            Ok(()) => {
-                self.corners.push(self.working_corner);
-                Some(Polygon::new_unchecked(self.corners.drain(..).collect()))
-            }
-            Err(e) => {
-                warn!(
-                    "Cannot turn corners with newest corner into a polygon: {}",
-                    e
-                );
-                None
-            }
-        }
-    }
-
-    pub fn try_push_working(&mut self) -> Result<(), PolygonError<f64>> {
-        assert!(!self.corners.is_empty());
-
-        if self.corners.len() == 1 {
-            return if self.corners[0] != self.working_corner {
-                self.corners.push(self.working_corner);
-                Ok(())
-            } else {
-                Err(PolygonError::VertexDoubling(self.corners[0], 0))
-            };
-        }
-
-        self.check_validity_all()?;
-        self.corners.push(self.working_corner);
-
-        Ok(())
-    }
+    unfinished_room: Option<(PolygonGraph<f64>, Vec2<f64>)>,
+    last_mouse_pos_m: Vec2<f64>,
 }
 
 impl PolygonRoomTool {
     /// Create a new polygon room tool. There should be only one instance and it should be created
     /// in the editor.
+    #[allow(clippy::new_without_default)]
     pub fn new() -> Self {
         Self {
-            unfinished_polygon: None,
+            unfinished_room: None,
+            last_mouse_pos_m: Vec2::new(0., 0.),
+        }
+    }
+
+    /* Helper function to try and finish the currently drawn polygon. If successful, it will add it
+     * to the map, clear the currently drawn polygon and return bool. Otherwise it will leave the
+     * unfinished polygon as is and return false without pushing anything.
+     */
+    fn try_push(&mut self, map: &mut Map) -> bool {
+        if self.unfinished_room.is_none() {
+            return false;
+        }
+
+        match self
+            .unfinished_room
+            .as_ref()
+            .unwrap()
+            .0
+            .clone()
+            .bounding_polygon(FLOAT_MARGIN)
+        {
+            Some(polygon) => {
+                map.push_polygon_room(polygon);
+                self.unfinished_room = None;
+                true
+            }
+            None => false,
         }
     }
 }
 
 impl Tool for PolygonRoomTool {
     fn deactivate(&mut self) {
-        self.unfinished_polygon = None;
+        self.unfinished_room = None;
     }
 
     fn update(&mut self, _map: &Map, mouse_pos_m: &Vec2<f64>) {
-        // Update the position of the node that would be placed into the polygon next.
-        if let Some(ref mut polygon) = &mut self.unfinished_polygon {
-            polygon.working_corner = *mouse_pos_m;
-        }
+        // Update the last mouse position that was seen for later use.
+        self.last_mouse_pos_m = *mouse_pos_m;
     }
 
     fn draw(&self, rld: &mut RaylibDrawHandle, transform: &Transform) {
-        if let Some(polygon) = &self.unfinished_polygon {
-            // The first corner is guaranteed to be set, so we can at least draw a line.
-            if polygon.corners.len() == 1 {
-                rld.draw_line_ex(
-                    transform.point_m_to_px(&polygon.corners[0]),
-                    transform.point_m_to_px(&polygon.working_corner),
+        if let Some((graph, last_node)) = &self.unfinished_room {
+            /* To turn the graph into a polygon, we need a copy, might as well do
+             * it now, so we can add the working corner to it.
+             */
+            let mut graph = graph.clone();
+
+            // Add the current mouse position as the next position if possible.
+            graph.add_edge(&last_node, &self.last_mouse_pos_m);
+
+            if graph.num_nodes() <= 1 {
+                // Only able to draw a point
+                rld.draw_circle_v(
+                    transform.point_m_to_px(&self.last_mouse_pos_m),
                     transform.length_m_to_px(0.1) as f32,
                     DEFAULT_COLOURS.room_selected,
                 );
-            } else if polygon.corners.len() == 2 {
-                // We have three valid corners, so we can draw a triangle.
-                rld.draw_triangle(
-                    transform.point_m_to_px(&polygon.corners[0]),
-                    transform.point_m_to_px(&polygon.corners[1]),
-                    transform.point_m_to_px(&polygon.working_corner),
-                    DEFAULT_COLOURS.room_selected,
-                )
+            } else if let Some(polygon) = graph.clone().bounding_polygon(FLOAT_MARGIN) {
+                let triangles = math::triangulate(polygon, FLOAT_MARGIN);
+                for triangle in triangles {
+                    let triangle: [Vec2<f64>; 3] = triangle.into();
+                    rld.draw_triangle(
+                        transform.point_m_to_px(&triangle[0]),
+                        transform.point_m_to_px(&triangle[1]),
+                        transform.point_m_to_px(&triangle[2]),
+                        DEFAULT_COLOURS.room_selected,
+                    )
+                }
             } else {
-                // A proper polygon can be drawn.
-                if polygon.check_validity_all().is_ok() {
-                    let mut corners = polygon.corners.clone();
-                    corners.push(polygon.working_corner);
-                    let polygon = Polygon::new_unchecked(corners);
-                    let triangles = math::triangulate(polygon);
-                    for triangle in triangles {
-                        let triangle: [Vec2<f64>; 3] = triangle.into();
-                        rld.draw_triangle(
-                            transform.point_m_to_px(&triangle[0]),
-                            transform.point_m_to_px(&triangle[1]),
-                            transform.point_m_to_px(&triangle[2]),
-                            DEFAULT_COLOURS.room_selected,
-                        )
-                    }
-                } else if polygon.check_validity_completed().is_ok() {
-                    let polygon = Polygon::new_unchecked(polygon.corners.clone());
-                    let triangles = math::triangulate(polygon);
-                    for triangle in triangles {
-                        let triangle: [Vec2<f64>; 3] = triangle.into();
-                        rld.draw_triangle(
-                            transform.point_m_to_px(&triangle[0]),
-                            transform.point_m_to_px(&triangle[1]),
-                            transform.point_m_to_px(&triangle[2]),
-                            DEFAULT_COLOURS.room_selected,
-                        )
-                    }
+                // For some reason the polygon creation failed. Draw lines for the edges instead.
+                for edge in graph.edge_iter() {
+                    rld.draw_line_ex(
+                        transform.point_m_to_px(&edge.start),
+                        transform.point_m_to_px(&edge.end),
+                        transform.length_m_to_px(0.1) as f32,
+                        DEFAULT_COLOURS.room_selected,
+                    );
                 }
             }
         }
     }
 
     fn place_single(&mut self, map: &mut Map, mouse_pos_m: &Vec2<f64>) {
-        if let Some(ref mut polygon) = &mut self.unfinished_polygon {
-            if polygon.working_corner == polygon.corners[0] {
-                /* The working corner will be ignored, since it would double the vertex at the
-                 * polygon starting position.
-                 */
-                if let Some(polygon) = polygon.try_into_completed() {
-                    map.push_polygon_room(polygon);
-                    self.unfinished_polygon = None;
-                }
-            } else {
-                // Check if we can add the corner to the polygon without ruining it.
-                if let Err(e) = polygon.try_push_working() {
-                    error!("Cannot add corner to polygon: {}", e);
-                }
+        if let Some((ref mut graph, ref mut last_placed)) = &mut self.unfinished_room {
+            // If the corner already exists in the polygon, try to finish and push it after adding the
+            // next edge.
+            let try_finish = graph.has_node(&mouse_pos_m);
+
+            // Add an edge from the last corner to the currently active position if possible.
+            if graph.add_edge(last_placed, &mouse_pos_m) {
+                *last_placed = *mouse_pos_m;
+            }
+
+            if try_finish {
+                self.try_push(map);
             }
         } else {
             // Start a new unfinished polygon
-            self.unfinished_polygon = Some(UnfinishedPolygon {
-                corners: vec![*mouse_pos_m],
-                working_corner: *mouse_pos_m,
-            });
+            self.unfinished_room = Some((PolygonGraph::new(), *mouse_pos_m));
         }
     }
 
     fn finish(&mut self, map: &mut Map) {
-        if let Some(ref mut polygon) = self.unfinished_polygon {
-            if let Some(polygon) = polygon.try_into_completed() {
-                map.push_polygon_room(polygon);
-                self.unfinished_polygon = None;
-            }
-        }
+        self.try_push(map);
     }
 
     fn abort(&mut self) {
-        self.unfinished_polygon = None;
+        self.unfinished_room = None;
     }
 }
diff --git a/src/tool/rect_room_tool.rs b/src/tool/rect_room_tool.rs
index 7cb85bb..9445787 100644
--- a/src/tool/rect_room_tool.rs
+++ b/src/tool/rect_room_tool.rs
@@ -19,6 +19,7 @@ pub struct RectRoomTool {
 impl RectRoomTool {
     /// Create a new room tool where no rooms have been drawn yet. Should be created only once per
     /// program instance and by the editor.
+    #[allow(clippy::new_without_default)]
     pub fn new() -> Self {
         Self {
             unfinished_rect: None,
diff --git a/src/tool/selection_tool.rs b/src/tool/selection_tool.rs
index c790734..4850a28 100644
--- a/src/tool/selection_tool.rs
+++ b/src/tool/selection_tool.rs
@@ -9,7 +9,7 @@
 use super::Tool;
 use crate::colours::DEFAULT_COLOURS;
 use crate::map::Map;
-use crate::math::{Rect, Surface, Vec2};
+use crate::math::{ExactSurface, Rect, Vec2};
 use crate::transform::Transform;
 use raylib::core::drawing::{RaylibDraw, RaylibDrawHandle};
 
@@ -21,6 +21,7 @@ pub struct SelectionTool {
 impl SelectionTool {
     /// Create a new selection tool. There should be only one such tool per program instance and it
     /// should be created in the editor.
+    #[allow(clippy::new_without_default)]
     pub fn new() -> Self {
         Self {
             selection_rect: None,
diff --git a/src/tool/wall_tool.rs b/src/tool/wall_tool.rs
index 123171c..e79d815 100644
--- a/src/tool/wall_tool.rs
+++ b/src/tool/wall_tool.rs
@@ -16,6 +16,7 @@ pub struct WallTool {
 impl WallTool {
     /// Create a new wall tool. There should only be one wall tool per program instance, which should
     /// be created inside of the editor.
+    #[allow(clippy::new_without_default)]
     pub fn new() -> Self {
         Self {
             unfinished_wall: None,