Outline checks: inside, crossing, cut-outs

/** Points along the outline/run with arcs broken into chords of at most `step` radians. */
export function flatten(pts, closed = false, step = Math.PI / 36) {
  const out = [];
  const n = pts.length, segs = closed ? n : n - 1;
  for (let i = 0; i < segs; i++) {
    const p = pts[i], q = pts[(i + 1) % n];
    out.push({ x: p.x, y: p.y });
    const a = arcOf(p, q, p.b);
    if (!a) continue;
    const k = Math.max(2, Math.ceil(Math.abs(a.sweep) / step));
    for (let j = 1; j < k; j++) { const t = a.a0 + a.sweep * j / k; out.push({ x: a.cx + a.r * Math.cos(t), y: a.cy + a.r * Math.sin(t) }); }
  }
  if (!closed && n) out.push({ x: pts[n - 1].x, y: pts[n - 1].y });
  return out;
}

/** Ray-cast point in polygon (arcs followed); the boundary itself is not relied on by callers. */
export function pointInPolygon(p, pts0) {
  const pts = hasArcs(pts0) ? flatten(pts0, true) : pts0;
  let inside = false;
  for (let i = 0, j = pts.length - 1; i < pts.length; j = i++) {
    const a = pts[i], b = pts[j];
    if ((a.y > p.y) !== (b.y > p.y) && p.x < ((b.x - a.x) * (p.y - a.y)) / (b.y - a.y) + a.x) inside = !inside;
  }
  return inside;
}

/** Do segments ab and cd cross or touch? (eps relative to their size) */
export function segmentsIntersect(a, b, c, d, eps = 1e-9) {
  const s = Math.max(dist(a, b), dist(c, d), 1) * eps;
  const d1 = cross(c, d, a), d2 = cross(c, d, b), d3 = cross(a, b, c), d4 = cross(a, b, d);
  if (((d1 > s && d2 < -s) || (d1 < -s && d2 > s)) && ((d3 > s && d4 < -s) || (d3 < -s && d4 > s))) return true;
  const on = (p, q, r, dv) => Math.abs(dv) <= s && Math.min(p.x, q.x) - s <= r.x && r.x <= Math.max(p.x, q.x) + s && Math.min(p.y, q.y) - s <= r.y && r.y <= Math.max(p.y, q.y) + s;
  return on(c, d, a, d1) || on(c, d, b, d2) || on(a, b, c, d3) || on(a, b, d, d4);
}

/** Does a closed outline cross itself? (Neighbouring edges share a vertex and are skipped.) */
export function selfIntersects(pts0) {
  const pts = hasArcs(pts0) ? flatten(pts0, true) : pts0;
  const n = pts.length;
  if (n < 4) return false;
  for (let i = 0; i < n; i++) {
    const a = pts[i], b = pts[(i + 1) % n];
    for (let j = i + 1; j < n; j++) {
      if (j === i || (j + 1) % n === i || (i + 1) % n === j) continue;
      if (segmentsIntersect(a, b, pts[j], pts[(j + 1) % n])) return true;
    }
  }
  return false;
}

/**
 * Why an outline can't be measured, or null. Checks it is a real polygon and doesn't cross
 * itself (a crossing outline has no meaningful area: the shoelace would be wrong).
 */
export function outlineProblem(pts, what = 'area') {
  if (pts.length < 3 && !(pts.length === 2 && hasArcs(pts))) return t('geom.' + what + '.min');
  if (selfIntersects(pts)) return t('geom.' + what + '.cross');
  if (polygonArea(pts) < 1e-9) return t('geom.' + what + '.empty');
  return null;
}

/** Why a cut-out can't go into an area, or null: it must sit fully inside and clear of other cut-outs. */
export function holeProblem(outer, holes, hole) {
  const p = outlineProblem(hole, 'hole');
  if (p) return p;
  const fh = flatten(hole, true);
  if (outlinesCross(outer, hole) || !fh.every((v) => pointInPolygon(v, outer))) return t('geom.hole.inside');
  for (const h of holes) {
    if (outlinesCross(h, hole) || fh.some((v) => pointInPolygon(v, h)) || flatten(h, true).some((v) => pointInPolygon(v, hole))) return t('geom.hole.overlap');
  }
  return null;
}