1// The geohash cell system: recursive halving of the map's surface in world2// pixels, 32 children to a cell, addresses that refine by appending a3// character. It divides any map at all, because it never asks what the4// picture is of -- which is why it was the first system and why its math5// moved here VERBATIM: the parity harness compares its floats and strings6// byte for byte, and nothing about the extraction may move them.7import { geohashAlphabet, geohashMaxDepth, palette } from "../constants.js";89import { surfaceExtent } from "./index.js";1011// bbox is the recursive halving itself, unchanged from the original12// geohashExtent: alternate axes, five bits to a character.13function bbox(hash) {14 const extent = [...surfaceExtent()];15 let splitX = true;16 for (const character of hash) {17 const value = geohashAlphabet.indexOf(character);18 if (value < 0) continue;19 for (const mask of [16, 8, 4, 2, 1]) {20 if (splitX) {21 const middle = (extent[0] + extent[2]) / 2;22 if (value & mask) extent[0] = middle;23 else extent[2] = middle;24 } else {25 const middle = (extent[1] + extent[3]) / 2;26 if (value & mask) extent[1] = middle;27 else extent[3] = middle;28 }29 splitX = !splitX;30 }31 }32 return extent;33}3435// cellAt is the reverse of bbox: the same halvings, choosing at each one36// the side the point is on. Computed when asked rather than stored,37// because the grid divides the ground a lens covers and a split world38// gives each layer its own -- a hash stored beside a location could only39// be right for one.40function cellAt(coordinate, depth) {41 const extent = [...surfaceExtent()];42 const [x, y] = coordinate;43 if (x < extent[0] || x > extent[2] || y < extent[1] || y > extent[3]) return "";44 let splitX = true;45 let hash = "";46 for (let level = 0; level < depth; level++) {47 let value = 0;48 for (const mask of [16, 8, 4, 2, 1]) {49 if (splitX) {50 const middle = (extent[0] + extent[2]) / 2;51 if (x >= middle) {52 value |= mask;53 extent[0] = middle;54 } else {55 extent[2] = middle;56 }57 } else {58 const middle = (extent[1] + extent[3]) / 2;59 if (y >= middle) {60 value |= mask;61 extent[1] = middle;62 } else {63 extent[3] = middle;64 }65 }66 splitX = !splitX;67 }68 hash += geohashAlphabet[value];69 }70 return hash;71}7273let memo = { key: null, extent: null };7475function containsBox(id) {76 const surface = surfaceExtent();77 const key = `${surface.join(",")}|${id}`;78 if (memo.key !== key) memo = { key, extent: bbox(id) };79 return memo.extent;80}8182export const geohashSystem = {83 slug: "geohash",84 name: "Geohash",85 short: "G",8687 appliesTo() {88 return true;89 },9091 maxLevel() {92 return geohashMaxDepth;93 },9495 inputLength() {96 return geohashMaxDepth;97 },9899 level(id) {100 return id.length;101 },102103 parent(id) {104 return id.slice(0, -1);105 },106107 children(id) {108 return [...geohashAlphabet].map((character) => id + character);109 },110111 childIndex(id) {112 return Math.max(0, geohashAlphabet.indexOf(id[id.length - 1]));113 },114115 contains(id, coordinate) {116 // Callers sweep thousands of pins against one cell at a time, so the117 // last cell's box is remembered rather than re-halved per pin. The118 // memo keys on the surface too: a lens switch moves every box.119 const extent = containsBox(id);120 const [x, y] = coordinate;121 return x >= extent[0] && x <= extent[2] && y >= extent[1] && y <= extent[3];122 },123124 descendTarget(id, coordinate) {125 return cellAt(coordinate, id.length + 1);126 },127128 bbox,129130 center(id) {131 const extent = bbox(id);132 return [(extent[0] + extent[2]) / 2, (extent[1] + extent[3]) / 2];133 },134135 ring(id) {136 const [minimumX, minimumY, maximumX, maximumY] = bbox(id);137 return [138 [minimumX, minimumY],139 [minimumX, maximumY],140 [maximumX, maximumY],141 [maximumX, minimumY],142 [minimumX, minimumY],143 ];144 },145146 poleContained() {147 return null;148 },149150 label(id) {151 return { context: id.slice(0, -1), principal: id.slice(-1) };152 },153154 colorKey(id) {155 return Math.max(0, geohashAlphabet.indexOf(id[id.length - 1])) % palette.length;156 },157158 normalizeInput(text) {159 return [...text.toLocaleLowerCase()]160 .filter((character) => geohashAlphabet.includes(character))161 .slice(0, geohashMaxDepth)162 .join("");163 },164165 // Every normalized spelling is a place -- the empty string is the root166 // -- so parsing never refuses.167 parseInput(text) {168 return text;169 },170171 locate(coordinate) {172 const value = cellAt(coordinate, geohashMaxDepth);173 return value ? { label: "Geohash", value } : null;174 },175};176177// cellAtDepth serves the one caller that names a depth of its own: the178// pin card's fixed-depth address, independent of where the grid stands.179export function geohashCellAt(coordinate, depth = geohashMaxDepth) {180 return cellAt(coordinate, depth);181}