/**
 * Contour extraction by marching squares.
 *
 * Given a scalar field and a threshold, walk every cell of the grid and emit
 * the line segments where the surface crosses that level. Chain those segments
 * into continuous polylines so the result can be drawn as strokes rather than
 * as a scatter of disconnected ticks — the chaining is what makes the output a
 * DRAWING instead of a dashed approximation of one.
 *
 * Pure. This is the piece that converts a measurement into a line.
 */

/** Linear crossing position between two corner values. */
function lerp(threshold, a, b) {
  const d = b - a;
  // A flat edge has no defined crossing; put it at the midpoint rather than
  // dividing by zero and emitting a coordinate of Infinity.
  return Math.abs(d) < 1e-12 ? 0.5 : (threshold - a) / d;
}

/**
 * Extract contour segments at one level.
 *
 * @param {{data: Float32Array, width: number, height: number}} field
 * @param {number} threshold
 * @returns {number[][]} Segments as [x1, y1, x2, y2] in grid coordinates.
 */
export function marchingSquares(field, threshold) {
  const { data, width, height } = field;
  const segments = [];
  const at = (x, y) => data[y * width + x];

  for (let y = 0; y < height - 1; y += 1) {
    for (let x = 0; x < width - 1; x += 1) {
      const tl = at(x, y);
      const tr = at(x + 1, y);
      const br = at(x + 1, y + 1);
      const bl = at(x, y + 1);

      let idx = 0;
      if (tl > threshold) idx |= 8;
      if (tr > threshold) idx |= 4;
      if (br > threshold) idx |= 2;
      if (bl > threshold) idx |= 1;
      if (idx === 0 || idx === 15) continue;

      // Crossing points on each edge, in grid coordinates.
      const top = [x + lerp(threshold, tl, tr), y];
      const right = [x + 1, y + lerp(threshold, tr, br)];
      const bottom = [x + lerp(threshold, bl, br), y + 1];
      const left = [x, y + lerp(threshold, tl, bl)];

      const push = (a, b) => segments.push([a[0], a[1], b[0], b[1]]);

      switch (idx) {
        case 1: case 14: push(left, bottom); break;
        case 2: case 13: push(bottom, right); break;
        case 3: case 12: push(left, right); break;
        case 4: case 11: push(top, right); break;
        case 6: case 9:  push(top, bottom); break;
        case 7: case 8:  push(left, top); break;

        // Saddles. Both diagonal corners are on the same side of the threshold,
        // so the cell can be resolved two ways. Disambiguate with the average of
        // the four corners — the standard fix. Choosing arbitrarily produces
        // contours that cross themselves, which looks like a rendering bug.
        case 5: {
          const centre = (tl + tr + br + bl) / 4;
          if (centre > threshold) { push(left, top); push(bottom, right); }
          else { push(left, bottom); push(top, right); }
          break;
        }
        case 10: {
          const centre = (tl + tr + br + bl) / 4;
          if (centre > threshold) { push(top, right); push(left, bottom); }
          else { push(top, left); push(right, bottom); }
          break;
        }
        default: break;
      }
    }
  }
  return segments;
}

/**
 * Chain segments into continuous polylines.
 *
 * Marching squares emits segments in scan order, not in path order. Drawing
 * them as-is gives a field of unconnected ticks. Joining endpoints turns them
 * into the long, continuous lines that read as a contour drawn by hand.
 *
 * @param {number[][]} segments
 * @param {number} [tol]  How close two endpoints must be to count as the same.
 * @returns {number[][][]} Polylines as arrays of [x, y].
 */
export function chain(segments, tol = 1e-6) {
  // Spatial hash on quantised endpoints: O(n) rather than O(n^2) pairwise.
  const key = (x, y) => `${Math.round(x / tol)},${Math.round(y / tol)}`;
  const ends = new Map();

  segments.forEach((s, i) => {
    for (const k of [key(s[0], s[1]), key(s[2], s[3])]) {
      if (!ends.has(k)) ends.set(k, []);
      ends.get(k).push(i);
    }
  });

  const used = new Uint8Array(segments.length);
  const paths = [];

  for (let i = 0; i < segments.length; i += 1) {
    if (used[i]) continue;
    used[i] = 1;
    const s = segments[i];
    const path = [[s[0], s[1]], [s[2], s[3]]];

    // Extend from both ends until nothing connects.
    for (const forward of [true, false]) {
      for (;;) {
        const tip = forward ? path[path.length - 1] : path[0];
        const candidates = ends.get(key(tip[0], tip[1])) ?? [];
        const next = candidates.find((j) => !used[j]);
        if (next === undefined) break;
        used[next] = 1;
        const t = segments[next];
        const head = Math.abs(t[0] - tip[0]) < tol && Math.abs(t[1] - tip[1]) < tol;
        const point = head ? [t[2], t[3]] : [t[0], t[1]];
        if (forward) path.push(point); else path.unshift(point);
      }
    }

    // Two-segment stubs are marching-squares noise at the field's edge, not
    // structure. Dropping them keeps the drawing clean.
    if (path.length > 2) paths.push(path);
  }

  return paths;
}

/**
 * Extract a full set of nested contours.
 *
 * @param {{data: Float32Array, width: number, height: number, min: number, max: number}} field
 * @param {number} levels  How many contour lines.
 * @param {number} [floor] Fraction of the range to start at; below this the
 *                         terrain is flat and the contours are just noise.
 * @returns {Array<{level: number, t: number, paths: number[][][]}>}
 */
export function contours(field, levels, floor = 0.06) {
  const out = [];
  const range = field.max - field.min;
  for (let i = 0; i < levels; i += 1) {
    // Distribute levels with a slight bias toward the low end, where the
    // interesting silhouette of the landmass lives; evenly spaced levels put
    // most of the lines inside the peaks where they read as clutter.
    const t = floor + (1 - floor) * ((i + 1) / (levels + 1)) ** 1.35;
    const level = field.min + range * t;
    const paths = chain(marchingSquares(field, level));
    if (paths.length) out.push({ level, t, paths });
  }
  return out;
}