//! Module for turning a polygon into a number of non-overlapping triangles.

use super::Polygon;
use crate::math::{self, LineSegment, Surface, Triangle};
use float_cmp::ApproxEq;
use nalgebra::RealField;

/// 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: RealField, M>(polygon: &Polygon<T>, corner: usize, margin: M) -> Flags
where
    T: ApproxEq<Margin = M>,
    M: Copy,
{
    // 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],
        margin,
    ) < 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]),
        margin,
    ) {
        // 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: RealField, M>(mut polygon: Polygon<T>, margin: M) -> Vec<Triangle<T>>
where
    T: ApproxEq<Margin = M>,
    M: Copy,
{
    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, margin));
    }

    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 = match flags.iter().rposition(|&x| (x & FLAG_EAR) != 0) {
            Some(pos) => pos,
            None => panic!(
                "Polygon has more than three vertices, but no ear: {:?}",
                polygon
            ),
        };

        // 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],
                margin,
            ));

            // 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, margin);
        flags[next] = flag_corner(&polygon, next, margin);
    }

    // Push the remaining triangle into the list.
    triangles.push(Triangle::new(
        polygon.corners[0],
        polygon.corners[1],
        polygon.corners[2],
        margin,
    ));

    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.),
            ],
            (f64::EPSILON, 0),
        )
        .unwrap();

        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.)))
        );
    }
}