Engineering Atlas › System Design Fundamentals

Geospatial cells with S2 and H3

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

S2: cube, quadtree, Hilbert curve

Each point on the sphere is projected onto one of six faces of a surrounding cube, and a non-linear transform evens out cell sizes so that, at any level, areas differ by only about a factor of two: level-10 cells range from 48.8 to 102.0 square km (S2 cell statistics). Geohash cells, by contrast, shrink to slivers near the poles.

Each face is a quadtree 30 levels deep; a level-30 leaf is under a square centimetre. Cells are numbered along a Hilbert curve, which, unlike geohash's Z-order curve, never jumps: consecutive cells are always edge neighbours. The six faces' curves are oriented so that each one ends where the next begins, giving one continuous loop over the whole sphere (S2 cell hierarchy).

The 64-bit cell ID packs the face (3 bits), 2 bits per level, and a trailing 1 bit marking the level. All descendants of a cell therefore occupy one contiguous range of leaf IDs, so containment is range_min <= id <= range_max, which any B-tree or sorted key store handles.

Cell area falls 4x per level: level 10 averages about 81 square km, level 16 about 140 m across.

S2 coverings

The region coverer takes a polygon or circle plus limits (min level, max level, max cells) and returns mixed-size cells covering it: big cells inside, small cells along the boundary. The default is 8 cells (s2region_coverer.h), which gives a loose cover; 200 give a tight one at the cost of more lookups. Never go below 4: with at least 4 cells the covering's area is at worst about 10 times the region's, but with fewer it can be astronomically larger (S2 coverings guide). The covering is the query plan: one range scan per cell, then an exact geometry test.

H3: icosahedron and hexagons

H3 projects the sphere onto an icosahedron and lays a hexagonal grid over it. There are 122 base cells at resolution 0. Each finer resolution has about seven times as many cells (aperture 7), over 16 resolutions from 0 to 15. Resolution 7 hexagons average about 5.2 square km, resolution 8 about 0.74 square km, resolution 9 about 0.1 square km, and resolution 15 under one square metre (H3 resolution table).

Hexagons have two consequences. All six neighbours share an edge at the same centre distance, so the ring of cells at distance k (gridDisk) is uniform, whereas square grids mix edge and corner neighbours and bias smoothing. But hexagons cannot be split exactly into smaller hexagons, so a parent's seven children only approximate its area, and truncating IDs is not an exact containment test as it is in S2. H3 approximates the seven-way split by rotating the grid between resolutions; containment is exact in the index, but only approximate on the ground (H3 indexing).

Every resolution also has exactly 12 pentagons, at the icosahedron's vertices, mostly in oceans; some functions return errors when they hit one.

Down the stack

Layer 1The contract

S2 promises an exact hierarchy: every leaf belongs to exactly one cell at each level, and a cell contains a point if and only if the point's leaf ID falls in the cell's ID range. A covering is guaranteed to contain the whole region; an interior covering is guaranteed to lie inside it. H3 promises a deterministic cell for every point at each resolution and exact neighbour relations, but parent-child containment is only approximate, and some grid functions can return errors near pentagons.

Layer 2The mechanism

An S2CellId is a 64-bit integer: 3 face bits, then 2 bits per level of Hilbert position, then a single 1 bit, then zeros. The lowest set bit encodes the level. If lsb = id & -id, the descendants span [id - lsb + 1, id + lsb - 1], and the parent at a coarser level is found by clearing low bits and setting the new lowest bit. Converting a point to a cell uses lookup tables that advance the Hilbert curve 4 levels at a time.

An H3Index is also 64 bits: a reserved bit, a 4-bit mode (1 means cell), 3 reserved bits, a 4-bit resolution, a 7-bit base cell (0 to 121), then fifteen 3-bit digits, each 0 to 6, with unused digits set to 7 (H3 cell index). Function names changed in H3 v4: kRing became gridDisk, geoToH3 became latLngToCell, h3ToParent became cellToParent and polyfill became polygonToCells, so tutorials using the old names target v3 (H3 migration guide). cellToParent lowers the resolution field and sets the trailing digits to 7. Internally, points are projected gnomonically onto an icosahedron face and placed on IJK hexagon coordinates, with the grid rotated between odd and even resolutions.

