Geohash, quadtree, and H3

Spatial indexes generate candidates. Exact geometry or geography predicates decide the answer. Treating a cell match as the final radius or polygon result creates boundary errors.

Coordinate contract

GeoJSON uses WGS 84 longitude, latitude coordinates in decimal degrees. Distance APIs must say whether inputs are planar geometry units or geography meters and whether they use a sphere or spheroid. Validate axis order, CRS, longitude wrapping, and antimeridian behavior.

Geohash

A geohash prefix identifies a latitude/longitude rectangle. Longer prefixes refine the rectangle, but a nearby point can lie across a cell boundary with no shared long prefix. Radius search therefore covers the center cell plus every neighboring/intersecting cell required by the query, unions candidates, and applies an exact distance test.

Rectangle size and physical area vary with latitude. Select precision from measured density and candidate fanout, not one universal "meters per character" claim.

Quadtree

A quadtree recursively splits a region into four children. Adaptive trees refine dense or geometrically complex regions and stop in sparse regions. Complexity depends on distribution, maximum depth, query shape, and output size. Polygon/radius queries visit every intersecting leaf, then run an exact predicate.

H3

H3 partitions the globe hierarchically, mostly into hexagons, with 12 pentagons and distortion. Cells at one resolution do not have exactly equal area. Parent-child relationships are exact logically, while geometric containment can be approximate.

H3 polygon conversion APIs have documented containment modes. A centroid-contained set is not automatically a conservative polygon cover. Grid traversal must handle pentagon distortion and possible API failure modes.

Exact verification and updates

Use the cell index for candidate generation and a database geography predicate such as ST_DWithin for authoritative distance. Keep versioned memberships for moving objects, atomically publish the new version, and deduplicate candidates before filtering.

Diagram scenarios

The animation covers geohash neighbor expansion, adaptive quadtree traversal, H3 containment/pentagon boundaries, antimeridian handling, and versioned moving-object updates.

Related case

Interactive scenarios