Add ear clipping algorithm

1 files changed, 91 insertions, 2 deletions

diff --git a/src/math/polygon/mod.rs b/src/math/polygon/mod.rs
index d351ec7..baa1e6d 100644
--- a/src/math/polygon/mod.rs
+++ b/src/math/polygon/mod.rs
@@ -6,7 +6,8 @@ pub mod triangulate;
 pub use polygon_graph::*;
 pub use triangulate::*;
 
-use super::{LineSegment, Surface, Vec2};
+use super::{LineSegment, Surface, TripletOrientation, Vec2};
+use crate::math;
 use nalgebra::{ClosedDiv, ClosedMul, ClosedSub, RealField, Scalar};
 use num_traits::Zero;
 use std::ops::Neg;
@@ -120,7 +121,51 @@ impl<
     }
 
     fn contains_line_segment(&self, line_segment: &LineSegment<T>) -> bool {
-        unimplemented!()
+        /* 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. */
+
+        /* 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) | (o, TripletOrientation::Collinear) => {
+                        if 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
     }
 }
 
@@ -151,6 +196,50 @@ 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.),
+        ]);
+
+        /* 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.))));
+    }
+
+    #[test]
     fn polygon_union() {
         let first = Polygon::new(vec![
             Vec2::new(-2., 1.),