Layer 3The machine

Point-to-cell conversion is dominated by trigonometry: a few sin, cos, and atan2 calls at roughly 20 to 50 ns each, so one conversion costs on the order of 100 ns to 1 us. After that, everything is integer work. Parent computation is a few bit operations; comparing two IDs is one instruction.

Storage benefits most. An 8-byte key packs about 400 entries into an 8 KB B-tree leaf page. In LSM stores and Bigtable-style systems that keep rows sorted by key, an S2 covering cell is one contiguous key range, so each cell costs one seek and then sequential block reads. The flip side is that a dense city maps to a narrow key range, which concentrates load on one tablet or shard.

Why it's built this way

  1. A sphere cannot be flattened without distortion, so both systems project onto polyhedron faces where distortion is bounded.
  2. Cube faces split cleanly into quadrants, so S2 can use exact quadtree bits and a Hilbert curve for contiguous ranges.
  3. Hexagons give equidistant neighbours, but a sphere cannot be tiled by hexagons alone, so H3 must include exactly 12 pentagons.
  4. Databases and caches handle integers best, so both encode cells as 64-bit IDs with the hierarchy in the bits.

Diagram

flowchart TD
    P["Point (lat, lng)"] --> S1["S2: project to cube face"]
    P --> H1["H3: project to icosahedron face"]
    S1 --> S2["Quadtree subdivide, 30 levels"]
    S2 --> S3["Order cells on Hilbert curve"]
    S3 --> S4["64-bit cell ID, descendants contiguous"]
    S4 --> S5["Range scans for containment"]
    H1 --> H2["Hexagon grid, aperture 7"]
    H2 --> H3["64-bit cell index, 16 resolutions"]
    H3 --> H4["k-rings for neighbours and smoothing"]

Worked example

A ride-hailing company computes surge multipliers every minute for a metro area of about 1,500 square km.

At H3 resolution 8 (0.74 square km per cell) the city has roughly 2,000 cells. Each of 50,000 requests and 300,000 driver pings per minute maps to a cell in about a microsecond, and a streaming job keeps two counters per cell. Per-cell ratios are noisy, so each cell is smoothed with its first ring (gridDisk(cell, 1), 7 cells), weighting neighbours equally because they are equidistant.

For 30,000 airport and stadium pickup geofences, S2 fits better. Each polygon is covered with at most 16 cells between levels 10 and 16, about 480,000 (cell ID, fence ID) rows. A pickup point's ancestor cell at each of those 7 levels is looked up, returning the few fences to check exactly with point-in-polygon, all well under a millisecond in memory.

Covering size is the tuning knob: at 16 cells per fence about 12 percent of lookups yield a false-positive candidate; 64 cells cut that to 3 percent but quadruple the index.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
S2Exact hierarchy, contiguous descendant ranges, flexible coverings, low distortionSquare cells have unequal neighbour distances, harder to visualiseIndexing regions, containment, range-scan storage
H3Equidistant neighbours, uniform-looking cells, great for aggregationApproximate hierarchy, 12 pentagons per level, no exact parent containmentAnalytics, heatmaps, smoothing, supply and demand bucketing
GeohashReadable strings, works anywhereLarge distortion near poles, Z-curve jumps, 8-neighbour expansionSimple proximity search, small scope
R-tree on raw geometryExact shapes, no discretisationNeeds a spatial engine, hard to shardComplex polygons in a single database

Pitfalls in production

Leadership lens

Check yourself

  1. Why can S2 answer "is this point inside this cell" with a single integer range check?

    Show answer

    Cells are numbered along a Hilbert curve with a level-terminating bit, so all leaf descendants of a cell fall in one contiguous ID range, and the point's leaf ID is inside the cell exactly when it is inside that range.

  2. Why do H3 users prefer hexagons for smoothing demand across neighbouring areas?

    Show answer

    All six neighbours share an edge and are equidistant from the centre, so a k-ring is an unbiased neighbourhood; square grids mix edge and corner neighbours at different distances.

  3. What do you lose by using H3's parent function as a containment test?

    Show answer

    Exactness. Seven child hexagons only approximate their parent's area, so points near the boundary can belong to a child whose parent ID is not the hexagon that geometrically contains them.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →