Made of little things.

import type { Point, Sample } from './track.js';

function railNeighbors(rail: Point[]) {
  const cells = new Map<string, number[]>(),
    keys: string[][] = [];
  for (let i = 0; i < rail.length; i++) {
    const a = rail[i],
      b = rail[(i + 1) % rail.length];
    keys[i] = [];
    for (
      let x = Math.floor(Math.min(a.x, b.x) / 8);
      x <= Math.floor(Math.max(a.x, b.x) / 8);
      x++
    )
      for (
        let y = Math.floor(Math.min(a.y, b.y) / 8);
        y <= Math.floor(Math.max(a.y, b.y) / 8);
        y++
      ) {
        const key = `${x},${y}`,
          list = cells.get(key) ?? [];
        list.push(i);
        cells.set(key, list);
        keys[i].push(key);
      }
  }
  return (i: number) =>
    [...new Set(keys[i].flatMap((key) => cells.get(key)!))]
      .map((j) => i + ((j - i + rail.length) % rail.length))
      .filter((j) => j >= i + 2 && j < i + rail.length / 3)
      .sort((a, b) => a - b);
}

// Remove local loops in an offset boundary, then round the closed pocket.
// Distant branches (and overpasses) are deliberately separate road surfaces.
export function closeRail(samples: Sample[], side: number) {
  const n = samples.length - 1;
  const rail = samples.slice(0, -1).map((s) => ({
    x: s.x - ((s.ty * s.width) / 2) * side,
    y: s.y + ((s.tx * s.width) / 2) * side,
    z: s.z,
  }));
  const at = (i: number) => rail[((i % n) + n) % n];
  const sm = (i: number) => samples[((i % n) + n) % n];
  const cross = (ax: number, ay: number, bx: number, by: number) =>
    ax * by - ay * bx;
  const sections = new Set<number>();
  let loops = 0;
  for (let pass = 0; pass < 4; pass++) {
    let changed = false;
    const neighbors = railNeighbors(rail);
    for (let i = 0; i < n; i++) {
      const a = at(i),
        b = at(i + 1);
      for (const j of neighbors(i)) {
        const arc =
          (sm(j).distance - sm(i).distance + samples[n].distance) %
          samples[n].distance;
        if (arc > Math.max(sm(i).width, sm(j).width) * 4 + 12) continue;
        const c = at(j),
          d = at(j + 1),
          dx = b.x - a.x,
          dy = b.y - a.y,
          ex = d.x - c.x,
          ey = d.y - c.y;
        const det = cross(dx, dy, ex, ey);
        if (Math.abs(det) < 1e-8) continue;
        const t = cross(c.x - a.x, c.y - a.y, ex, ey) / det,
          u = cross(c.x - a.x, c.y - a.y, dx, dy) / det;
        if (t < 0 || t > 1 || u < 0 || u > 1) continue;
        const p = {
          x: a.x + t * dx,
          y: a.y + t * dy,
          z: (a.z + t * (b.z - a.z) + c.z + u * (d.z - c.z)) / 2,
        };
        if (Math.abs(a.z + t * (b.z - a.z) - c.z - u * (d.z - c.z)) > 8)
          continue;
        let lo = i,
          hi = j + 1;
        const radius = Math.max(2, sm(i).wallThickness * 3, sm(i).width * 0.55);
        for (
          let k = 0;
          k < 60 && Math.hypot(at(lo).x - p.x, at(lo).y - p.y) < radius;
          k++
        )
          lo--;
        for (
          let k = 0;
          k < 60 && Math.hypot(at(hi).x - p.x, at(hi).y - p.y) < radius;
          k++
        )
          hi++;
        const start = at(lo),
          end = at(hi);
        let distance = 0;
        const ds = [0];
        for (let k = lo + 1; k <= hi; k++) {
          distance += Math.hypot(sm(k).x - sm(k - 1).x, sm(k).y - sm(k - 1).y);
          ds.push(distance);
        }
        for (let k = lo + 1; k < hi; k++) {
          const f = ds[k - lo] / distance;
          sections.add(sm(k).section);
          rail[((k % n) + n) % n] = {
            x: (1 - f) ** 2 * start.x + 2 * f * (1 - f) * p.x + f * f * end.x,
            y: (1 - f) ** 2 * start.y + 2 * f * (1 - f) * p.y + f * f * end.y,
            z: (1 - f) * start.z + f * end.z,
          };
        }
        loops++;
        changed = true;
        i = Math.min(n - 1, hi);
        break;
      }
    }
    if (!changed) break;
  }

  // Near-cusps can reverse without producing a complete loop when width changes.
  for (let pass = 0; pass < 3; pass++)
    for (let i = 0; i < n; i++) {
      const a = at(i),
        b = at(i + 1),
        sa = sm(i),
        sb = sm(i + 1);
      const wallPoint = (k: number, d: number): Point => {
        const prev = at(k - 1),
          next = at(k + 1),
          length = Math.hypot(next.x - prev.x, next.y - prev.y) || 1;
        return {
          x: at(k).x - ((next.y - prev.y) / length) * d,
          y: at(k).y + ((next.x - prev.x) / length) * d,
          z: 0,
        };
      };
      const half = Math.max(sa.wallThickness, sm(i - 1).wallThickness) / 2;
      const w0 = wallPoint(i, -half),
        w1 = wallPoint(i + 1, -half),
        w2 = wallPoint(i + 1, half),
        w3 = wallPoint(i, half);
      const area = (a: Point, b: Point, c: Point) =>
        cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);
      const wallFold = area(w0, w1, w2) * area(w0, w2, w3) < -1e-10;
      if (
        !wallFold &&
        (b.x - a.x) * (sb.x - sa.x) + (b.y - a.y) * (sb.y - sa.y) >= -1e-7
      )
        continue;
      let lo = i,
        hi = i + 1,
        d = 0;
      const reach = Math.max(3, sa.width * 0.7);
      while (d < reach && i - lo < n / 10) {
        d += Math.hypot(sm(lo).x - sm(lo - 1).x, sm(lo).y - sm(lo - 1).y);
        lo--;
      }
      d = 0;
      while (d < reach && hi - i < n / 10) {
        d += Math.hypot(sm(hi + 1).x - sm(hi).x, sm(hi + 1).y - sm(hi).y);
        hi++;
      }
      const A = at(lo),
        B = at(hi),
        prev = at(lo - 1),
        next = at(hi + 1),
        l = Math.hypot(B.x - A.x, B.y - A.y) / 3;
      const al = Math.hypot(A.x - prev.x, A.y - prev.y) || 1,
        bl = Math.hypot(next.x - B.x, next.y - B.y) || 1;
      const C = {
          x: A.x + ((A.x - prev.x) * l) / al,
          y: A.y + ((A.y - prev.y) * l) / al,
        },
        D = {
          x: B.x - ((next.x - B.x) * l) / bl,
          y: B.y - ((next.y - B.y) * l) / bl,
        };
      for (let k = lo + 1; k < hi; k++) {
        const f = (k - lo) / (hi - lo),
          g = 1 - f;
        sections.add(sm(k).section);
        rail[((k % n) + n) % n] = {
          x:
            g * g * g * A.x +
            3 * g * g * f * C.x +
            3 * g * f * f * D.x +
            f * f * f * B.x,
          y:
            g * g * g * A.y +
            3 * g * g * f * C.y +
            3 * g * f * f * D.y +
            f * f * f * B.y,
          z: g * A.z + f * B.z,
        };
      }
      loops++;
      i = Math.min(n - 1, hi);
    }
  return { rail, loops, sections };
}
type Triangle = {
  a: Point;
  dx: number;
  dy: number;
  ex: number;
  ey: number;
  det: number;
  gx: number;
  gy: number;
};
export class RoadDeck {
  private cells = new Map<string, Triangle[]>();
  constructor(samples: Sample[]) {
    const triangle = (a: Point, b: Point, c: Point) => {
      const dx = b.x - a.x,
        dy = b.y - a.y,
        ex = c.x - a.x,
        ey = c.y - a.y,
        det = dx * ey - dy * ex;
      if (Math.abs(det) < 1e-9) return;
      const t = {
        a,
        dx,
        dy,
        ex,
        ey,
        det,
        gx: ((b.z - a.z) * ey - dy * (c.z - a.z)) / det,
        gy: (dx * (c.z - a.z) - (b.z - a.z) * ex) / det,
      };
      for (
        let x = Math.floor(Math.min(a.x, b.x, c.x) / 8);
        x <= Math.floor(Math.max(a.x, b.x, c.x) / 8);
        x++
      )
        for (
          let y = Math.floor(Math.min(a.y, b.y, c.y) / 8);
          y <= Math.floor(Math.max(a.y, b.y, c.y) / 8);
          y++
        ) {
          const key = `${x},${y}`,
            list = this.cells.get(key) ?? [];
          list.push(t);
          this.cells.set(key, list);
        }
    };
    for (let i = 0; i < samples.length - 1; i++) {
      const a = samples[i],
        b = samples[i + 1];
      triangle(a.rightEdge, b.rightEdge, b.leftEdge);
      triangle(a.rightEdge, b.leftEdge, a.leftEdge);
    }
  }
  at(x: number, y: number, z: number) {
    let best: { z: number; gx: number; gy: number } | null = null,
      distance = Infinity;
    for (const t of this.cells.get(
      `${Math.floor(x / 8)},${Math.floor(y / 8)}`,
    ) ?? []) {
      const px = x - t.a.x,
        py = y - t.a.y;
      const u = (px * t.ey - py * t.ex) / t.det,
        v = (t.dx * py - t.dy * px) / t.det;
      if (u < -1e-8 || v < -1e-8 || u + v > 1 + 1e-8) continue;
      const height = t.a.z + px * t.gx + py * t.gy,
        d = Math.abs(z - height);
      if (d < distance) {
        distance = d;
        best = { z: height, gx: t.gx, gy: t.gy };
      }
    }
    return best;
  }
}