// @wuys/map · data/polylabel.js
//
// Pole of inaccessibility — the point INSIDE a polygon that's FARTHEST from
// any boundary. The classic Mapbox algorithm (Vladimir Agafonkin, 2016) for
// label/icon placement: subdivide the polygon's bounding box into cells, score
// each cell by (distance from cell-center to nearest polygon edge) + (cell
// half-diagonal as an upper-bound bonus), keep the best, recursively
// subdivide the most-promising cells, stop when no cell can beat the best
// found so far by more than `precision`.
//
// Returns `{ x, y, distance }` — the geographic pole + the inscribed-circle
// radius. The largest aspect-ratio-R rectangle that fits inside that circle
// has dims `2r·R/√(R²+1) × 2r/√(R²+1)` — used downstream for flag rendering.

/**
 * @param {Array<[number,number]>} polygon  closed outer ring (lon/lat pairs)
 * @param {number} [precision=0.1]
 * @returns {{ x:number, y:number, distance:number }}
 */
export function polylabel(polygon, precision = 0.1) {
  if (!polygon || polygon.length < 3) return { x: 0, y: 0, distance: 0 };

  // Bounding box of the polygon.
  let minX = Infinity, minY = Infinity, maxX = -Infinity, maxY = -Infinity;
  for (const p of polygon) {
    if (p[0] < minX) minX = p[0]; if (p[0] > maxX) maxX = p[0];
    if (p[1] < minY) minY = p[1]; if (p[1] > maxY) maxY = p[1];
  }
  const w = maxX - minX, h = maxY - minY;
  const cellSize = Math.min(w, h);
  if (cellSize === 0) return { x: minX, y: minY, distance: 0 };
  let half = cellSize / 2;

  // Min-heap keyed by `max` (upper-bound on the best cell that this could
  // become after subdivision). Plain array, sorted on each push — N is small.
  const queue = [];
  function pushCell(c) {
    queue.push(c);
    // insertion at correct sort position (binary)
    let i = queue.length - 1;
    while (i > 0 && queue[i].max > queue[Math.floor((i - 1) / 2)].max) {
      [queue[i], queue[Math.floor((i - 1) / 2)]] = [queue[Math.floor((i - 1) / 2)], queue[i]];
      i = Math.floor((i - 1) / 2);
    }
  }
  function popCell() {
    const top = queue[0];
    const last = queue.pop();
    if (queue.length) {
      queue[0] = last;
      let i = 0;
      while (true) {
        const l = 2 * i + 1, r = 2 * i + 2;
        let largest = i;
        if (l < queue.length && queue[l].max > queue[largest].max) largest = l;
        if (r < queue.length && queue[r].max > queue[largest].max) largest = r;
        if (largest === i) break;
        [queue[i], queue[largest]] = [queue[largest], queue[i]];
        i = largest;
      }
    }
    return top;
  }

  // Seed cells covering the bbox.
  for (let x = minX; x < maxX; x += cellSize) {
    for (let y = minY; y < maxY; y += cellSize) {
      pushCell(makeCell(x + half, y + half, half, polygon));
    }
  }

  // Start with the polygon centroid as the best-known.
  let best = getCentroidCell(polygon);
  // The bbox center can sometimes beat the centroid (for U-shaped polygons).
  const bbCenter = makeCell(minX + w / 2, minY + h / 2, 0, polygon);
  if (bbCenter.d > best.d) best = bbCenter;

  while (queue.length) {
    const cell = popCell();
    if (cell.d > best.d) best = cell;
    if (cell.max - best.d <= precision) continue;
    // Subdivide.
    half = cell.h / 2;
    pushCell(makeCell(cell.x - half, cell.y - half, half, polygon));
    pushCell(makeCell(cell.x + half, cell.y - half, half, polygon));
    pushCell(makeCell(cell.x - half, cell.y + half, half, polygon));
    pushCell(makeCell(cell.x + half, cell.y + half, half, polygon));
  }

  return { x: best.x, y: best.y, distance: best.d };
}

function makeCell(x, y, h, polygon) {
  const d = pointToPolygonDist(x, y, polygon);
  // Upper bound: if a corner of this cell happens to be deeper-inside than
  // its centre, by at most h·√2.
  return { x, y, h, d, max: d + h * Math.SQRT2 };
}

/** Signed distance: positive inside the polygon, negative outside. */
function pointToPolygonDist(x, y, polygon) {
  let inside = false;
  let minDistSq = Infinity;
  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    const ax = polygon[i][0], ay = polygon[i][1];
    const bx = polygon[j][0], by = polygon[j][1];
    if ((ay > y) !== (by > y) && x < (bx - ax) * (y - ay) / (by - ay) + ax) {
      inside = !inside;
    }
    const dsq = segDistSq(x, y, ax, ay, bx, by);
    if (dsq < minDistSq) minDistSq = dsq;
  }
  const d = Math.sqrt(minDistSq);
  return inside ? d : -d;
}

/** Squared distance from (px,py) to the segment (ax,ay)-(bx,by). */
function segDistSq(px, py, ax, ay, bx, by) {
  let x = ax, y = ay;
  let dx = bx - ax, dy = by - ay;
  if (dx !== 0 || dy !== 0) {
    const t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);
    if (t > 1) { x = bx; y = by; }
    else if (t > 0) { x += dx * t; y += dy * t; }
  }
  dx = px - x; dy = py - y;
  return dx * dx + dy * dy;
}

/** Polygon centroid (using the shoelace formula). */
function getCentroidCell(polygon) {
  let area = 0, x = 0, y = 0;
  for (let i = 0, j = polygon.length - 1; i < polygon.length; j = i++) {
    const ax = polygon[i][0], ay = polygon[i][1];
    const bx = polygon[j][0], by = polygon[j][1];
    const f = ax * by - bx * ay;
    x += (ax + bx) * f;
    y += (ay + by) * f;
    area += f * 3;
  }
  if (area === 0) return makeCell(polygon[0][0], polygon[0][1], 0, polygon);
  return makeCell(x / area, y / area, 0, polygon);
}
