mortie

Mortie is a library for applying morton indexing to healpix grids. Morton numbering (also called z-ordering) facilitates several geospatial operators such as buffering and neighborhood look-ups, and can generally be thought of as a type of geohashing.

This particular implementation focuses on hierarchical healpix maps, and is mostly inspired from this paper.

Documentation

The full documentation — the generated API reference alongside the specification, interchange and coverage guides — is published at espg.github.io/mortie. Every page below is rendered there; the in-tree markdown links are the same content at the revision you are reading.

The normative encoding and conventions — the packed-word bit layout, the decimal string grammar, the order 0–29 resolution table, the morton-hive store layout, and the coverage-MOC serializations, all frozen for the 1.x series — are documented in docs/specification.md. Moving a packed word to and from the wider HEALPix ecosystem (cdshealpix / healpy (order, nested-pixel) pairs) is covered in docs/healpix_interchange.md.

Example notebooks

Runnable walkthroughs live in examples/; each opens on Binder from the badge in its first cell. Two of them need no downloads at all — morton_set_algebra.ipynb for the MOC boolean verbs, and toc_temporal_coverage.ipynb for the toc word (temporal order coverage: encoding, the conservative merge, the comparator-free sort, window predicates, and the UTC/GPS boundary).

Performance

Mortie's morton core is a Rust extension and the sole runtime path — there is no Python implementation to fall back on — so performance is reported as absolute throughput rather than a speedup ratio. Encoding (geo2mort) and decoding (mort2geo) run at tens of millions of morton indices per second on one core, staying within roughly 2× across orders 4–29.

See docs/benchmarks.md for the full cross-order table (raw encode / decode throughput and coverage timing at orders 4 / 12 / 18 / 29), regenerated in place by a committed script. Cell counts there are deterministic; timings are machine/run dependent.

Pre-built wheels are available for Linux, macOS, and Windows. The Rust extension is required and is included in all pip-installed wheels.

Installation

pip install mortie

For development builds with Rust, see BUILDING.md.

Rust crates

The Rust side is a cargo workspace with two members. mortie-core holds the packed-word codec — the bit layout, encode/decode, the order arithmetic, the decimal-string grammar, and the (depth, nested-ipix) ↔ packed-word pivot — and carries no dependencies at all, so a Rust project can take the codec without inheriting pyo3, numpy, rayon or a HEALPix crate. The root package mortie (library mortie_rustie) is the pyo3 extension this Python package compiles to; it depends on mortie-core and re-exports it, so every Rust path is unchanged. See BUILDING.md for the layout.

Neither crate is published to crates.io yet, so cargo add mortie-core finds nothing today; the crate is only available from this repository. Publishing mortie-core is tracked separately in issue #201.

Spatial Buffer

Mortie provides a morton_buffer function for expanding a set of morton cells by a configurable border ring. This is useful for... well, buffering.

import numpy as np
import mortie

# Convert coordinates to morton cells at order 6
cells = np.unique(mortie.geo2mort(lats, lons, order=6))

# Expand by 1-cell ring (8-connected neighbors)
border = mortie.morton_buffer(cells, k=1)
expanded = np.union1d(cells, border)

Latitude convention. Since 0.10 geo2mort and the coverage kernels take WGS84 geodetic latitude and map it to the authalic sphere, so cells are equal-area on the ellipsoid. Cell ids therefore differ from pre-0.10 mortie and from raw-spherical HEALPix libraries; pass latitude="geodetic-spherical" for the old behaviour. See docs/specification.md §9.

All input indices must be at the same order. The function returns only the new border cells, not the input cells themselves.

Polygon Coverage

morton_coverage computes the set of morton indices that cover a polygon defined by lat/lon vertices. It uses a top-down hierarchical descent over the HEALPix tree: starting from the 12 base cells it keeps cells inside the polygon, prunes cells outside, and refines cells the boundary passes through down to the requested order. Cost scales with the polygon's boundary, not its area — interior regions collapse to a few coarse cells, so a large but simple polygon is cheap. Vertex count still matters (a one-time O(V) edge/seed setup, plus per-boundary-cell work that grows with local edge density), but far more gently than the old O(cells × vertices) approach — a 1M-vertex polygon covers in ~1 s, roughly 40× faster than before.

