H3 vs S2 Cell Indexing Trade-offs for Mobility

Two discrete global grid systems dominate production mobility stacks, and they optimize for opposite things: Uber’s H3 tiles the globe with hexagons for uniform neighbour geometry, while Google’s S2 threads a Hilbert space-filling curve through quadrilateral cells so that spatial proximity becomes a contiguous integer-range scan. This page expands the constant-time containment model from Uber H3 Hexagon Indexing for Mobility under the broader spatial index lookup architecture, and it sits beside Comparing Geohash vs H3 for Low-Latency Routing as the other named comparison mobility teams weigh: when you have already ruled out string geohashes, does H3’s neighbour uniformity or S2’s range-query linearity give the cheaper hot path for your workload?

Concept and specification #

Both systems map (lat, lon) to a 64-bit cell id at a chosen resolution, but the id’s meaning differs, and that difference decides which query is cheap.

H3 encodes mode, resolution, base cell, and a base-7 sequence of child digits into 64 bits. Hexagonal tiling gives every interior cell exactly six equidistant neighbours, so a k-ring (grid_disk) is a bitwise traversal and proximity queries are uniform in every direction. The catch is that hexagons do not nest perfectly: a resolution-9 cell is not fully contained by a single resolution-8 parent — cell_to_parent is an approximation with ~1/7 boundary leakage — so H3 hierarchy is a lookup convenience, not exact containment.

S2 projects the sphere onto the six faces of a cube and threads a Hilbert curve through each face. A cell id is the face (3 bits) plus the cell’s position along the Hilbert curve plus a trailing sentinel bit. The decisive property: every cell’s descendants occupy a contiguous range $[\text{id}<em>\min ,\text{id}</em>\max ]$ on that curve, and children tile their parent exactly (four quads per parent, no leakage). So a spatial region becomes a small set of [min, max] integer intervals you can answer with an ordinary sorted index or a B-tree WHERE id BETWEEN — no spatial engine required.

Formally, an S2 covering of a region is a set of $r$ ranges and a point query is $r$ interval tests:

$$\text{contains}(p)⟺\exists ,i:;\text{id}<em>{\min }^{(i)}\le \text{cell}(p)\le \text{id}</em>{\max }^{(i)}$$

while an H3 proximity query over a k-ring visits

$$N_{\text{cells}}(k)=3k^2+3k+1$$

cells with no global linear order to exploit. The two shapes answer different questions cheaply: S2 excels at “is this point in this region” via range scans against a plain database; H3 excels at “what is near this point” via uniform rings.

Edge lengths track resolution/level closely enough to swap by scale band:

Step-by-step implementation #

Prerequisites: Python 3.11+, h3>=4.0, s2sphere>=0.2, numpy>=1.26. Input is a stream of (lat, lon) WGS84 pairs; the two hot paths answer “which zone is this point in”.

1. H3 — encode and gather a uniform ring. Proximity is a bitwise grid_disk.

import h3

H3_RES: int = 9  # ~174 m edge, block-level mobility

def h3_candidates(lat: float, lon: float, zone_index: dict[str, set[str]], k: int = 1) -> set[str]:
    """Union of zone ids in the ping's cell and its k-ring."""
    cell: str = h3.latlng_to_cell(lat, lon, H3_RES)
    out: set[str] = set()
    for nb in h3.grid_disk(cell, k):            # 6-neighbour bitwise traversal
        out |= zone_index.get(nb, frozenset())
    return out

2. S2 — encode to a leaf cell, truncate to a level. The parent is exact bit truncation.

from s2sphere import CellId, LatLng

S2_LEVEL: int = 16  # ~140 m, comparable to H3 res 9

def s2_cell(lat: float, lon: float) -> int:
    leaf = CellId.from_lat_lng(LatLng.from_degrees(lat, lon))  # level-30 leaf
    return leaf.parent(S2_LEVEL).id()           # exact truncation to a level-16 id

3. S2 — precompute region coverings as id ranges, query by range scan. This is the pattern H3 cannot match: containment against a plain sorted index.

from s2sphere import RegionCoverer, LatLngRect, LatLng

