Pattern outlines: curves, lengths and areas

/** One centripetal Catmull–Rom span p1 → p2 (p0, p3 its neighbours), `steps` samples after p1 (p2 included). */
function crSpan(p0, p1, p2, p3, steps) {
  const tj = (ti, a, b) => ti + Math.max(Math.sqrt(dst(a, b)), 1e-9);
  const t0 = 0, t1 = tj(t0, p0, p1), t2 = tj(t1, p1, p2), t3 = tj(t2, p2, p3);
  const out = [];
  for (let s = 1; s <= steps; s++) {
    const t = t1 + (t2 - t1) * (s / steps);
    const L = (pa, pb, ta, tb) => { const k = (tb - ta) < 1e-12 ? 0 : (t - ta) / (tb - ta); return { x: pa.x + (pb.x - pa.x) * k, y: pa.y + (pb.y - pa.y) * k }; };
    const A1 = L(p0, p1, t0, t1), A2 = L(p1, p2, t1, t2), A3 = L(p2, p3, t2, t3);
    const B1 = L(A1, A2, t0, t2), B2 = L(A2, A3, t1, t3);
    out.push(L(B1, B2, t1, t2));
  }
  out[out.length - 1] = { x: p2.x, y: p2.y };
  return out;
}

/** The sampled path of one edge (closed outline, or one run of an open line). */
export function edgePath(pts, edge, closed = true) {
  const n = pts.length;
  const at = (i) => pts[((i % n) + n) % n];
  const idx = edge.idx;
  const out = [{ x: pts[idx[0]].x, y: pts[idx[0]].y }];
  for (let k = 0; k + 1 < idx.length; k++) {
    const p1 = pts[idx[k]], p2 = pts[idx[k + 1]];
    const curved = idx.length > 2 && (p1.c || p2.c || edge.smooth);
    if (!curved) { out.push({ x: p2.x, y: p2.y }); continue; }
    // neighbours inside the edge; at a corner end, reflect (a free end: the curve leaves the corner pointing at the next point)
    let p0, p3;
    if (k > 0) p0 = pts[idx[k - 1]];
    else if (edge.smooth && closed) p0 = at(idx[0] - 1);
    else p0 = { x: 2 * p1.x - p2.x, y: 2 * p1.y - p2.y };
    if (k + 2 < idx.length) p3 = pts[idx[k + 2]];
    else if (edge.smooth && closed) p3 = at(idx[k + 1] + 1);
    else p3 = { x: 2 * p2.x - p1.x, y: 2 * p2.y - p1.y };
    out.push(...crSpan(p0, p1, p2, p3, STEPS));
  }
  return out;
}

export function length(path) {
  let L = 0;
  for (let i = 1; i < path.length; i++) L += dst(path[i - 1], path[i]);
  return L;
}

export function cumulative(path) {
  const c = [0];
  for (let i = 1; i < path.length; i++) c.push(c[i - 1] + dst(path[i - 1], path[i]));
  return c;
}

/** The point at distance d along a path (clamped), with the unit tangent there. */
export function pointAt(path, d, cum = cumulative(path)) {
  if (path.length < 2) return { x: path[0]?.x ?? 0, y: path[0]?.y ?? 0, tx: 1, ty: 0, i: 0 };
  const L = cum[cum.length - 1];
  const t = Math.min(Math.max(d, 0), L);
  let i = 1;
  while (i < cum.length - 1 && cum[i] < t) i++;
  const a = path[i - 1], b = path[i];
  const seg = cum[i] - cum[i - 1];
  const k = seg > 1e-12 ? (t - cum[i - 1]) / seg : 0;
  const len = Math.max(dst(a, b), 1e-12);
  return { x: a.x + (b.x - a.x) * k, y: a.y + (b.y - a.y) * k, tx: (b.x - a.x) / len, ty: (b.y - a.y) / len, i: i - 1 };
}

/** The nearest point of a path to p: its distance along the path and from p. */
export function nearest(path, p) {
  let best = { d: 0, dist: Infinity, x: path[0]?.x ?? 0, y: path[0]?.y ?? 0, i: 0 };
  let run = 0;
  for (let i = 1; i < path.length; i++) {
    const a = path[i - 1], b = path[i];
    const v = sub(b, a), L2 = v.x * v.x + v.y * v.y;
    const k = L2 > 1e-18 ? Math.min(1, Math.max(0, ((p.x - a.x) * v.x + (p.y - a.y) * v.y) / L2)) : 0;
    const q = { x: a.x + v.x * k, y: a.y + v.y * k };
    const dd = dst(p, q);
    if (dd < best.dist) best = { d: run + Math.sqrt(L2) * k, dist: dd, x: q.x, y: q.y, i: i - 1 };
    run += Math.sqrt(L2);
  }
  return best;
}

/** Signed area (counter-clockwise positive) of a closed path. */
export function area(path) {
  let a = 0;
  for (let i = 0, n = path.length; i < n; i++) { const p = path[i], q = path[(i + 1) % n]; a += p.x * q.y - q.x * p.y; }
  return a / 2;
}

export function centroid(path) {
  let a = 0, cx = 0, cy = 0;
  for (let i = 0, n = path.length; i < n; i++) {
    const p = path[i], q = path[(i + 1) % n], k = p.x * q.y - q.x * p.y;
    a += k; cx += (p.x + q.x) * k; cy += (p.y + q.y) * k;
  }
  if (Math.abs(a) < 1e-12) { const b = bounds(path); return { x: (b.minX + b.maxX) / 2, y: (b.minY + b.maxY) / 2 }; }
  return { x: cx / (3 * a), y: cy / (3 * a) };
}

/** Where segments ab and cd cross: { x, y, s, t } (s along ab, t along cd, both 0…1 inside) | null when parallel. */
export function lineHit(a, b, c, d) {
  const r = sub(b, a), s = sub(d, c);
  const den = r.x * s.y - r.y * s.x;
  if (Math.abs(den) < 1e-14) return null;
  const q = sub(c, a);
  const u = (q.x * s.y - q.y * s.x) / den, v = (q.x * r.y - q.y * r.x) / den;
  return { x: a.x + r.x * u, y: a.y + r.y * u, s: u, t: v };
}

/** The same points, counter-clockwise (pieces are kept CCW so "outward" is always to the right of travel). */
export function orientCCW(pts) {
  if (pts.length < 3) return pts;
  const { path } = sampled(pts, true);
  if (area(path) >= 0) return pts;
  return [pts[0], ...pts.slice(1).reverse()];
}