Merge branch 'triangulation' into polygon-rooms

1 files changed, 149 insertions, 0 deletions

diff --git a/src/math/polygon/triangulate.rs b/src/math/polygon/triangulate.rs
new file mode 100644
index 0000000..78dfa03
--- /dev/null
+++ b/src/math/polygon/triangulate.rs
@@ -0,0 +1,149 @@
+//! Module for turning a polygon into a number of non-overlapping triangles.
+
+use super::Polygon;
+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>(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
+}
+
+#[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.)))
+        );
+    }
+}