Module spatial 

2i: space as a key discipline (FACT-04, D31).

A newcomer’s map. To index locations in a btree we need a way to turn two dimensions (lon, lat) into ONE sortable number such that places near each other in space usually get nearby numbers – then “everything in this box” becomes a few contiguous key ranges. A Hilbert curve does exactly that (better locality than the simpler Z-order: the curve never makes the big diagonal jumps Z does). We port PostGIS’s own Hilbert implementation – notable because PostGIS, the reference R-tree system, uses this very ordering to BUILD its R-trees; curve order is the best layout the R-tree camp knows, so we store in curve order directly.

Two fixed levels: FINE cells (16 bits per axis, ~600 m at the equator) for points and small shapes; COARSE (8 bits per axis) for anything whose bounding box would need more than MAX_CELLS fine cells. A geometry posts to at most MAX_CELLS cells – write cost O(1) per geometry, ever (Law 2).

Values carry the geometry’s bounding box as four f32s rounded OUTWARD (also PostGIS’s trick): a float box strictly containing the double box filters candidates without touching the payload; a degenerate box (xmin==xmax, ymin==ymax) IS a point, so point workloads answer exact distances straight from the posting – zero payload reads.

Structs

BoxF

Outward-rounded f32 bounding box – PostGIS box2df_from_gbox_p.

Enums

Geom

Typed geometry – the kernel’s only geometry language. Coordinates are (lon, lat) pairs in WGS84 degrees (GeoJSON axis order); rings are implicitly closed. GeoJSON <-> Geom conversion lives above the kernel.

Constants

LEVEL_COARSE

LEVEL_FINE

LEVEL_WORLD

Geometries too big for MAX_CELLS coarse cells (continent scale) post ONE entry in the world bucket, which every query also scans. Sound (never missed), bounded (one posting), cheap (members are rare and bbox-filtered). The corner-clip shortcut this replaces missed interior queries – caught by the coarse-fallback oracle test.

MAX_CELLS

A geometry posts to at most this many cells (Law 2’s bound).

Functions

cell_hilbert

Hilbert index of an (x, y) cell on a 2^bits x 2^bits grid – the classic level-parameterized xy2d walk (public domain; PostGIS uses the same curve family via a 32-bit bit-scan for its sorted R-tree builds, which inspired this keyspace). The bit-scan variant is fixed to 32-bit grids; our cells live at 8- and 16-bit levels, and a cell’s index must be computed AT ITS LEVEL or aligned squares stop being contiguous runs – the oracle test below caught exactly that with a scaled-shift shortcut. O(bits) per call, index-time only.

cell_of

Quantize lon in [-180,180], lat in [-90,90] to bits-per-axis cells.

cover_cells

The cells a bbox covers at bits per axis, capped: returns None when the cover would exceed max cells (caller drops to a coarser level).

cover_ranges

Decompose a query bbox into Hilbert key RANGES at one level: a quadtree refinement over Hilbert quadrants, emitting one [lo, hi] run for every square fully inside the box, dropping squares fully outside, and splitting the ones that straddle the box’s edge. max_ranges caps the output; the refinement spends that budget where it buys the most.