// @wuys/map · data/triangulate.js
//
// Ear-clipping polygon triangulation. Used by the flag layer to break each
// polygon into small triangles. Within a small triangle, orthographic
// projection is near-linear, so a per-triangle 2D affine transform very
// closely matches the true projection — giving the user both full fill AND
// no flag distortion on globe rotation.
//
// Input:  ring of [lon, lat] points (CCW or CW, doesn't matter — we detect
//         and normalise to CCW for the ear test).
// Output: array of triangles, each as [[lon,lat],[lon,lat],[lon,lat]].
//
// Robust enough for country outlines (which are well-formed simple polygons
// at the simplification levels we ship). Does not handle holes — country
// data has no holes after preprocessing.

/**
 * Douglas-Peucker line simplification. Drops vertices whose perpendicular
 * distance to the segment between their non-dropped neighbours is less than
 * `tolerance`. Lower tolerance → more vertices kept.
 *
 * @param {Array<[number, number]>} pts  ring (open — first ≠ last)
 * @param {number} tolerance  perpendicular distance threshold (in lat/lon°)
 * @returns {Array<[number, number]>}
 */
export function simplifyDP(pts, tolerance) {
  if (!pts || pts.length < 4) return pts ? pts.slice() : [];
  const keep = new Uint8Array(pts.length);
  keep[0] = 1;
  keep[pts.length - 1] = 1;
  const stack = [[0, pts.length - 1]];
  while (stack.length) {
    const [a, b] = stack.pop();
    if (b <= a + 1) continue;
    const [ax, ay] = pts[a];
    const [bx, by] = pts[b];
    let maxD = 0, maxI = -1;
    const dx = bx - ax, dy = by - ay;
    const len2 = dx * dx + dy * dy || 1;
    for (let i = a + 1; i < b; i++) {
      const [px, py] = pts[i];
      // Perpendicular distance from P to segment AB.
      const t = ((px - ax) * dx + (py - ay) * dy) / len2;
      const cx = ax + dx * t;
      const cy = ay + dy * t;
      const ddx = px - cx, ddy = py - cy;
      const d2 = ddx * ddx + ddy * ddy;
      if (d2 > maxD) { maxD = d2; maxI = i; }
    }
    if (maxI !== -1 && maxD > tolerance * tolerance) {
      keep[maxI] = 1;
      stack.push([a, maxI], [maxI, b]);
    }
  }
  const out = [];
  for (let i = 0; i < pts.length; i++) if (keep[i]) out.push(pts[i]);
  return out;
}

/**
 * Simplify a closed ring to AT MOST `targetCount` vertices by binary-searching
 * the DP tolerance. Always keeps at least 4 vertices. Used by the flag layer
 * to bound the triangle count per polygon (essential for SVG element budget).
 */
export function simplifyToCount(ring, targetCount) {
  if (!ring || ring.length <= targetCount) return ring ? ring.slice() : [];
  // Open the ring for DP.
  let pts = ring;
  if (pts.length >= 2) {
    const [fx, fy] = pts[0];
    const [lx, ly] = pts[pts.length - 1];
    if (Math.abs(fx - lx) < 1e-12 && Math.abs(fy - ly) < 1e-12) {
      pts = pts.slice(0, -1);
    }
  }
  // Binary search tolerance.
  let lo = 0, hi = 50;       // 50° tolerance is more than enough to collapse any country
  let best = pts;
  for (let iter = 0; iter < 24; iter++) {
    const mid = (lo + hi) / 2;
    const s = simplifyDP(pts, mid);
    if (s.length > targetCount) {
      lo = mid;
    } else {
      best = s;
      if (s.length === targetCount) return best;
      hi = mid;
    }
    if (hi - lo < 1e-4) break;
  }
  // Ensure at least 4 vertices — a triangle isn't enough geometry for the
  // affine-per-triangle approach to look right.
  if (best.length < 4) return pts.slice(0, Math.min(pts.length, 4));
  return best;
}

/**
 * Signed area (shoelace) — positive for CCW, negative for CW.
 */
