VehicleMapping HD AV Spatial Data

Tiling HD Maps with Quadkeys and H3

Cutting a validated HD map into servable tiles sounds like a spatial-index problem and is really a data-ownership problem. The index decides which bytes go in which file; the ownership rule decides whether a consumer can read one of those files on its own. Get the index right and the wrong ownership rule and you have built a map where every tile requires its neighbour, which is a regional file with extra steps.

This task cuts a map for map tile serving and distribution: choose a level from the metric cell size at your latitude, give every lane feature exactly one owning tile, emit reference stubs where features cross a boundary, and compute onboard prefetch sets with H3 rings.

The two indexes do different jobs, and a fleet normally runs both:

Quadkey Hierarchy against H3 Ring Geometry Left: a quadtree subdivision with keys extending by one digit per level and a storage path derived from the key. Right: a hexagonal grid with a centre cell and its uniform-distance ring of six neighbours. 120121 122123 parent "12" subdivides prefix selects a subtree → tiles/1/2/0/tile.bin sorts, ranges and caches like a path ego k-ring(1) is exactly the six neighbours all at the same distance — a true radius query quadkeys address storage · H3 selects what to fetch — neither replaces the other

Prerequisites #

  • Python 3.10+, NumPy 1.24+, shapely 2.0+ for midpoint and intersection tests, h3 4.x for the ring queries.
  • Input: a validated, projected map whose features carry stable identifiers, as produced by lane-level topology modeling and signed by the version-control stage.
  • Upstream stage: this runs after validation and before delta computation, so the tile is the unit the digest is taken over.
  • Output: one file per occupied quadkey, plus a manifest mapping quadkey to content digest.

Step-by-Step #

1. Choose the level from the metric cell size #

A quadkey level is a global subdivision count, not a metric size — cell width shrinks with the cosine of latitude. Compute the actual size at your operating latitude before fixing the level.

python
import numpy as np

EARTH_CIRCUMFERENCE_M = 40_075_017.0

def cell_size_m(level: int, lat_deg: float) -> float:
    """Approximate quadkey cell width in metres at a given latitude."""
    return EARTH_CIRCUMFERENCE_M * np.cos(np.radians(lat_deg)) / (1 << level)

At level 15 this returns about 1 223 m at the equator, 786 m at 50°N and 611 m at 60°N. Expected output: a float; choose the coarsest level whose value stays inside your target range across every latitude the fleet operates at, then confirm the densest tile at that level decodes inside the frame budget.

2. Assign every feature to exactly one owning tile #

The ownership rule is the whole design. A feature belongs to the tile containing its midpoint by arc length, whatever else it overlaps, and it is written into that tile complete.

python
from shapely.geometry import LineString

def owning_quadkey(geom: LineString, level: int) -> str:
    """The tile that owns a feature: the one containing its arc-length midpoint."""
    mid = geom.interpolate(0.5, normalized=True)
    return quadkey(mid.x, mid.y, level)


def assign_owners(features: dict[str, LineString], level: int) -> dict[str, list[str]]:
    """Group feature ids by owning tile."""
    owners: dict[str, list[str]] = {}
    for fid, geom in features.items():
        owners.setdefault(owning_quadkey(geom, level), []).append(fid)
    return {k: sorted(v) for k, v in owners.items()}

Midpoint rather than start point matters: start points cluster at junctions, so a start-point rule loads the tile containing a busy intersection with every lane radiating out of it. Sorting the identifier lists keeps the tile bytes deterministic, which is what makes the digest in computing content-addressed map tile deltas stable across re-cuts.

Two ownership rules on the same junction, and why one of them makes the centre tile enormous:

Start-Point Ownership against Midpoint Ownership at a Junction Two two-by-two tile grids with a junction inside the lower-right tile, showing per-tile feature counts under each ownership rule. start-point rule 22 214 all twelve turn lanes start inside the junction so one tile decodes roughly six times slower midpoint rule 55 55 turn geometry distributes across the four tiles decode time stays flat across the region neither rule splits a feature — they differ only in which single tile holds it whole

3. Emit reference stubs on the boundary #

A consumer reading the neighbour tile still needs to know a lane continues into it. Write a stub — identifier, owning quadkey, and the entry point — rather than a copy of the geometry.

python
def boundary_stubs(features: dict[str, LineString], owners: dict[str, list[str]],
                   level: int) -> dict[str, list[dict]]:
    """For each tile, stubs for features owned elsewhere that cross into it."""
    stubs: dict[str, list[dict]] = {}
    owner_of = {fid: qk for qk, fids in owners.items() for fid in fids}
    for fid, geom in features.items():
        home = owner_of[fid]
        touched = {quadkey(x, y, level) for x, y in geom.coords}
        for qk in sorted(touched - {home}):
            stubs.setdefault(qk, []).append({"id": fid, "owner": home})
    return stubs

