Metadata-Version: 2.4
Name: h3_bound_cells
Version: 0.2.2
Classifier: Programming Language :: Rust
Classifier: Programming Language :: Python :: Implementation :: CPython
Requires-Dist: polars>=1 ; extra == 'polars'
Provides-Extra: polars
License-File: LICENCE
Summary: H3 BoundCells for Fast Point-in-Polygon Lookups
Author-email: Ben Burwood <ben.burwood@streetwave.co>
Requires-Python: >=3.9
Description-Content-Type: text/markdown; charset=UTF-8; variant=GFM

# H3 Bound Cells

Convert geographic polygons into multi-resolution [H3](https://h3geo.org) cell coverings, with fast point-in-region lookups. 

Rust core is built on [`h3o`](https://crates.io/crates/h3o) and exposed to Python via [PyO3](https://pyo3.rs) / [Maturin](https://www.maturin.rs).

## 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.

![BoundCells](BoundCells.png)

## Install

The package is built locally with maturin:

```
uv sync --dev
uv run maturin develop --release
```

The `dev` dependency group (declared in `pyproject.toml`) also pulls in `flask`,
`h3`, `polars`, and `pytest`, used by the visualisation server, the tests, and
the optional Polars integration below.

## Usage

```python
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) -> 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`).
- **`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):

```python
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.

```python
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 server

A small Flask + MapLibre app for drawing polygons and visualising the output:

```
just serve
# or:
uv run --dev dev/server.py
```

Then open <http://127.0.0.1:5050/>. Draw a polygon, hit **Compute Bound Cells**, and the area and border layers render colour-coded by resolution.
Renders are capped at 50,000 cells; reduce `start_res` or shrink the polygon if you trip the limit. 
The page also accepts a pre-computed `{"area": {...}, "border": {...}}` blob via the **Render Cells** panel for offline inspection of saved output.

