using System.Collections.Generic;
using UnityEngine;

namespace InteractiveVideo
{
    /// <summary>
    /// Allocation-free polygon helpers. All functions work in whatever 2D space the caller uses,
    /// as long as every input is in the same space.
    /// </summary>
    public static class PolygonUtility
    {
        /// <summary>
        /// Even-odd (ray casting) point-in-polygon test. Handles concave polygons.
        /// Returns false for null polygons or fewer than 3 points. Allocates nothing.
        /// </summary>
        public static bool ContainsPoint(IReadOnlyList<Vector2> polygon, Vector2 point)
        {
            if (polygon == null) return false;
            int n = polygon.Count;
            if (n < 3) return false;

            bool inside = false;
            for (int i = 0, j = n - 1; i < n; j = i++)
            {
                Vector2 a = polygon[i];
                Vector2 b = polygon[j];
                // Does the horizontal ray from `point` towards +X cross edge (a,b)?
                if ((a.y > point.y) != (b.y > point.y))
                {
                    float xAtY = (b.x - a.x) * (point.y - a.y) / (b.y - a.y) + a.x;
                    if (point.x < xAtY) inside = !inside;
                }
            }
            return inside;
        }

        /// <summary>Axis-aligned bounds of a polygon. Returns an empty rect at the origin for an empty polygon.</summary>
        public static Rect ComputeBounds(IReadOnlyList<Vector2> polygon)
        {
            if (polygon == null || polygon.Count == 0) return new Rect(0, 0, 0, 0);
            float minX = float.MaxValue, minY = float.MaxValue, maxX = float.MinValue, maxY = float.MinValue;
            for (int i = 0; i < polygon.Count; i++)
            {
                Vector2 p = polygon[i];
                if (p.x < minX) minX = p.x;
                if (p.x > maxX) maxX = p.x;
                if (p.y < minY) minY = p.y;
                if (p.y > maxY) maxY = p.y;
            }
            return Rect.MinMaxRect(minX, minY, maxX, maxY);
        }

        /// <summary>Twice the signed area; positive when the winding is counter-clockwise in a Y-up space.</summary>
        public static float SignedAreaTimesTwo(IReadOnlyList<Vector2> polygon)
        {
            float sum = 0f;
            int n = polygon.Count;
            for (int i = 0, j = n - 1; i < n; j = i++)
                sum += (polygon[j].x * polygon[i].y) - (polygon[i].x * polygon[j].y);
            return sum;
        }

        /// <summary>
        /// Writes Lerp(a[i], b[i], t) for every point into <paramref name="result"/> (cleared first).
        /// Requires equal point counts; returns false (result untouched) otherwise.
        /// </summary>
        public static bool LerpPolygon(IReadOnlyList<Vector2> a, IReadOnlyList<Vector2> b, float t, List<Vector2> result)
        {
            if (a == null || b == null || a.Count != b.Count) return false;
            result.Clear();
            for (int i = 0; i < a.Count; i++) result.Add(Vector2.LerpUnclamped(a[i], b[i], t));
            return true;
        }

        // Scratch list for ear clipping. Main thread only.
        private static readonly List<int> s_Remaining = new List<int>(128);

        /// <summary>
        /// Ear-clipping triangulation for simple polygons (no self-intersections, either winding).
        /// Appends triangle indices (indices into the polygon, plus <paramref name="indexOffset"/>) to
        /// <paramref name="indices"/>. O(n^2), fine for the 20-80 point polygons preprocessing produces.
        /// Degenerate input (collinear runs, small self-intersections) falls back to a triangle fan so the
        /// mask still shows something instead of failing.
        /// </summary>
        public static void Triangulate(IReadOnlyList<Vector2> polygon, List<int> indices, int indexOffset = 0)
        {
            int n = polygon.Count;
            if (n < 3) return;
            if (n == 3)
            {
                indices.Add(indexOffset); indices.Add(indexOffset + 1); indices.Add(indexOffset + 2);
                return;
            }

            bool ccw = SignedAreaTimesTwo(polygon) > 0f;
            var remaining = s_Remaining;
            remaining.Clear();
            for (int i = 0; i < n; i++) remaining.Add(i);

            int guard = 0;
            int maxIterations = n * n;
            while (remaining.Count > 3 && guard++ < maxIterations)
            {
                bool clipped = false;
                int count = remaining.Count;
                for (int i = 0; i < count; i++)
                {
                    int iPrev = remaining[(i + count - 1) % count];
                    int iCur = remaining[i];
                    int iNext = remaining[(i + 1) % count];
                    Vector2 a = polygon[iPrev], b = polygon[iCur], c = polygon[iNext];

                    if (!IsConvex(a, b, c, ccw)) continue;
                    if (AnyPointInside(polygon, remaining, a, b, c, iPrev, iCur, iNext)) continue;

                    indices.Add(indexOffset + iPrev);
                    indices.Add(indexOffset + iCur);
                    indices.Add(indexOffset + iNext);
                    remaining.RemoveAt(i);
                    clipped = true;
                    break;
                }

                if (!clipped)
                {
                    // Degenerate polygon: fan the rest from the first remaining vertex.
                    for (int i = 1; i + 1 < remaining.Count; i++)
                    {
                        indices.Add(indexOffset + remaining[0]);
                        indices.Add(indexOffset + remaining[i]);
                        indices.Add(indexOffset + remaining[i + 1]);
                    }
                    remaining.Clear();
                    return;
                }
            }

            if (remaining.Count == 3)
            {
                indices.Add(indexOffset + remaining[0]);
                indices.Add(indexOffset + remaining[1]);
                indices.Add(indexOffset + remaining[2]);
            }
        }

        private static bool IsConvex(Vector2 a, Vector2 b, Vector2 c, bool ccw)
        {
            float cross = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
            return ccw ? cross > 1e-9f : cross < -1e-9f;
        }

        private static bool AnyPointInside(IReadOnlyList<Vector2> polygon, List<int> remaining,
            Vector2 a, Vector2 b, Vector2 c, int ia, int ib, int ic)
        {
            for (int k = 0; k < remaining.Count; k++)
            {
                int idx = remaining[k];
                if (idx == ia || idx == ib || idx == ic) continue;
                if (PointInTriangle(polygon[idx], a, b, c)) return true;
            }
            return false;
        }

        private static bool PointInTriangle(Vector2 p, Vector2 a, Vector2 b, Vector2 c)
        {
            float d1 = Sign(p, a, b);
            float d2 = Sign(p, b, c);
            float d3 = Sign(p, c, a);
            bool hasNeg = (d1 < 0f) || (d2 < 0f) || (d3 < 0f);
            bool hasPos = (d1 > 0f) || (d2 > 0f) || (d3 > 0f);
            return !(hasNeg && hasPos);
        }

        private static float Sign(Vector2 p1, Vector2 p2, Vector2 p3) =>
            (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
    }
}