Add ear clipping algorithm

2 files changed, 201 insertions, 6 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.),
diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs
index 4860518..096a1c6 100644
--- a/src/math/polygon/triangulate.rs
+++ b/src/math/polygon/triangulate.rs
@@ -1,13 +1,119 @@
 //! Module for turning a polygon into a number of non-overlapping triangles.
 
 use super::Polygon;
-use crate::math::Triangle;
-use nalgebra::Scalar;
+use crate::math::{self, LineSegment, Surface, Triangle};
+use nalgebra::{RealField, Scalar};
+
+/// Type that saves the flags that match a corner in a space efficient manner.
+type Flags = u8;
+
+/// Tells the algorithm that this corner of the polygon is an ear. An ear means the adjacent corners
+/// form a triangle with this corner of which the area is entirely contained by the polygon itself.
+const FLAG_EAR: Flags = 0b0000_0001;
+/// Tells the algorithm that this corner is convex, meaning its internal angle is less than Pi.
+/// Useful, because this is a necessary condition for earness. False if the vertex is reflex.
+// TODO: The convex flag is a remnant from the previous algorithm, but currently it's not being
+// used. Consider removing it entirely.
+const FLAG_CONVEX: Flags = 0b0000_0010;
+
+fn flag_corner<T: Scalar + Copy>(polygon: &Polygon<T>, corner: usize) -> Flags
+where
+    T: RealField,
+{
+    // 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();
+    let next = (corner + 1) % polygon.corners.len();
+
+    /* Since the angle is also in counterclockwise direction, like the polygon itself, the corner
+     * is convex if and only if the angle is **not**.
+     */
+    if math::triplet_angle(
+        polygon.corners[prev],
+        polygon.corners[corner],
+        polygon.corners[next],
+    ) < T::pi()
+    {
+        // The corner is reflex.
+        return 0b0;
+    }
+
+    // The corner is convex, check if it is also an ear.
+    if polygon.contains_line_segment(&LineSegment::new(
+        polygon.corners[prev],
+        polygon.corners[next],
+    )) {
+        // Corner is an ear.
+        FLAG_EAR | FLAG_CONVEX
+    } else {
+        // Corner is not an ear.
+        FLAG_CONVEX
+    }
+}
 
 /// 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>(_polygon: &Polygon<T>) -> Vec<Triangle<T>> {
-    unimplemented!()
+pub fn triangulate<T: Scalar + Copy>(mut polygon: Polygon<T>) -> Vec<Triangle<T>>
+where
+    T: RealField,
+{
+    assert!(polygon.corners.len() >= 3);
+    /* Information about the corner of the polygon. See the flags constant for information about
+     * what the bits mean.
+     */
+    let mut flags = Vec::with_capacity(polygon.corners.len());
+    for c in 0..polygon.corners.len() {
+        flags.push(flag_corner(&polygon, c));
+    }
+
+    let mut triangles = Vec::with_capacity(polygon.corners.len() - 2);
+    // Clip ears until there's only the last triangle left.
+    /* NOTE: This could be changed to > 2 and the last triangle would be pushed inside the loop,
+     * because it is also detected as an ear, however this is more logical to the original idea
+     * imo.
+     */
+    while polygon.corners.len() > 3 {
+        // Find the ear with the highest index.
+        let ear = flags
+            .iter()
+            .rposition(|&x| (x & FLAG_EAR) != 0)
+            .expect("Polygon has more than three vertices, but no ear.");
+
+        // Add the ear's triangle to the list.
+        {
+            let prev = (ear + polygon.corners.len() - 1) % polygon.corners.len();
+            let next = (ear + 1) % polygon.corners.len();
+            triangles.push(Triangle::new(
+                polygon.corners[prev],
+                polygon.corners[ear],
+                polygon.corners[next],
+            ));
+
+            // Remove the ear from the polygon and the flag list.
+            polygon.corners.remove(ear);
+            flags.remove(ear);
+        }
+
+        // Reassess the status of the two adjacent points. Notice that since the ear was removed,
+        // their array positions have changed.
+        let prev = if ear == 0 || ear == polygon.corners.len() {
+            polygon.corners.len() - 1
+        } else {
+            ear - 1
+        };
+        let next = if ear == polygon.corners.len() { 0 } else { ear };
+
+        flags[prev] = flag_corner(&polygon, prev);
+        flags[next] = flag_corner(&polygon, next);
+    }
+
+    // Push the remaining triangle into the list.
+    triangles.push(Triangle::new(
+        polygon.corners[0],
+        polygon.corners[1],
+        polygon.corners[2],
+    ));
+
+    triangles
 }