Metadata-Version: 2.4
Name: h3_bound_cells
Version: 0.5.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

https://pypi.org/project/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).

Generation uses [`h3-compactfill`](https://github.com/ben-burwood/h3-compactfill) which is an extension to H3 which implements a short-circuited `polygonToCells` + `compact` Algorithm.

## Overview

`BoundCells` holds a Compacted Polyfill of a target Polygon, keyed by H3 Resolution.

*Generation* - Fairly standard polyfill+compact step which converts a Polygon into contained H3 Cells. 
  Start Resolution - This is the finest (highest) Resolution of the Cells, this is needed at cell edges to get a closer match to the polygon.
*Containment* - Walks a datasets H3 Cells (checking each from fine->coarse) against the BoundCells for containment predicate. 
  Prefilter allows for Parquet Predicate Pushdown which can Prune Row Groups by checking against Cell Index Ranges.

## Install

The package is built locally with maturin: `uv run maturin develop --release`

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

print(bc)
# BoundCells(cells={8: 9, 9: 5, ...})

for res, cells in bc.cells.items():
    print(f"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, containment_mode=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.
  - `containment_mode` — a `BCContainmentMode` selecting which cells the fill keeps (default `BCContainmentMode.ContainsCentroid`). See `BCContainmentMode` below.
  - `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.
- **`cells_to_bound_cells(cells) -> BoundCells`**
  - Build a covering directly from an existing set of H3 cells, skipping polygon tiling. `cells` is an iterable of H3 cells as hex strings or u64 ints.
  - Input must be at a **single resolution** (mixed resolutions raise `ValueError`); duplicates are de-duplicated. An empty input yields an empty covering.
- **`cell_in_bound_cells(cell: str, bound_cells: BoundCells) -> bool`** — membership test by H3 cell id.
- **`BCContainmentMode`** — enum choosing which cells a polygon fill keeps (mirrors h3o's `ContainmentMode`):
  - `ContainsCentroid` *(default)* — cell kept when its **centroid** is inside. Fast, approximate interior.
  - `ContainsBoundary` — cell kept only when **fully inside**. Strict interior — no false positives, but omits edge cells only partly inside.
  - `IntersectsBoundary` — cell kept when it **touches** the polygon. Produces a **superset** covering that extends past the edge.
  - `Covers` — like `IntersectsBoundary`, also handling polygons smaller than a cell. Also a **superset**.
  - ⚠️ The overlap modes (`IntersectsBoundary`, `Covers`) make the covering a conservative superset, so `cell_in_bound_cells` then means "overlaps the region" and can report cells lying *outside* the polygon as inside. Use them when you want a covering, not exact point-in-region.
- **`BoundCells`** — frozen class:
  - `.cells` — `dict[str, list[str]]` keyed by 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.