def zone_ranges(rect: LatLngRect) -> list[tuple[int, int]]:
    """Cover a zone with S2 cells, return contiguous Hilbert id ranges."""
    coverer = RegionCoverer()
    coverer.min_level = 14
    coverer.max_level = 18
    coverer.max_cells = 32                      # cap covering size — see failure modes
    covering = coverer.get_covering(rect)
    # Each cell's descendants are a contiguous [range_min, range_max] on the curve.
    return sorted((c.range_min().id(), c.range_max().id()) for c in covering)

def in_zone(point_id: int, ranges: list[tuple[int, int]]) -> bool:
    # Point-in-region is r interval tests (or a bisect against a sorted table).
    return any(lo <= point_id <= hi for lo, hi in ranges)

Gotcha: s2sphere is pure Python, so from_lat_lng costs ~3–5 µs versus H3’s ~1.5 µs C call. For high-rate encoding, precompute leaf ids in a batch or use a compiled s2geometry binding; keep the pure-Python path for the low-rate covering step only.

4. S2 — enumerate neighbours when you do need adjacency. Unlike H3’s single uniform ring, S2 splits edge and vertex neighbours.

def s2_neighbours(cell_id: int, level: int) -> list[int]:
    cid = CellId(cell_id)
    edge = [n.id() for n in cid.get_edge_neighbors()]      # 4 edge-adjacent
    vertex = [n.id() for n in cid.get_vertex_neighbors(level)]  # 4 diagonal
    return edge + vertex

Benchmark and verification #

Single core, 10k pings against ~5k zones, H3 res 9 vs S2 level 16 with a 32-cell covering, comparing a point-in-zone query.

S2’s range-scan query is faster once the covering is precomputed, because containment collapses to a handful of integer comparisons against a sorted table — ideal when zones live in Postgres or a KV store keyed by id range. H3 wins on encode latency and on proximity: “vehicles near this ping” is one uniform ring, whereas the same query on S2 requires assembling edge and vertex neighbours at possibly different levels. A minimal harness:

import time, statistics

def bench(fn, args, runs: int = 30) -> dict[str, float]:
    s: list[float] = []
    for _ in range(runs):
        t0 = time.perf_counter()
        for a in args:
            fn(*a)
        s.append((time.perf_counter() - t0) / len(args) * 1e6)  # µs/call
    s.sort()
    return {"p50": statistics.median(s), "p95": s[int(0.95 * runs)], "p99": s[int(0.99 * runs)]}

Verify covering fidelity before promoting: for each zone, sample points inside and outside the true polygon and confirm the S2 range set and the H3 cell set agree to >99.5% recall with the exact geometry, tightening max_level/H3_RES until boundary error is acceptable. The choice interacts with the memory budget from Memory Footprint of Streaming Polygon Indexes: each finer S2 level or H3 resolution multiplies stored cell count roughly 4× (S2) or 7× (H3).

Failure modes and edge cases #

• S2 covering blow-up. RegionCoverer on a thin, elongated, or diagonal zone with a high max_level and a large max_cells can emit hundreds of cells, exploding the range table and the scan cost. Cap max_cells (16–32 for triggers), and accept the coarser covering — over-covering a boundary is usually safer than a thousand-range scan on the hot path.
• H3 pentagons. At the 12 icosahedron vertices grid_disk returns fewer than $3k^2+3k+1$ cells and distortion metrics break. Never assert on ring size; iterate the returned list. Pentagons sit almost always over ocean, but a global fleet eventually hits one.
• H3 non-nesting. Treating cell_to_parent as exact containment silently drops points near hexagon boundaries, because a child hexagon straddles up to two parents. Use S2, or an explicit multi-resolution index, when exact hierarchical roll-up is required.
• S2 cube-face distortion. Cells near cube-face edges are more elongated than face centres, so a fixed level gives non-uniform ground area — a proximity threshold in “cells” is not a constant distance. Convert to metric radius explicitly rather than trusting cell counts.
• NaN or out-of-range coordinates. Both latlng_to_cell and from_lat_lng misbehave on NaN or out-of-range input — H3 raises, S2 can produce a garbage leaf. Validate at ingest and route bad fixes to a dead-letter path.

Related #

• Uber H3 Hexagon Indexing for Mobility — the parent deep dive on H3’s 64-bit address layout and constant-time containment
• Comparing Geohash vs H3 for Low-Latency Routing — the sibling comparison against string geohashes
• Spatial Indexing for Real-Time Checks — where discrete grids fit against tree indexes in the routing pipeline
• Memory Footprint of Streaming Polygon Indexes — how resolution choice drives stored cell count and RSS