using System.Collections.Generic;
using UnityEngine;
using UnityEngine.UI;

// Surface pleine d'un polygone quelconque, dessinée directement dans le maillage
// de l'UI. La triangulation se fait par découpe d'oreilles : un rectangle passe,
// une forme en L ou en U aussi, y compris avec un angle rentrant.
//
// Posée et alimentée par CreateShape, il n'y a rien à régler à la main.
[RequireComponent(typeof(CanvasRenderer))]
public class ShapeFill : MaskableGraphic
{
    [SerializeField, HideInInspector] private List<Vector2> points = new();

    public void SetPoints(IEnumerable<Vector2> value)
    {
        points.Clear();
        points.AddRange(value);

        SetVerticesDirty();
    }

    protected override void OnPopulateMesh(VertexHelper vh)
    {
        vh.Clear();

        if (points.Count < 3) return;

        for (int i = 0; i < points.Count; i++)
        {
            UIVertex vertex = UIVertex.simpleVert;
            vertex.position = points[i];
            vertex.color = color;

            vh.AddVert(vertex);
        }

        List<int> triangles = Triangulate(points);

        for (int i = 0; i + 2 < triangles.Count; i += 3)
        {
            vh.AddTriangle(triangles[i], triangles[i + 1], triangles[i + 2]);
        }
    }

    // Découpe d'oreilles : on retire un à un les sommets saillants dont le
    // triangle ne contient aucun autre point, jusqu'à ce qu'il n'en reste que trois.
    private static List<int> Triangulate(List<Vector2> polygon)
    {
        List<int> triangles = new();

        if (polygon.Count < 3) return triangles;

        List<int> remaining = new();
        for (int i = 0; i < polygon.Count; i++) remaining.Add(i);

        // On travaille toujours dans le sens anti-horaire.
        if (SignedArea(polygon) < 0f) remaining.Reverse();

        // Garde-fou : un polygone dégénéré ne doit pas boucler indéfiniment.
        int guard = polygon.Count * polygon.Count;

        while (remaining.Count > 3 && guard-- > 0)
        {
            bool clipped = false;

            for (int i = 0; i < remaining.Count; i++)
            {
                int previous = remaining[(i - 1 + remaining.Count) % remaining.Count];
                int current = remaining[i];
                int next = remaining[(i + 1) % remaining.Count];

                if (!IsEar(polygon, remaining, previous, current, next)) continue;

                triangles.Add(previous);
                triangles.Add(current);
                triangles.Add(next);

                remaining.RemoveAt(i);
                clipped = true;
                break;
            }

            // Plus aucune oreille : polygone croisé ou aplati, on s'arrête ici
            // avec ce qui a déjà été trianglé.
            if (!clipped) break;
        }

        if (remaining.Count == 3) triangles.AddRange(remaining);

        return triangles;
    }

    private static bool IsEar(List<Vector2> polygon, List<int> remaining, int previous, int current, int next)
    {
        Vector2 a = polygon[previous];
        Vector2 b = polygon[current];
        Vector2 c = polygon[next];

        // Sommet rentrant : pas une oreille.
        if (Cross(b - a, c - b) <= 0f) return false;

        foreach (int index in remaining)
        {
            if (index == previous || index == current || index == next) continue;

            if (InTriangle(polygon[index], a, b, c)) return false;
        }

        return true;
    }

    private static bool InTriangle(Vector2 point, Vector2 a, Vector2 b, Vector2 c)
    {
        float ab = Cross(b - a, point - a);
        float bc = Cross(c - b, point - b);
        float ca = Cross(a - c, point - c);

        bool negative = ab < 0f || bc < 0f || ca < 0f;
        bool positive = ab > 0f || bc > 0f || ca > 0f;

        return !(negative && positive);
    }

    private static float SignedArea(List<Vector2> polygon)
    {
        float area = 0f;

        for (int i = 0; i < polygon.Count; i++)
        {
            Vector2 a = polygon[i];
            Vector2 b = polygon[(i + 1) % polygon.Count];

            area += a.x * b.y - b.x * a.y;
        }

        return area * 0.5f;
    }

    private static float Cross(Vector2 u, Vector2 v)
    {
        return u.x * v.y - u.y * v.x;
    }
}