1// Package cells is the cell-system arithmetic the *server* needs: enough of2// every system a session can hold to answer two questions without asking the3// seam.4package cells56import (7 "strings"89 "github.com/FelineStateMachine/atlas/format/semconv"10)1112// THE FIRST QUESTION is the held cell's: is this feature inside it.13//14// A grid narrows what stands the same way a highlight does (docs/render-seam.md15// §4.2, rule 4), and the count above the panel beside the map has to be the16// count of what the map is drawing — which means the application has to be able17// to answer it for *every* system, not merely for the first one. A package that18// answers for geohash and says "no cell" for the rest is worse than one that19// answers for neither: the seam narrows the drawn set, the server narrows20// nothing, and the map, the footer and the dock stop agreeing while every one21// of them believes it is right.22//23// THE SECOND QUESTION is the world's: which systems divide it at all. Geohash24// divides anything, because it never asks what the picture is of. S2 asks, and25// refuses a ground that cannot say (analysis/cellsystems/s2.ts, `appliesTo`).26// The navigator offers only the systems that answer yes, so a system value27// arriving on a request means nothing except against a world — which is what28// [ApplicableSystems] answers and what the session spends it on.29//30// THE THIRD QUESTION arrived with the second system, and it is the reader's: I31// am standing here, now divide it that way instead. Cycling the navigator32// carries the held place across (carry.go, [Equivalent]), and the *record* has33// to name the cell that lands, because the record is what the first question34// is asked of. A crossing the seam made alone would be a cell the server never35// heard of, and the first question would start answering about a cell nobody36// is holding.37//38// WHY THIS IS HERE AND NOT IN THE ANALYSIS LANE. Cell systems belong to39// `analysis/cellsystems` (issue #5 §5.4) and that lane is TypeScript, consumed40// by the seam. The seam is deletable and the application is not, so a fact the41// *server* needs cannot live behind it: the alternative to this file is a42// third upward flow from the seam carrying the cell's extent, which43// docs/render-seam.md §5 forbids in as many words.44//45// TWO SYSTEMS, TWO PROVENANCES. The geohash halving here is a second copy of46// an arithmetic, and that is a cost rather than a design: it is kept to the47// smallest piece of it the three questions need — the halving, the same48// halving run backward, and nothing else. No plan, no style token, no pole49// closure, none of which the server has any use for. S2 is not a copy at all.50// Its spherical math is github.com/golang/geo/s2, the canonical Google51// library; the seam's s2js is that library ported, test vectors and all. The52// two lanes agree because they are the same arithmetic, not because two53// authors read the same paper, and what is written here is only the bridge54// from world pixels to the sphere, the port's own level bookkeeping, and the55// one measurement the third question needs: a cell's rectangle *as drawn*,56// which is an edge walk rather than a spherical area and says why at57// [S2Extent].58//59// AND IT IS GATED. `tests/cells` holds the geohash halving, the S2 side, the60// surface ladder, the carry and the applicable-systems answer to the shared61// contract vectors in `analysis/testdata/cells` — the same language-neutral62// oracle the TypeScript lane answers in analysis/test/vectors.test.ts. The63// hand-derived edge cases live beside this file (predicate_test.go), pure64// tables because nothing under internal/app may read a file. When a Go twin65// of the analysis lane exists, this package is the first thing it deletes.66//67// COORDINATES. Everything exported here speaks world pixels in the orientation68// the application's own projection produces: x east, y **negative-down**69// (internal/app/world.go, tileGrid.project), which is the space a pin's70// position lives in and the space the seam's cell systems work in. A declared71// flattening reads the other way round — y down from the top of the raster72// window (format/semconv, [semconv.Equirect.Invert]) — and the sign is flipped73// at that one call, which is exactly where analysis/semconv/geometry.ts says74// the two conventions meet.7576// The systems this package divides by, named in the order the navigator offers77// them (analysis/cellsystems/registry.ts): geohash first because it divides78// anything, S2 second because it asks the ground a question.79const (80 SystemGeohash = "geohash"81 SystemS2 = "s2"82)8384// Held is the held cell as a question rather than as a shape: does this cell85// hold the point at these world pixels.86//87// A predicate rather than a rectangle because only one of the two systems has88// a rectangle. A geohash cell is axis-aligned in world pixels and answers by89// comparing four numbers; an S2 cell is a spherical quadrilateral whose edges90// are straight on no projection, and the only honest way to ask it is to put91// the point back on the sphere. The seam's own test is the same shape92// (`cellTest` in render/chart/grid.ts: `(at) => on.contains(cell, at)`), which93// is what makes the two sides comparable at all.94//95// A nil Held is no narrowing: no grid, or no cell held inside it.96type Held func(x, y float64) bool9798// ApplicableSystems answers which systems will divide a world, in the99// navigator's order. It is the server's half of the seam's100// `applicableSystems(ground)`, and it is deliberately the same two questions101// in the same order: S2 wants a surface that says it is a sphere and a102// flattening that can be inverted, and geohash wants nothing.103//104// The attributes are the world's own (`atlas.geometry.*`, format/semconv).105// Only the lens-shaped half of a seam `Ground` is missing from that, and106// neither question reads it — which is why this takes attributes rather than107// a ground.108//109// ONE PROJECTION, FOR NOW. The seam accepts any invertible flattening it can110// read, which today means equirectangular or Web-Mercator. The registry knows111// one projection value (`equirect`, format/semconv), so a Mercator world112// cannot pass bundle validation and cannot reach this function; when the113// vocabulary grows the second value, this is where it lands, alongside the114// mapping reader in s2.go.115func ApplicableSystems(attrs map[string]string) []string {116 out := []string{SystemGeohash}117 if Applicable(attrs, SystemS2) {118 out = append(out, SystemS2)119 }120 return out121}122123// Applicable answers whether one system divides this world. It is the whole124// of the session's system-value validation: a value that is not a system, or125// is a system this world refuses, is not a place a reader can be standing.126func Applicable(attrs map[string]string, system string) bool {127 switch system {128 case SystemGeohash:129 return true130 case SystemS2:131 if attrs[semconv.KeyGeometrySurface] != semconv.SurfaceSphere {132 return false133 }134 _, mapped := MappingOf(attrs)135 return mapped136 }137 return false138}139140// GeohashAlphabet is the canonical order, which is also the child order. No141// `a`, `i`, `l` or `o`, so a hash read aloud cannot be misheard.142const GeohashAlphabet = "0123456789bcdefghjkmnpqrstuvwxyz"143144// GeohashMaxDepth is where the geohash telescope stops: three characters,145// fifteen halvings, a cell a few world pixels across on an 8192 square. It is146// the seam's floor (analysis/cellsystems/geohash.ts) and the length the147// navigator's field accepts, which is why a request carrying more than this148// is clamped rather than refused.149const GeohashMaxDepth = 3150151// Masks are the five bits of one character, most significant first.152var Masks = [5]int{16, 8, 4, 2, 1}153154// extent is a rectangle of world pixels: minimum x, minimum y, maximum x,155// maximum y, in the coordinates everything downstream of the projection156// speaks (y decreasing downward).157// Extent is a rectangle of world pixels.158type Extent struct{ MinX, MinY, MaxX, MaxY float64 }159160// Holds answers whether a point is inside.161func (e Extent) Holds(x, y float64) bool {162 return x >= e.MinX && x <= e.MaxX && y >= e.MinY && y <= e.MaxY163}164165// surfaceExtent is the ground a system divides: the lens's declared surface166// where it has one, its raster window otherwise, and the whole world square167// where it declares neither.168//169// The distinction is the split sheet's: `bounds` is the window the pyramid170// fills and `surface` is the ground that window pictures, which is smaller171// wherever the window was grown to take in a title drawn beside the map.172// Anything *dividing* the world measures the ground.173func SurfaceExtent(surface, bounds *Rect, size float64) Extent {174 if surface != nil {175 return Extent{surface.X, -(surface.Y + surface.Height), surface.X + surface.Width, -surface.Y}176 }177 if bounds != nil {178 return Extent{bounds.X, -(bounds.Y + bounds.Height), bounds.X + bounds.Width, -bounds.Y}179 }180 return Extent{0, -size, size, 0}181}182183// GeohashGround is the ground GEOHASH divides, which is not always184// [SurfaceExtent]: a game map's grid must cover the full map area and stay185// put across lens switches, and two lenses of one world may declare186// different surfaces. So on a PLANE with no earth anchoring, geohash divides187// the whole world square `[0, -size, size, 0]` whenever the volume declares188// one, and only a ground with no volume at all falls back to the surface189// ladder. Spheres keep the ladder — their surface is the body's own picture —190// and every other consumer of [SurfaceExtent] (S2, the grid's own ground191// question) keeps it too. An earth-anchored plane never reaches this: its192// geohash is the real one ([EarthMercator], [GeohashRealHeld]) and divides193// no rectangle of pixels at all.194//195// It is the seam's `geohashExtent` (analysis/cellsystems/geohash.ts), and the196// shared vectors hold the two to one set of numbers.197func GeohashGround(surface, bounds *Rect, size float64, attrs map[string]string) Extent {198 if size > 0 && planeSurface(attrs) {199 if _, anchored := EarthMercator(attrs); !anchored {200 return Extent{MinX: 0, MinY: -size, MaxX: size, MaxY: 0}201 }202 }203 return SurfaceExtent(surface, bounds, size)204}205206// planeSurface reads the surface the way the seam's `worldSurface` does:207// absent means plane, which every world was until the planets arrived.208func planeSurface(attrs map[string]string) bool {209 declared := attrs[semconv.KeyGeometrySurface]210 return declared == "" || declared == semconv.SurfacePlane211}212213// The axes alternate, five bits to a character, x first. A character outside214// the alphabet is skipped without consuming a halving, so the axis does not215// alternate past it — which is what the field's own normalization makes216// unreachable and what this keeps true anyway.217// GeohashExtent halves the ground down to the cell an address names.218func GeohashExtent(ground Extent, hash string) Extent {219 out := ground220 splitX := true221 for _, character := range strings.ToLower(hash) {222 value := strings.IndexRune(GeohashAlphabet, character)223 if value < 0 {224 continue225 }226 for _, mask := range Masks {227 if splitX {228 middle := (out.MinX + out.MaxX) / 2229 if value&mask != 0 {230 out.MinX = middle231 } else {232 out.MaxX = middle233 }234 } else {235 middle := (out.MinY + out.MaxY) / 2236 if value&mask != 0 {237 out.MinY = middle238 } else {239 out.MaxY = middle240 }241 }242 splitX = !splitX243 }244 }245 return out246}247248// GeohashCellAt is the halving run backward: the same divisions, choosing at249// each one the side the point is on, to the depth asked for. It is the seam's250// `cellAt` (analysis/cellsystems/geohash.ts) and the descent the carry uses to251// walk a new hierarchy down toward an old cell's centre.252//253// A point off the surface names nothing, which is the empty answer -- not the254// root, which is a place.255func GeohashCellAt(ground Extent, x, y float64, depth int) string {256 if !ground.Holds(x, y) {257 return ""258 }259 out := ground260 splitX := true261 hash := make([]byte, 0, depth)262 for range depth {263 value := 0264 for _, mask := range Masks {265 if splitX {266 middle := (out.MinX + out.MaxX) / 2267 if x >= middle {268 value |= mask269 out.MinX = middle270 } else {271 out.MaxX = middle272 }273 } else {274 middle := (out.MinY + out.MaxY) / 2275 if y >= middle {276 value |= mask277 out.MinY = middle278 } else {279 out.MaxY = middle280 }281 }282 splitX = !splitX283 }284 hash = append(hash, GeohashAlphabet[value])285 }286 return string(hash)287}288289// GeohashHeld is the held-cell question for a geohash address: the halving,290// and then four comparisons. It is the fast path — an axis-aligned rectangle291// asked about a point — and it is boundary-inclusive, which is the contract's292// own word for it (analysis/testdata/cells/containment.json): a pin on the293// line between two cells is standing in both, because the line is drawn a294// pixel wide and the reader put the pin on it.295func GeohashHeld(ground Extent, hash string) Held {296 held := GeohashExtent(ground, hash)297 return held.Holds298}299300// Rect is a rectangle of the volume's own raster pixels, y down.301type Rect struct {302 X float64 `json:"x"`303 Y float64 `json:"y"`304 Width float64 `json:"width"`305 Height float64 `json:"height"`306}