Key parameter: sampling geom.coords rather than the bounding box keeps the stub set tight — a diagonal lane's bounding box touches tiles the lane never enters. Expected output: a few stubs per boundary tile, each a few dozen bytes.

4. Compute the prefetch set with an H3 ring #

Onboard, the question is "which tiles are within reach", and that is a ring query. Convert the pose to an H3 cell, take a k-ring, and map each cell back to the quadkeys it overlaps.

python
import h3

def prefetch_quadkeys(lat: float, lon: float, level: int,
                      h3_res: int = 8, k: int = 2) -> set[str]:
    """Quadkeys covering the H3 k-ring around the current pose."""
    here = h3.latlng_to_cell(lat, lon, h3_res)
    keys = set()
    for cell in h3.grid_disk(here, k):
        for cell_lat, cell_lng in h3.cell_to_boundary(cell):
            keys.add(quadkey(cell_lng, cell_lat, level))
    return keys

Choose h3_res so a cell is comfortably smaller than a quadkey tile — otherwise one cell spans several tiles and the ring over-fetches. With k = 2 at resolution 8 the disk covers roughly a kilometre, which is the right order for a planning horizon.

How the level choice moves with latitude, which is the part a single number hides:

Quadkey Cell Width Against Latitude at Three Levels Three falling curves of cell width against latitude with a shaded target band, showing which level stays inside the band across the operating latitudes. target band 500–1000 m 0°25°50°70°N operating latitude → 0500 m1000 m2500 m level 14 level 15 — inside the band to ~60° level 16 pick from the widest latitude the fleet operates at, not from the equatorial figure

Verification & Acceptance Criteria #

The cut is correct when every feature appears exactly once as an owner and the tiles round-trip to the original map.

python
def assert_cut_is_sound(features, owners, stubs) -> None:
    owned = [fid for fids in owners.values() for fid in fids]
    assert len(owned) == len(set(owned)), "a feature is owned by two tiles"
    assert set(owned) == set(features), "a feature has no owning tile"
    for qk, entries in stubs.items():
        for e in entries:
            assert e["owner"] != qk, "a tile holds a stub for a feature it owns"
    print(f"{len(owners)} tiles, {len(owned)} features, no splits")

Acceptance gate: exactly one owner per feature; the union of owned features equals the input set; no self-referential stubs; and the largest tile's decode time inside the frame budget. Re-cutting the same input must reproduce byte-identical tiles, which the digest comparison in the release pipeline asserts.

Common Errors & Fixes #

One tile is many times larger than its neighbours. Ownership is falling on a start point or a bounding-box centroid, concentrating junction geometry. Switch to the arc-length midpoint as in step 2.

A lane vanishes at a tile boundary in the rendered map. The consumer is reading owned features only and ignoring stubs. Stubs are not optional metadata — resolve them, or accept that the renderer shows a tile rather than a map.

The prefetch set covers half the city. h3_res is too coarse relative to the quadkey level, so each ring cell maps to many tiles. Raise the resolution until a cell sits inside a tile.

Re-cutting an unchanged region produces new digests. Feature identifier lists are not sorted, or the coordinates were re-projected between runs. Sort before writing and pin the projection parameters, the same determinism requirement HD map version control places on every artefact.

FAQ #

Why not split a lane feature at the tile boundary? #

A split feature cannot be interpreted from one tile: the fragment has no start, no end, and half a curvature profile. Every consumer then needs both tiles to read either, which defeats the whole point of tiling and creates a hard dependency between a tile and its neighbour. Assigning the feature whole to the tile containing its midpoint keeps each tile independently readable, and a lightweight reference stub in the neighbour tells a consumer where the rest of the geometry lives if it needs it.

How do I choose the quadkey level? #

Work backwards from two numbers. First, the metric cell size you want at your operating latitude — quadkey cells shrink as the cosine of latitude, so a level giving 1 km at the equator gives about 640 m at 50 degrees north. Second, the decode time of your densest tile, which must fit inside the frame budget. Pick the coarsest level that satisfies both, because coarser tiles mean fewer boundaries to stitch and a smaller manifest.

What is an H3 k-ring used for here? #

It answers the question the vehicle actually asks: which cells lie within k steps of where I am. Quadkey neighbours are awkward for that because a cell's neighbours may share no prefix at all, and diagonal neighbours are further away than orthogonal ones. H3 cells tile the plane with uniform neighbour distance, so a k-ring is an exact radius query. Fleets keep quadkeys for storage paths and use H3 rings purely to decide what to prefetch.

Up one level: Map Tile Serving & Distribution — the distribution stage whose unit of transfer this cut defines.