1 files changed, 177 insertions, 0 deletions
diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
new file mode 100644
index 0000000..4530857
--- /dev/null
+++ b/src/math/polygon/mod.rs
@@ -0,0 +1,177 @@
+//! 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::Vec2;
+use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar};
+use num_traits::Zero;
+use std::ops::Neg;
+
+#[derive(Debug)]
+// 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.
+    pub fn contains_point(&self, p: Vec2<T>) -> bool
+    where
+        T: Zero + ClosedSub + ClosedMul + ClosedDiv + Neg<Output = T> + PartialOrd,
+    {
+        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
+    }
+
+    /// 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()]
+    }
+}
+
+#[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 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());
+    }
+}