Merge branch 'triangulation' into polygon-rooms

1 files changed, 341 insertions, 0 deletions

diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
new file mode 100644
index 0000000..cda1f2a
--- /dev/null
+++ b/src/math/polygon/mod.rs
@@ -0,0 +1,341 @@
+//! Contains functions and structures to help with operations on polygons.
+
+pub mod polygon_graph;
+pub mod triangulate;
+
+pub use polygon_graph::*;
+pub use triangulate::*;
+
+use super::{LineSegment, Surface, TripletOrientation, Vec2};
+use crate::math;
+use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar};
+use num_traits::Zero;
+use serde::{Deserialize, Serialize};
+use std::ops::Neg;
+
+#[derive(Debug, Deserialize, Serialize)]
+// TODO: Support polygons with holes
+pub struct Polygon<T: Scalar + Copy> {
+    pub corners: Vec<Vec2<T>>,
+}
+
+impl<T: Scalar + Copy> Polygon<T> {
+    pub fn new(corners: Vec<Vec2<T>>) -> Self {
+        Self { corners }
+    }
+
+    /// Check whether a point is inside a polygon or not. If a point lies on an edge, it also
+    /// counts as inside the polygon.
+
+    /// 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>>
+    where
+        T: RealField,
+    {
+        let mut graph = PolygonGraph::from_polygon(&self);
+        graph.add_all(&other);
+
+        // TODO: Make bounding box support multiple polygons
+        vec![graph.bounding_polygon()]
+    }
+}
+
+impl<
+        T: Scalar
+            + Copy
+            + ClosedSub
+            + ClosedMul
+            + ClosedDiv
+            + Neg<Output = T>
+            + PartialOrd
+            + RealField
+            + Zero,
+    > Surface<T> for Polygon<T>
+{
+    fn contains_point(&self, p: &Vec2<T>) -> bool {
+        let n = self.corners.len();
+
+        let a = self.corners[n - 1];
+        let mut b = self.corners[n - 2];
+        let mut ax;
+        let mut ay = a.y - p.y;
+        let mut bx = b.x - p.x;
+        let mut by = b.y - p.y;
+
+        let mut lup = by > ay;
+        for i in 0..n {
+            // ax = bx;
+            ay = by;
+            b = self.corners[i];
+            bx = b.x - p.x;
+            by = b.y - p.y;
+
+            if ay == by {
+                continue;
+            }
+            lup = by > ay;
+        }
+
+        let mut depth = 0;
+        for i in 0..n {
+            ax = bx;
+            ay = by;
+            let b = &self.corners[i];
+            bx = b.x - p.x;
+            by = b.y - p.y;
+
+            if ay < T::zero() && by < T::zero() {
+                // both "up" or both "down"
+                continue;
+            }
+            if ay > T::zero() && by > T::zero() {
+                // both "up" or both "down"
+                continue;
+            }
+            if ax < T::zero() && bx < T::zero() {
+                // both points on the left
+                continue;
+            }
+
+            if ay == by && (if ax < bx { ax } else { bx }) <= T::zero() {
+                return true;
+            }
+            if ay == by {
+                continue;
+            }
+
+            let lx = ax + (((bx - ax) * -ay) / (by - ay));
+            if lx == T::zero() {
+                // point on edge
+                return true;
+            }
+            if lx > T::zero() {
+                depth += 1;
+            }
+            if ay == T::zero() && lup && by > ay {
+                // hit vertex, both up
+                depth -= 1;
+            }
+            if ay == T::zero() && !lup && by < ay {
+                // hit vertex, both down
+                depth -= 1;
+            }
+
+            lup = by > ay;
+        }
+
+        (depth & 1) == 1
+    }
+
+    fn contains_line_segment(&self, line_segment: &LineSegment<T>) -> 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) {
+            return false;
+        }
+
+        /* Both end-points are inside the polygon. */
+
+        /* In case the an endpoint of the line segment is equal to a corner of the polygon, it's
+         * not enough to merely check one edge, since if the corner is reflex, the segment may
+         * still be inside, eventhough its similar to the outwards pointing normal of one edge, but
+         * may be to the inside of the other edge.
+         */
+        let mut start_looks_inside = false;
+        let mut end_looks_inside = false;
+        /* Helper function that checks if a point p, when starting from the given corner c is in a
+         * direction so that considering both edges that are connected to c, the point is in the
+         * direction of the inside of the polygon.
+         */
+        let corner_vec_pointing_inside = |p: Vec2<T>, c: usize| {
+            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);
+
+            vec_angle == T::zero() || vec_angle >= edge_angle
+        };
+
+        for c in 0..self.corners.len() {
+            if line_segment.start == self.corners[c] {
+                start_looks_inside = corner_vec_pointing_inside(line_segment.end, c);
+                if !start_looks_inside {
+                    return false;
+                }
+            }
+            if line_segment.end == self.corners[c] {
+                end_looks_inside = corner_vec_pointing_inside(line_segment.start, c);
+                if !end_looks_inside {
+                    return false;
+                }
+            }
+        }
+
+        if start_looks_inside && end_looks_inside {
+            return true;
+        }
+
+        /* Check the intersections of the line segment with all polygon edges and see if it is
+         * piercing through any of them.
+         */
+        for c in 0..self.corners.len() {
+            let next = (c + 1) % self.corners.len();
+
+            let current_edge = LineSegment::new(self.corners[c], self.corners[next]);
+
+            if LineSegment::intersect(&line_segment, &current_edge) {
+                let orientation_start = math::triplet_orientation(
+                    current_edge.start,
+                    current_edge.end,
+                    line_segment.start,
+                );
+                let orientation_end = math::triplet_orientation(
+                    current_edge.start,
+                    current_edge.end,
+                    line_segment.end,
+                );
+                match (orientation_start, orientation_end) {
+                    /* If at least one of the points is on the edge, make sure, the line points
+                     * inside of the polygon, not to the outside.
+                     */
+                    (TripletOrientation::Collinear, o) => {
+                        if !start_looks_inside && o == TripletOrientation::Clockwise {
+                            return false;
+                        }
+                    }
+                    (o, TripletOrientation::Collinear) => {
+                        if !end_looks_inside && o == TripletOrientation::Clockwise {
+                            return false;
+                        }
+                    }
+                    /* Start and endpoint are on different sides of the edge, therefore the line
+                     * must be partially outside.
+                     */
+                    _ => return false,
+                }
+            }
+        }
+
+        true
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[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.),
+        ]);
+
+        assert!(!polygon.contains_point(&Vec2::new(1., -2.)));
+        assert!(!polygon.contains_point(&Vec2::new(-1., 0.5)));
+        assert!(polygon.contains_point(&Vec2::new(0., 0.5)));
+        assert!(polygon.contains_point(&Vec2::new(0.5, 1.)));
+        assert!(polygon.contains_point(&Vec2::new(0.5, 1.5)));
+        assert!(!polygon.contains_point(&Vec2::new(-2., 1.9)));
+        assert!(!polygon.contains_point(&Vec2::new(0., 3.)));
+        assert!(polygon.contains_point(&Vec2::new(1., 3.)));
+    }
+
+    #[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.),
+        ]);
+
+        /* NOTE: From now on, inside means inside the polygon, but might be on an edge or on a
+         * corner point, really inside means inside and not on an edge.
+         */
+
+        // Start point really inside, end point really inside. Line not completely inside.
+        assert!(!polygon
+            .contains_line_segment(&LineSegment::new(Vec2::new(2.5, 0.5), Vec2::new(0.5, 2.5))));
+
+        // Start point on edge, end point on corner, line completely outside.
+        assert!(!polygon
+            .contains_line_segment(&LineSegment::new(Vec2::new(1.5, 2.), Vec2::new(4., 2.))));
+
+        // Start point on edge, end point on edge, line inside.
+        assert!(polygon
+            .contains_line_segment(&LineSegment::new(Vec2::new(3.5, 3.), Vec2::new(3.5, 4.5))));
+
+        // Start point on corner, end point on corner, line inside.
+        assert!(polygon
+            .contains_line_segment(&LineSegment::new(Vec2::new(5.5, 3.), Vec2::new(6.5, 4.5))));
+
+        // Start point really inside, end point on edge. Line not inside.
+        assert!(!polygon
+            .contains_line_segment(&LineSegment::new(Vec2::new(3.5, 0.5), Vec2::new(5.5, 0.5))));
+
+        // Start point and endpoint outside. Line completely outside.
+        assert!(!polygon
+            .contains_line_segment(&LineSegment::new(Vec2::new(7.0, 0.), Vec2::new(7.5, 1.))));
+
+        // Start point on vertex, pointing in same dir as one of the adjacent edge normals,
+        // completely inside.
+        assert!(
+            polygon.contains_line_segment(&LineSegment::new(Vec2::new(2., 0.5), Vec2::new(4., 0.)))
+        );
+
+        // Start and end point on vertex, not pointing in the dir of adjacent edge normals,
+        // not completely inside.
+        assert!(
+            !polygon.contains_line_segment(&LineSegment::new(Vec2::new(4., 2.), Vec2::new(0., 0.)))
+        );
+    }
+
+    #[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 second = Polygon::new(vec![
+            Vec2::new(0., 0.),
+            Vec2::new(-2., 2.),
+            Vec2::new(3., 2.),
+            Vec2::new(1.5, 0.),
+        ]);
+
+        let union = first.unite(second);
+        assert_eq!(union.len(), 1);
+        let union = &union[0];
+
+        println!("Union of the two polygons: {:?}", union);
+
+        assert_eq!(union.corners.len(), 11);
+        assert!(union
+            .corners
+            .iter()
+            .find(|&p| p.x == 0. && p.y == 0.)
+            .is_some());
+    }
+}