1// The S2 cell system: the sphere divided by the six faces of a cube projected2// onto it, each face a quadtree of exactly-nested quadrilateral cells3// addressed by Hilbert-curve tokens.4//5// It is the proof the contract holds nothing geohash-shaped. Identities do not6// refine by appending characters — the children of 47a1cb are 47a1ca4 and its7// siblings. Cells have edges that are straight on neither projection. And an8// address only means something on a ground that declares what its picture is9// of, so this is the system that can refuse a ground.10//11// The spherical math is s2js's — the Go library ported, test vectors and all,12// and the one third-party dependency this lane keeps (issue #5 §9's pinned13// surface). This file only bridges it to world pixels through the ground's14// declared flattening.1516import { s2 } from "s2js";1718import type { CellID, CellLabel, GroundedCellSystem, LocatedCell, Pole, Ring } from "./contract.ts";19import type { CellSystem } from "./contract.ts";20import type { Coordinate, Extent, Ground } from "./ground.ts";21import { surfaceExtent } from "./ground.ts";22import { palette } from "./tokens.ts";23import { geoMapping, worldSurface } from "../semconv/geometry.ts";24import type { GeoMapping, World } from "../semconv/geometry.ts";2526/**27 * The telescope stops at S2 level 10 — cells a few kilometres across on a28 * Mars-sized body, tokens six characters long — which is depth enough for a29 * couple of thousand pins and shallow enough that every level stays a place30 * rather than a coordinate.31 */32const deepestS2Level = 10;3334/**35 * Port levels count the root as 0 and the six faces as 1; S2 counts the faces36 * as level 0. The two bookkeepings meet here and nowhere else.37 */38const portLevel = (level: number): number => level + 1;3940const levelOfToken = (id: CellID): number => s2.cellid.level(s2.cellid.fromToken(id));4142/**43 * The mapping bridge, remembered per world: world pixels are only meaningful44 * through the flattening the ground declares, and reading it is parsing.45 */46const mappings = new WeakMap<World, GeoMapping | null>();4748function mappingOf(ground: Ground): GeoMapping | null {49 const world = ground.world;50 const held = mappings.get(world);51 if (held !== undefined) return held;52 const fresh = geoMapping(world);53 mappings.set(world, fresh);54 return fresh;55}5657/** Degrees from a point on the unit sphere. */58function degreesOf(point: s2.Point): readonly [number, number] {59 const ll = s2.LatLng.fromPoint(point);60 return [(ll.lat * 180) / Math.PI, (ll.lng * 180) / Math.PI];61}6263/**64 * The leaf cell under a coordinate, remembered against the mapping that65 * produced it: leaves are looked up per pin on every filter pass, and a66 * coordinate is a stable object for exactly as long as its pin is.67 */68const leaves = new WeakMap<object, { mapping: GeoMapping; leaf: bigint }>();6970function leafOf(ground: Ground, coordinate: Coordinate): bigint {71 const mapping = mappingOf(ground);72 if (!mapping) return 0n;73 const memo = leaves.get(coordinate);74 if (memo && memo.mapping === mapping) return memo.leaf;75 const [lat, lng] = mapping.toLatLng(coordinate[0], -coordinate[1]);76 const leaf = s2.cellid.fromLatLng(s2.LatLng.fromDegrees(lat, lng));77 leaves.set(coordinate, { mapping, leaf });78 return leaf;79}8081/**82 * The boundary as world pixels: the four geodesic edges, each walked in small83 * great-circle steps on the sphere itself, then unwrapped so a loop that84 * crossed the antimeridian stays continuous. The adapters wrap or split it,85 * each in its own way.86 */87function ringOf(ground: Ground, mapping: GeoMapping, id: CellID): Coordinate[] {88 const cellID = s2.cellid.fromToken(id);89 const cell = s2.Cell.fromCellID(cellID);90 const level = s2.cellid.level(cellID);91 const steps = Math.max(2, Math.min(16, 2 ** (4 - level) * 2));92 const surface = surfaceExtent(ground);93 const width = surface[2] - surface[0];94 const points: [number, number][] = [];95 for (let edge = 0; edge < 4; edge++) {96 const from = cell.vertex(edge).vector;97 const to = cell.vertex((edge + 1) % 4).vector;98 for (let step = 0; step < steps; step++) {99 const t = step / steps;100 const x = from.x + (to.x - from.x) * t;101 const y = from.y + (to.y - from.y) * t;102 const z = from.z + (to.z - from.z) * t;103 const norm = Math.hypot(x, y, z) || 1;104 const [lat, lng] = degreesOf(new s2.Point(x / norm, y / norm, z / norm));105 const [worldX, worldY] = mapping.toWorld(lat, lng);106 points.push([worldX, -worldY]);107 }108 }109 // Sequential unwrap: a jump of more than half the world is the seam, not110 // the ground.111 for (let at = 1; at < points.length; at++) {112 const current = points[at];113 const previous = points[at - 1];114 if (!current || !previous) continue;115 const delta = current[0] - previous[0];116 if (delta > width / 2) current[0] -= width;117 else if (delta < -width / 2) current[0] += width;118 }119 // The closing point joins the loop in the frame the walk ended in, not the120 // one it began in: a pole cell's loop accumulates a whole world of121 // longitude, and closing back to the original frame would hand the adapters122 // a segment sweeping the entire planet — a phantom edge the boundary draws123 // and the fill fans spokes to.124 const opening = points[0];125 const ending = points[points.length - 1];126 if (!opening || !ending) return points;127 const closing: [number, number] = [opening[0], opening[1]];128 const delta = closing[0] - ending[0];129 if (delta > width / 2) closing[0] -= width;130 else if (delta < -width / 2) closing[0] += width;131 points.push(closing);132 return points;133}134135/**136 * The mapping this ground declares, or a refusal. Every geometric method needs137 * it, and `appliesTo` is the question a caller was supposed to ask first.138 */139function requireMapping(ground: Ground): GeoMapping {140 const mapping = mappingOf(ground);141 if (!mapping) {142 throw new Error(143 "s2: this ground declares no invertible flattening — ask appliesTo(ground) first " +144 "(analysis/cellsystems, issue #5 §5.4)",145 );146 }147 return mapping;148}149150/** The surface as a rectangle: the root's own geometry, since the root is the ground. */151function surfaceRing(ground: Ground): Coordinate[] {152 const [minimumX, minimumY, maximumX, maximumY] = surfaceExtent(ground);153 return [154 [minimumX, minimumY],155 [minimumX, maximumY],156 [maximumX, maximumY],157 [maximumX, minimumY],158 [minimumX, minimumY],159 ];160}161162// The root is `""` in every system (contract.ts), and S2's token vocabulary163// has no spelling for it — `fromToken("")` answers a cell id that is not the164// sphere and not an error. Every method below that could be handed the root165// answers for the whole ground instead of asking s2js a question it cannot166// hear. None of these cases is reachable from a plan (the root is never a plan167// cell) which is why the oracle never had to have an answer; the contract says168// it should, so this one does. See docs/analysis.md, "the root cases".169170/** S2, bound to one ground. */171function grounded(ground: Ground): GroundedCellSystem {172 const system: GroundedCellSystem = {173 level(id: CellID): number {174 return id === "" ? 0 : portLevel(levelOfToken(id));175 },176177 parent(id: CellID): CellID {178 if (id === "") return "";179 const cellID = s2.cellid.fromToken(id);180 const level = s2.cellid.level(cellID);181 if (level === 0) return "";182 return s2.cellid.toToken(s2.cellid.parent(cellID, level - 1));183 },184185 children(id: CellID): CellID[] {186 if (id === "") {187 return [0, 1, 2, 3, 4, 5].map((face) => s2.cellid.toToken(s2.cellid.fromFace(face)));188 }189 return s2.cellid.children(s2.cellid.fromToken(id)).map(s2.cellid.toToken);190 },191192 childIndex(id: CellID): number {193 if (id === "") return 0;194 const cellID = s2.cellid.fromToken(id);195 const level = s2.cellid.level(cellID);196 return level === 0 ? s2.cellid.face(cellID) : s2.cellid.childPosition(cellID, level);197 },198199 // The root is the whole sphere: it holds every point the ground can name.200 contains(id: CellID, at: Coordinate): boolean {201 const leaf = leafOf(ground, at);202 if (id === "") return leaf !== 0n;203 return s2.cellid.contains(s2.cellid.fromToken(id), leaf);204 },205206 descendTarget(id: CellID, at: Coordinate): CellID {207 const leaf = leafOf(ground, at);208 if (leaf === 0n) return "";209 const target = id === "" ? 0 : levelOfToken(id) + 1;210 if (target > deepestS2Level) return "";211 return s2.cellid.toToken(s2.cellid.parent(leaf, target));212 },213214 // The root is the whole ground: six faces cover a sphere, and their union215 // in world pixels is the picture itself.216 bbox(id: CellID): Extent {217 if (id === "") return surfaceExtent(ground);218 let minimumX = Infinity;219 let minimumY = Infinity;220 let maximumX = -Infinity;221 let maximumY = -Infinity;222 for (const [x, y] of system.ring(id)) {223 minimumX = Math.min(minimumX, x);224 minimumY = Math.min(minimumY, y);225 maximumX = Math.max(maximumX, x);226 maximumY = Math.max(maximumY, y);227 }228 return [minimumX, minimumY, maximumX, maximumY];229 },230231 center(id: CellID): Coordinate {232 const mapping = requireMapping(ground);233 if (id === "") {234 const [minimumX, minimumY, maximumX, maximumY] = surfaceExtent(ground);235 return [(minimumX + maximumX) / 2, (minimumY + maximumY) / 2];236 }237 const [lat, lng] = degreesOf(s2.Cell.fromCellID(s2.cellid.fromToken(id)).center());238 const [x, y] = mapping.toWorld(lat, lng);239 return [x, -y];240 },241242 ring(id: CellID): Ring {243 const mapping = requireMapping(ground);244 if (id === "") return surfaceRing(ground);245 return ringOf(ground, mapping, id);246 },247248 // The root circles both poles, and no single answer says so; nothing asks,249 // because a pole closure is a question about a cell being drawn.250 poleContained(id: CellID): Pole | null {251 if (id === "") return null;252 const cellID = s2.cellid.fromToken(id);253 if (s2.cellid.contains(cellID, s2.cellid.fromLatLng(s2.LatLng.fromDegrees(90, 0)))) {254 return "north";255 }256 if (s2.cellid.contains(cellID, s2.cellid.fromLatLng(s2.LatLng.fromDegrees(-90, 0)))) {257 return "south";258 }259 return null;260 },261262 label(id: CellID): CellLabel {263 return { context: id.slice(0, -1), principal: id.slice(-1) };264 },265266 // Sibling tokens can share their final character, so the accent comes from267 // the sibling ordinal instead — neighbours always differ.268 colorKey(id: CellID): number {269 return system.childIndex(id) % palette.length;270 },271272 normalizeInput(text: string): string {273 return [...text.toLocaleLowerCase()]274 .filter((character) => "0123456789abcdef".includes(character))275 .slice(0, 6)276 .join("");277 },278279 // A partial token is not yet a place: the field holds the draft and the280 // session stays put until the address parses whole. A deeper token clamps281 // to the telescope's floor, re-tokenized so the spelling is canonical.282 parseInput(text: string): CellID | null {283 if (text === "") return "";284 const cellID = s2.cellid.fromToken(text);285 if (cellID === 0n || !s2.cellid.valid(cellID)) return null;286 const level = s2.cellid.level(cellID);287 if (level > deepestS2Level) {288 return s2.cellid.toToken(s2.cellid.parent(cellID, deepestS2Level));289 }290 return s2.cellid.toToken(cellID);291 },292293 locate(at: Coordinate): LocatedCell | null {294 const leaf = leafOf(ground, at);295 if (leaf === 0n) return null;296 return { label: "S2", value: s2.cellid.toToken(s2.cellid.parent(leaf, deepestS2Level)) };297 },298 };299 return system;300}301302export const s2System: CellSystem = {303 slug: "s2",304 name: "S2",305 short: "S2",306307 // Only a ground that declares what its picture is of — a sphere, through any308 // invertible flattening — can be divided geodesically.309 appliesTo(ground: Ground): boolean {310 return worldSurface(ground.world) === "sphere" && geoMapping(ground.world) !== null;311 },312313 maxLevel(): number {314 return portLevel(deepestS2Level);315 },316317 // A level-10 token is six characters; the field takes no more.318 inputLength(): number {319 return 6;320 },321322 on: grounded,323};