Cartographic Projection
every map is wrong, and by exactly how much
Concept

Hierarchy — where it appears

The property that a cell's identifier begins with its parent's, which makes a coarse query one range scan and an aggregation a truncation. It is what a quadkey encodes, and it is the property that makes a tile scheme cacheable and a cell scheme aggregable without a join.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

The same address length, a tenth of the area. Every cell of a lon/lat quadtree at level 4 carries an identifier of the same length. The heavy curve is each cell's area as a fraction of the largest, against its latitude: a polar cell is 10.2 times smaller than an equatorial one. The light curve is the inverse of the cell's aspect ratio, which falls from 1.00 near the equator to 0.10 at the top — the cells stop being anything like square long before they stop being usable.

An address is an area

A cell identifier does not name a place, it names a region — so its precision is an area rather than a length. On the obvious lon/lat scheme that area varies by a factor of 10 at level 4 and 163 at level 8, and the factor doubles with every level: the same identifier length means less ground the further north it is used.

applied · Cells Hilbert order on one face, as a curve. The order in which Hilbert numbering visits the 64 cells of one cube face at level 3. The line never leaves a cell without entering one that shares an edge with it — that is what makes it a space-filling curve, and it is why two cells with nearby identifiers are usually near each other on the ground.

The address is a curve through the sphere

A database does not fetch a set of cells, it reads ranges of identifiers — so the cost of a query is how many runs its cells form, not how many cells it needs. Hilbert order wins that measurement and loses the one usually quoted for it: its neighbouring cells are further apart in identifier than row-major's, on average and at worst.

applied · Cells One field, one round trip between two cell schemes. Left: a stated field binned into an equal-angle grid of 36 by 18 cells. Right: the same field after being rebinned into an equal-area grid of 30 by 15 offset by six degrees of longitude, and rebinned back. Every step is exact area-weighted averaging, the total is preserved to 2 × 10⁻¹⁶, and the root-mean-square difference between the two pictures is 0.144 on a field whose own standard deviation is 0.370.

The same data on two grids

Five essays have addressed, queried and ordered cells within one scheme and nobody has moved a number between two. Doing it exactly — area-weighted, both directions — preserves the total to 2 × 10⁻¹⁶ and loses 39 per cent of the field's own standard deviation in a single round trip; six round trips leave 23 per cent of its variance. The quantity that would reveal the damage is the one that never moves.

applied · Cells A parent and its children, twice. An aperture-7 hexagonal hierarchy beside a square one. The heavy outline is the parent and the light ones are its children. On the right every child is wholly inside and the four of them tile the parent exactly. On the left the child lattice is turned by 19.107° relative to the parent's, only the central child is wholly inside, and 7.14% of the parent is covered by no child of its own. The two families have exactly the same total area — a hexagon cannot be tiled by smaller hexagons at any ratio at all, which is why the mismatch is a construction rather than an approximation.

A cell's children do not fit inside it

Ten rungs price one cell system at one resolution, and every one of them is used hierarchically. A hexagonal hierarchy does not nest: at the aperture-seven scheme the discrete global grids use, one fourteenth of a parent is covered by no child of its own, exactly, and each of the six ring children is eleven twelfths inside.

applied · Cells How far the two routes end up apart. The distance between a line simplified directly at the final tolerance and the same line simplified through two intermediate products, as a multiple of the final tolerance, with a stated extra step applied to each intermediate. With nothing in between the two are the same line to the last bit, because Douglas–Peucker's outputs are nested. Rounding the intermediate to half the tolerance, smoothing it for legibility, or running it through a moving average each break that, and the last of them puts the final product 0.142 away from where a direct route would have put it — nine times the tolerance the product is published under.

Two routes to one scale

A national series is cascaded — the million is derived from the quarter-million, which was derived from the fifty — and the folklore is that the errors accumulate. They do not: Douglas–Peucker and Visvalingam both cascade to the same line the direct route produces, bit for bit, because both output a sublevel set of a per-vertex number. What breaks it is anything else in the chain, and a moving average puts the product nine tolerances away.

applied · Generalise

Named alongside it

The objects these essays reach for when they reach for this one.

AggregationCellDiscrete global gridAddressClosed formLocalityAnisotropyToleranceAreaCell systemCompositionConservation

All concepts