import mortie

# Define polygon vertices (lat, lon in degrees)
lats = [40.0, 40.0, 50.0, 50.0]
lons = [-125.0, -115.0, -115.0, -125.0]

# Flat cover — every cell at order 6
cells = mortie.morton_coverage(lats, lons, order=6)

# Compact Multi-Order Coverage — coarse interior, fine boundary (usually far smaller)
moc = mortie.morton_coverage_moc(lats, lons, order=10)

# Adaptive boundary: stop at an angular tolerance, or cap the cell count
moc_tol = mortie.morton_coverage_moc(lats, lons, order=10, tolerance=0.5)   # degrees
moc_bud = mortie.morton_coverage_moc(lats, lons, order=10, max_cells=500)

The function handles concave polygons, antimeridian-crossing polygons, and polar regions. Multipart polygons and holes are supported by passing a list of rings (even-odd fill): disjoint parts are unioned and a nested ring carves a hole, so a donut is [outer, hole]. Helpers compress_moc (merge 4-sibling groups) and moc_to_order (densify a MOC to a flat order) round out the API. See docs/coverage_methods.md for the full method/precision/runtime trade-offs and a benchmark matrix.

The Moc object

mortie.moc(...) wraps the same cover as an object, so coverage geometry reads as geometry:

from mortie import moc

cali = moc(cali_geojson)      # multi-order coverage; no order argument
q    = moc(aoi_geojson)       # GeoJSON dicts, ring arrays, or a uint64 word array
assert cali.contains(q)
shards = q.to_order(9)        # fixed-order cast when a consumer's grid wants one

Two layers, and they stay separate. The free moc_* functions above are the kernel / batch layer — words in, words out, no wrapping cost — and they are unchanged and un-deprecated; the plural batch forms (mocs_and, mocs_intersect, mocs_to_orders, polygons_to_morton_mocs) stay function-shaped permanently. Moc is ergonomics only: a thin view over the canonical uint64 word array, where every method is a single delegation to one of those kernels. The array stays the interchange format — Moc.__morton_moc__() hands the words back, and any object exposing that dunder is accepted wherever a Moc is.

Vocabulary mirrors MOCpy where it applies, so the crosswalk is short:

Mind the two places where the vocabulary matches but the meaning does not. MOCpy's from_polygon(lon, lat, …) takes its coordinates in the opposite order to Moc.from_polygon(lats, lons, …); and MOCpy's MOC.contains is a point-in-MOC mask (deprecated there in favour of contains_lonlat), not the MOC-in-MOC test a.contains(b) is. a.to_order(n) also densifies when n is finer than the cover, which degrade_to_order(n).flatten() does not.

The predicates are cover algebra, not polygon algebra — both sides dilate their polygons to cell boundaries, so intersects can over-report near a boundary while a False stays decisive. docs/api/moc_object.md carries the conservative-direction table and the full constructor matrix.

mortie.moc is no longer a submodule. It is the constructor as of issue #196; import mortie.moc and from mortie.moc import x break. The flat package names (mortie.moc_to_order, mortie.compress_moc, …) are unchanged and are the supported spelling — see the CHANGELOG.

Dependencies

numpy. All HEALPix operations use the Rust-native healpix crate bundled in the compiled extension — no external HEALPix library is needed.

Funding

Initial funding of this work was supported by the ICESat-2 project science office, at the Laboratory for Cryospheric Sciences (NASA Goddard, Section 615).

References

[1] Youngren, Robert W., and Mikel D. Petty. "A multi-resolution HEALPix data structure for spherically mapped point data." Heliyon 3.6 (2017): e00332. doi: 10.1016/j.heliyon.2017.e00332