function signedArea(pts) {
  let s = 0;
  const n = pts.length;
  for (let i = 0; i < n; i++) {
    const [x0, y0] = pts[i];
    const [x1, y1] = pts[(i + 1) % n];
    s += x0 * y1 - x1 * y0;
  }
  return s / 2;
}

/** Is point P strictly inside triangle ABC (CCW orientation)? */
function pointInTriangle(px, py, ax, ay, bx, by, cx, cy) {
  // Barycentric — non-negative => inside (allowing on-edge).
  const v0x = cx - ax, v0y = cy - ay;
  const v1x = bx - ax, v1y = by - ay;
  const v2x = px - ax, v2y = py - ay;
  const dot00 = v0x * v0x + v0y * v0y;
  const dot01 = v0x * v1x + v0y * v1y;
  const dot02 = v0x * v2x + v0y * v2y;
  const dot11 = v1x * v1x + v1y * v1y;
  const dot12 = v1x * v2x + v1y * v2y;
  const denom = dot00 * dot11 - dot01 * dot01;
  if (Math.abs(denom) < 1e-20) return false;
  const inv = 1 / denom;
  const u = (dot11 * dot02 - dot01 * dot12) * inv;
  const v = (dot00 * dot12 - dot01 * dot02) * inv;
  return u > 1e-9 && v > 1e-9 && (u + v) < 1 - 1e-9;
}

/** Cross of (b - a) × (c - b) — positive turn-left (CCW), negative turn-right. */
function cross(ax, ay, bx, by, cx, cy) {
  return (bx - ax) * (cy - by) - (by - ay) * (cx - bx);
}

/**
 * Ear-clipping triangulation of a simple polygon (no holes).
 * @param {Array<[number, number]>} ring  ordered vertex list (any winding)
 * @returns {Array<Array<[number, number]>>}  list of triangles
 */
export function earClip(ring) {
  if (!ring || ring.length < 3) return [];
  // Deduplicate last == first if the ring is closed.
  let pts = ring;
  if (pts.length >= 2) {
    const [fx, fy] = pts[0];
    const [lx, ly] = pts[pts.length - 1];
    if (Math.abs(fx - lx) < 1e-12 && Math.abs(fy - ly) < 1e-12) {
      pts = pts.slice(0, -1);
    }
  }
  if (pts.length < 3) return [];

  // Normalise to CCW so the ear test (left turn at convex vertices) is correct.
  if (signedArea(pts) < 0) pts = pts.slice().reverse();

  // Index list. We remove ears by splicing this list, leaving pts untouched.
  const idx = [];
  for (let i = 0; i < pts.length; i++) idx.push(i);

  const triangles = [];
  let guard = 3 * pts.length;          // safety cap against pathological input
  while (idx.length > 3 && guard-- > 0) {
    let earFound = false;
    for (let i = 0; i < idx.length; i++) {
      const prev = idx[(i - 1 + idx.length) % idx.length];
      const curr = idx[i];
      const next = idx[(i + 1) % idx.length];
      const [ax, ay] = pts[prev];
      const [bx, by] = pts[curr];
      const [cx, cy] = pts[next];
      // Convex (left turn) and CCW polygon → potential ear.
      if (cross(ax, ay, bx, by, cx, cy) <= 0) continue;
      // No other polygon vertex inside this triangle.
      let contains = false;
      for (let j = 0; j < idx.length; j++) {
        if (j === i) continue;
        const k = idx[j];
        if (k === prev || k === next) continue;
        const [px, py] = pts[k];
        if (pointInTriangle(px, py, ax, ay, bx, by, cx, cy)) { contains = true; break; }
      }
      if (contains) continue;
      // It's an ear — emit + clip.
      triangles.push([pts[prev], pts[curr], pts[next]]);
      idx.splice(i, 1);
      earFound = true;
      break;
    }
    // No ear found this pass — polygon is malformed. Bail with what we have.
    if (!earFound) break;
  }
  if (idx.length === 3) {
    triangles.push([pts[idx[0]], pts[idx[1]], pts[idx[2]]]);
  }
  return triangles;
}
