From 3b0c99351da92410bbfaba233e40376b767cb64e Mon Sep 17 00:00:00 2001
From: Arne Dußin
Date: Mon, 23 Nov 2020 23:25:45 +0100
Subject: Add triangulation function

---
 src/math/polygon/mod.rs         | 33 ++++++++++++++++++++-------------
 src/math/polygon/triangulate.rs | 30 ++++++++++++++++++++++++++++++
 2 files changed, 50 insertions(+), 13 deletions(-)

(limited to 'src/math')

diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
index e19e097..cc89169 100644
--- a/src/math/polygon/mod.rs
+++ b/src/math/polygon/mod.rs
@@ -42,7 +42,15 @@ impl<T: Scalar + Copy> Polygon<T> {
 }
 
 impl<
-        T: Scalar + Copy + ClosedSub + ClosedMul + ClosedDiv + Neg<Output = T> + PartialOrd + Zero,
+        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 {
@@ -145,18 +153,11 @@ impl<
             let prev = (c + self.corners.len() - 1) % self.corners.len();
             let next = (c + 1) % self.corners.len();
 
-            let last_edge_orientation =
-                math::triplet_orientation(self.corners[prev], self.corners[c], p);
-            let current_edge_orientation =
-                math::triplet_orientation(self.corners[c], self.corners[next], p);
-
-            if last_edge_orientation == TripletOrientation::Clockwise
-                && current_edge_orientation == TripletOrientation::Clockwise
-            {
-                false
-            } else {
-                true
-            }
+            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() {
@@ -297,6 +298,12 @@ mod test {
         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]
diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs
index 096a1c6..78dfa03 100644
--- a/src/math/polygon/triangulate.rs
+++ b/src/math/polygon/triangulate.rs
@@ -117,3 +117,33 @@ where
 
     triangles
 }
+
+#[cfg(test)]
+mod test {
+    use super::*;
+    use crate::math::Vec2;
+
+    #[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 triangles = super::triangulate(polygon);
+
+        assert_eq!(triangles.len(), 8);
+        assert_eq!(
+            triangles[0],
+            (Triangle::new(Vec2::new(2., 0.5), Vec2::new(4., 2.), Vec2::new(4., 0.)))
+        );
+    }
+}
-- 
cgit v1.2.3-70-g09d2