H3 Bound Cells

Convert geographic polygons into multi-resolution H3 cell coverings, with fast point-in-region lookups.

Rust core is built on h3o and exposed to Python via PyO3 / Maturin.

Overview

BoundCells is a pair of dicts keyed by H3 resolution:

• area — cells whose interior lies inside the polygon.
  • The area layer is compacted: wherever all 7 children at a resolution are present, they collapse up to the parent.
  • A single covering naturally spans multiple resolutions (chunky cells in the interior, smaller cells near the edge).
• border — cells that overlap the polygon boundary, materialised at every coarser resolution down to min_cell_resolution.

The border layer is what makes containment lookups cheap. To check whether an arbitrary cell falls inside the region, cell_in_bound_cells first tests the cell against the border layer at its own resolution, then walks its ancestors from fine to coarse against the compacted area cells, returning true on the first hit — no need to materialise every leaf cell of the polygon. A query cell is "inside" if it — or one of its H3 ancestors computed via cell.parent() — is an area cell.

Install

The package is built locally with maturin:

uv sync
uv run maturin develop --release

Usage

import h3
from h3_bound_cells import polygon_to_bound_cells, cell_in_bound_cells, BoundCells

# Rectangle around central London. (lat, lng) pairs; the ring need not be closed.
exterior = [
    (51.50, -0.13),
    (51.52, -0.13),
    (51.52, -0.08),
    (51.50, -0.08),
]

bc = polygon_to_bound_cells(exterior, start_res=9, min_cell_resolution=4)

print(bc)
# BoundCells(area_resolutions=[...], border_resolutions=[...])

for res, cells in bc.area.items():
    print(f"area   res {res}: {len(cells)} cells")
for res, cells in bc.border.items():
    print(f"border res {res}: {len(cells)} cells")

# Point-in-region check: Trafalgar Square at H3 resolution 11.
cell = h3.latlng_to_cell(51.5074, -0.1278, 11)
assert cell_in_bound_cells(cell, bc)

# JSON-friendly round trip
restored = BoundCells.from_dict(bc.to_dict())

API

• polygon_to_bound_cells(exterior, holes=None, start_res=None, min_cell_resolution=None, tolerance=None) -> BoundCells
  • exterior, holes — lists of (lat, lng) tuples. Note: this is (latitude, longitude), matching the H3 convention (e.g. h3.latlng_to_cell) — the reverse of GeoJSON/shapely/WKT, which use (longitude, latitude). Swap the order when feeding in GeoJSON coordinates.
  • start_res — H3 resolution to tile at. When omitted, it is auto-picked from the polygon's planar area.
  • min_cell_resolution — floor for the border layer (default 4).
  • tolerance — Douglas–Peucker simplification distance in degrees, applied to the polygon before tiling. Tiling cost is linear in vertex count, so simplifying high-fidelity boundaries (e.g. OS/OSM data with metre-scale vertices) is a large speed-up. Defaults to 0 — no simplification, an exact covering identical to the raw geometry. Pass a small positive value (e.g. 1e-5, ≈1 m, for a ~5× speed-up on detailed boundaries) to opt in. Note that any non-zero tolerance is effectively-lossless rather than provably identical: a cell whose centroid lies within ~tolerance of the boundary can flip. Larger values are faster but shift more such edge cells.
• cell_in_bound_cells(cell: str, bound_cells: BoundCells) -> bool — membership test by H3 cell id.
• BoundCells — frozen class:
  • .area, .border — dict[str, list[str]] keyed by stringified resolution.
  • .to_dict() / BoundCells.from_dict(d) — JSON-friendly round trip.
  • BoundCells.merge([bc1, bc2, ...]) — union of multiple results.
  • .cells_at_resolution(res) — flatten/expand the covering to a single H3 resolution (parents map up, coarser cells expand to their children).

Polars integration (optional)

Filter a Polars DataFrame/LazyFrame down to the rows whose H3 cell falls inside a covering.

Install the optional polars extra:

pip install h3_bound_cells[polars]

Importing h3_bound_cells registers a bound_cells namespace on Polars expressions (only registered when polars is installed):

import polars as pl
import h3_bound_cells  # registers the bound_cells namespace

bc = h3_bound_cells.polygon_to_bound_cells(exterior, start_res=9)

df = pl.DataFrame({"cell": [...]})  # H3 cells as hex strings or u64 ints

# Filter to rows inside the covering:
df.filter(pl.col("cell").bound_cells.is_in(bc))

# Or use the boolean result as a column:
df.with_columns(inside=pl.col("cell").bound_cells.is_in(bc))

• pl.col(cell_column).bound_cells.is_in(bound_cells) — a boolean expression, true where the cell lies inside bound_cells.
• Use it anywhere an expression is accepted (filter, select, with_columns, boolean combinations, …).
• Works with both eager and lazy frames. Cells may be hex strings or u64 ints; a null cell maps to false (dropped by filter).

Predicate pushdown (Parquet)

is_in is a native plugin, so the query optimiser can't see through it to prune a scan on its own. To fix that, is_in ANDs a pure H3-index range predicate in front of the exact check (prefilter=True, on by default). Because an H3 index sorts identically as a u64 and as its 15-char hex string, Polars can push that range test into a Parquet SCAN and skip whole row groups via their min/max statistics — often a large speed-up on big scans, with an identical result. The exact plugin check still runs, so correctness is unchanged.

This is ONLY recommended in Lazy Execution as it provides purely IO-bound wins, with a collected DataFrame there is no scan to prune so this then just becomes and additional filter to run.

lf = pl.scan_parquet("atlas.parquet")  # sorted by the H3 column

# UInt64 cell column (default dtype):
lf.filter(pl.col("h3").bound_cells.is_in(bc))

# Canonical 15-char hex-string cell column:
lf.filter(pl.col("h3point").bound_cells.is_in(bc, dtype=pl.Utf8))

For the prefilter to be correct and effective:

• Resolution — by default the range predicate covers every resolution, so it is correct whatever resolution the column is at. If you know it, pass child_res=<res> (e.g. child_res=15) for the leanest predicate; the extra ranges of the default sit in empty u64 regions for a uniform-resolution column, so they don't weaken pruning either way.
• Matching dtype — dtype must match the column: pl.UInt64 (default) for an integer column, or pl.Utf8 for a canonical 15-char lowercase-hex string column.
• Sorted column — row-group skipping is dramatic only when the column is sorted (tight per-group min/max). On unsorted data the prefilter still trims per-row plugin cost but skips no row groups.

Pass prefilter=False for the exact-only behaviour.

Dev visualiser

A small MapLibre app for drawing polygons and visualising the covering. It runs the Rust core entirely in the browser via WebAssembly — no backend — so it is a fully static page.

Draw a polygon (Draw polygon, click vertices, double-click to finish) and the area and border layers render colour-coded by resolution. Leave start_res blank to let the library auto-pick from the polygon's area, or set it to override. Renders are capped at 50,000 cells; reduce the polygon size or raise start_res if you trip the limit.

Running it locally

The page needs the WASM module built into dev/pkg/, and must be served over http(s) (ES-module + .wasm loading doesn't work from a file:// URL). Both are handled by:

just serve            # builds dev/pkg, then serves http://127.0.0.1:5050/

Or run the steps by hand (requires wasm-pack):

wasm-pack build --target web --out-dir dev/pkg --no-default-features --features wasm
python -m http.server -d dev 5050

The browser build compiles the same polygon_to_bound_cells core under the crate's wasm Cargo feature (PyO3 is behind the default python feature and excluded here).