History/scripts/build-region-adjacency.mjs

/**
 * scripts/build-region-adjacency.mjs — build the precomputed region-adjacency
 * manifest: `public/region-adjacency.json` = `{ "<regionKey>": ["<neighbourKey>", ...], ... }`.
 *
 * For every sub-region (region key, see `public/region-keys.json`) this records
 * which *other* sub-regions it **borders** — i.e. shares an edge or a point with.
 * The result is the data behind the model's `getNeighbours` tool (P2 of #16):
 * given a set of region keys, the engine returns the union of their adjacency
 * entries (excluding the queried keys), so the LLM can plan *frontier-biased,
 * contiguous* territory transfers (a nation realistically gains/loses a region
 * it already abuts) instead of whole countries.
 *
 * Method — bounding-box-pruned polygon intersection (turf is allowed in .mjs
 * scripts; it is deliberately kept OUT of the TS typecheck program, see the
 * v0.17 note). For each unordered pair of regions (i < j) we first do a cheap
 * bbox-proximity reject with a small gap tolerance (adjacent regions' bboxes
 * touch, so their gap is ≈0), and only for the survivors do we run
 * `@turf/boolean-intersects`, which returns true exactly when the two
 * (Multi)Polygons share at least one point (edge or corner touch, or overlap).
 * A hit adds each key to the other's set — adjacency is recorded **symmetrically**
 * and **deduplicated** (a neighbour appears once even if the pair shares several
 * disjoint border segments).
 *
 * Output contract (asserted by scripts/region-adjacency.test.ts):
 *   - one entry for **every** region key (including regions with no bordering
 *     neighbours, e.g. isolated islands — their list is simply empty);
 *   - adjacency is symmetric (A ∈ B's list  ⟺  B ∈ A's list);
 *   - no key lists itself.
 *
 * Deterministic + idempotent: the input files are fixed, the intersection test
 * is a pure geometric computation, and the output is written with keys and
 * neighbour lists both sorted — so a re-run rewrites a byte-identical file.
 *
 * Usage: `node scripts/build-region-adjacency.mjs`  (or `npm run build:region-adjacency`).
 */
import { readFileSync, writeFileSync } from 'node:fs';
import path from 'node:path';
import { fileURLToPath } from 'node:url';
import bbox from '@turf/bbox';
import booleanIntersects from '@turf/boolean-intersects';
import { feature } from '@turf/helpers';

const here = path.dirname(fileURLToPath(import.meta.url));
const root = path.resolve(here, '..');

// "Close enough" bbox gap (degrees) for the cheap reject. Adjacent regions'
// bboxes touch (gap ≈ 0); a small tolerance absorbs 4-dp coordinate rounding
// and digitization fuzz. It only prunes work — it never affects correctness,
// because `booleanIntersects` is the final arbiter (a pair is a neighbour only
// if the polygons actually share a point).
const GAP_DEG = 0.05; // ≈ 5.5 km

// --- load the geo + region-key manifest (plain parse; keys join feature->key) --
const geo = JSON.parse(readFileSync(path.join(root, 'public', 'regions.geo.json'), 'utf8'));
const idToKey = JSON.parse(readFileSync(path.join(root, 'public', 'region-keys.json'), 'utf8'));

// Region records in stable file order, keyed by their region key.
const regions = [];
for (const f of geo.features ?? []) {
  const id = f.id == null ? '' : String(f.id);
  const key = idToKey[id];
  if (!key) continue; // a geo feature with no manifest entry is skipped
  regions.push({ key, feature: feature(f.geometry), bbox: bbox(f.geometry) });
}

if (regions.length === 0) {
  throw new Error('no regions with valid region keys — check regions.geo.json / region-keys.json');
}

// bboxes are flat [minX, minY, maxX, maxY] (turf's BBox type).
function bboxesClose(a, b) {
  return (
    a[0] <= b[2] + GAP_DEG && // a.w <= b.e + gap
    b[0] <= a[2] + GAP_DEG && // b.w <= a.e + gap
    a[1] <= b[3] + GAP_DEG && // a.s <= b.n + gap
    b[1] <= a[3] + GAP_DEG // b.s <= a.n + gap
  );
}

// key -> set of neighbouring keys (deduped; a pair sharing several segments is
// recorded once).
const adj = new Map();
for (const r of regions) adj.set(r.key, new Set());

let pairChecks = 0;
let intersections = 0;
for (let i = 0; i < regions.length; i++) {
  for (let j = i + 1; j < regions.length; j++) {
    if (!bboxesClose(regions[i].bbox, regions[j].bbox)) continue; // cheap reject
    pairChecks++;
    let touches = false;
    try {
      touches = booleanIntersects(regions[i].feature, regions[j].feature);
    } catch {
      touches = false; // a degenerate geometry pair is treated as non-adjacent
    }
    if (touches) {
      intersections++;
      adj.get(regions[i].key).add(regions[j].key);
      adj.get(regions[j].key).add(regions[i].key);
    }
  }
}

// --- write idempotently: keys sorted, neighbour lists sorted ------------------
// Every region key gets an entry (an isolated island's list is simply empty).
const manifest = {};
for (const key of [...adj.keys()].sort()) {
  manifest[key] = [...adj.get(key)].sort();
}

// Self-reference guard (can't happen — we only ever add the *other* region — but
// assert it so a future regression is loud rather than silent).
for (const [k, list] of Object.entries(manifest)) {
  if (list.includes(k)) throw new Error(`region ${k} lists itself as a neighbour`);
}

writeFileSync(path.join(root, 'public', 'region-adjacency.json'), JSON.stringify(manifest, null, 2) + '\n');

// --- summary ------------------------------------------------------------------
const totalEntries = Object.values(manifest).reduce((n, l) => n + l.length, 0);
const withNeighbours = Object.values(manifest).filter((l) => l.length > 0).length;
const maxDegree = Math.max(0, ...Object.values(manifest).map((l) => l.length));
console.log(
  `[build-region-adjacency] wrote public/region-adjacency.json — ${Object.keys(manifest).length} region keys, ` +
    `${totalEntries / 2} border pairs (${totalEntries} directed entries), max degree ${maxDegree}, ` +
    `${withNeighbours} with ≥1 neighbour (${pairChecks} bbox-close pairs tested, ${intersections} intersect)`,
);
// A couple of human-checkable examples (highest-degree regions, stable order).
const byDegree = Object.entries(manifest).sort((a, b) => b[1].length - a[1].length || a[0].localeCompare(b[0]));
for (const [k, list] of byDegree.slice(0, 3)) {
  console.log(`  e.g. ${k} (deg ${list.length}) → ${list.slice(0, 4).join(', ')}${list.length > 4 ? ', …' : ''}`);
}