Lukas Murdock
Subscribe for updates and more.

Geohash

Planted 02023-05-04

Geohash: What and Why

Geohash is a public domain geocode system based on the Morton Z-order curve.

Critical Feature: Proximity search with prefix property; Geohashing guarantees the longer a shared prefix between two hashes the closer they are.

Feature: Arbitrarily precise cells; longer strings are more precise; shorter strings are less precise.

Caveat: However, two areas can be close together but have entirely different Geohashes; this is due to how the geohash algorithm segments latitude/longitude coordinates into buckets. To solve this you can query neighboring buckets as well.

Encoding a latitude, longitude pair to a string geohash is a three step process:

  1. Quantize latitude and longitude to 32-bit integers
  2. Bit-interleave integers to produce 64-bit value (the integer geohash)
  3. Base32 encode (with custom alphabet) to produce string geohash

Example common flow of getting Geohash from Address:

  1. Address → Google Geocoding Service → [Latitude, Longitude]
  2. [Latitude, Longitude] → Geohash function → encoded base32 string

Filter data by proximity

  1. Given [Latitude, Longitude, Proximity]
  2. Approximate a cell containing the search area (approximate bounding)
    • Lat/lon: the given lat/lon is bounding circle center and proximity is approximated by bounding circle radius
    • Geohash: the given lat/lon is located inside calculated geohash (but not centered) and proximity is approximated by either
      1. reducing precision (widens bounding area)
      2. generating neighbor bounding areas
  3. Search
    • Lat/lon: calculate and search within bounding circle [latitudeMin, latitudeMax, longitudeMin, longitudeMax]
    • Geohash: search where geohash starts with bounding precision and (optionally) neighboring bounding precisions

References on Geohash

Geohash in Code

Other geocode systems

Uber H3: Hexagonal hierarchical geospatial indexing system

Example flow of search by radius:

  1. Given [Latitude, Longitude, SearchRadius]
  2. Calculate grid disk (array of h3Indexes)
    • Calculate grid disk of radius based on average cell edge length
    • Calculate grid disk based on the search area
  3. Search for indexes between the minimum and maximum grid disk h3Indexes

Docs

References on H3

https://gis.utah.gov/using-h3-hexes/

Minimum bounding rectangle

In computational geometry, the minimum bounding rectangle (MBR), also known as bounding box (BBOX) or envelope, is given a set of 2-dimensional objects: min(x), max(x), min(y), max(y).

Rel