geohash.gno

  1// Package geohash encodes a latitude/longitude pair into the short base32
  2// string known as a geohash, decodes one back into the cell it names, and
  3// walks from a cell to the eight around it.
  4//
  5// A geohash is a prefix code: every character narrows the box, so two places
  6// that share a long prefix are close together, and truncating a hash zooms
  7// out. That is the whole reason to use one on chain, where an avl tree keyed
  8// by geohash gives a cheap "everything near here" range scan without storing
  9// any geometry: Get the prefix, iterate, done.
 10//
 11//	hash, _ := geohash.Encode(42.6, -5.6, 5)   // "ezs42"
 12//	box, _ := geohash.DecodeBox("ezs42")       // the cell it names
 13//	north, _ := geohash.Neighbor("ezs42", geohash.North)
 14//
 15// The alphabet is the standard one and deliberately drops a, i, l and o, so a
 16// hash survives being read aloud or written down. Anything outside it is
 17// refused rather than quietly skipped.
 18//
 19// Everything here is pure arithmetic on exact binary fractions: both world
 20// ranges are powers of two divided by powers of two, so every box bound is
 21// representable in a float64 and two identical calls can never disagree. No
 22// map is iterated and no value is rounded, which is what makes a Render built
 23// on this deterministic.
 24//
 25// A live demo of this package is at
 26// [r/moul/x/daily/geohashdemo](/r/moul/x/daily/geohashdemo/v0).
 27package geohash
 28
 29import "errors"
 30
 31// Alphabet is the standard geohash base32 alphabet. It omits a, i, l and o so
 32// that a hash read aloud or copied by hand stays unambiguous.
 33const Alphabet = "0123456789bcdefghjkmnpqrstuvwxyz"
 34
 35// MaxPrecision is the longest hash this package will produce or accept: 12
 36// characters, 60 bits, a cell well under a millimetre across. Past that the
 37// extra characters say nothing a float64 can still distinguish.
 38const MaxPrecision = 12
 39
 40var (
 41	// ErrPrecision is returned by Encode for a length outside 1..MaxPrecision.
 42	ErrPrecision = errors.New("geohash: precision out of range")
 43	// ErrLatitude is returned by Encode for a latitude outside -90..90.
 44	ErrLatitude = errors.New("geohash: latitude out of range")
 45	// ErrLongitude is returned by Encode for a longitude outside -180..180.
 46	ErrLongitude = errors.New("geohash: longitude out of range")
 47	// ErrEmpty is returned when a hash is required and none was given.
 48	ErrEmpty = errors.New("geohash: empty hash")
 49	// ErrTooLong is returned for a hash longer than MaxPrecision.
 50	ErrTooLong = errors.New("geohash: hash longer than the maximum precision")
 51	// ErrInvalidChar is returned for a character outside Alphabet, which
 52	// includes the four letters the alphabet deliberately leaves out.
 53	ErrInvalidChar = errors.New("geohash: character is not in the geohash alphabet")
 54	// ErrDirection is returned by Neighbor for a Direction it does not know.
 55	ErrDirection = errors.New("geohash: unknown direction")
 56	// ErrNoNeighbor is returned by Neighbor when the step leaves the world:
 57	// north of the top row, or south of the bottom one. Longitude wraps and
 58	// never produces this.
 59	ErrNoNeighbor = errors.New("geohash: no neighbour in that direction")
 60)
 61
 62// Box is the rectangle of latitudes and longitudes a geohash names. A geohash
 63// is a box, never a point, and the shorter the hash the larger the box.
 64type Box struct {
 65	MinLat, MaxLat float64
 66	MinLon, MaxLon float64
 67}
 68
 69// Center returns the midpoint of the box, which is what Decode reports.
 70func (b Box) Center() (lat, lon float64) {
 71	return (b.MinLat + b.MaxLat) / 2, (b.MinLon + b.MaxLon) / 2
 72}
 73
 74// Contains reports whether a point falls inside the box. The lower and left
 75// edges belong to the box and the upper and right ones do not, matching how
 76// Encode assigns a point sitting exactly on a midpoint.
 77func (b Box) Contains(lat, lon float64) bool {
 78	return lat >= b.MinLat && lat < b.MaxLat && lon >= b.MinLon && lon < b.MaxLon
 79}
 80
 81// HeightDeg is the box's north-south extent in degrees.
 82func (b Box) HeightDeg() float64 { return b.MaxLat - b.MinLat }
 83
 84// WidthDeg is the box's east-west extent in degrees.
 85func (b Box) WidthDeg() float64 { return b.MaxLon - b.MinLon }
 86
 87// Direction names one of the eight cells around a geohash. The values are
 88// ordered clockwise from north, so adding four modulo eight is the reverse.
 89type Direction int
 90
 91// The eight directions, clockwise from north.
 92const (
 93	North Direction = iota
 94	NorthEast
 95	East
 96	SouthEast
 97	South
 98	SouthWest
 99	West
100	NorthWest
101)
102
103// String returns the lowercase hyphenated name, or "unknown" for a value that
104// is not one of the eight.
105func (d Direction) String() string {
106	switch d {
107	case North:
108		return "north"
109	case NorthEast:
110		return "north-east"
111	case East:
112		return "east"
113	case SouthEast:
114		return "south-east"
115	case South:
116		return "south"
117	case SouthWest:
118		return "south-west"
119	case West:
120		return "west"
121	case NorthWest:
122		return "north-west"
123	}
124	return "unknown"
125}
126
127// step returns the latitude and longitude offsets, in whole cells, for a
128// direction. The second result is false for a direction that is not one of
129// the eight.
130func (d Direction) step() (dLat, dLon float64, ok bool) {
131	switch d {
132	case North:
133		return 1, 0, true
134	case NorthEast:
135		return 1, 1, true
136	case East:
137		return 0, 1, true
138	case SouthEast:
139		return -1, 1, true
140	case South:
141		return -1, 0, true
142	case SouthWest:
143		return -1, -1, true
144	case West:
145		return 0, -1, true
146	case NorthWest:
147		return 1, -1, true
148	}
149	return 0, 0, false
150}
151
152// Encode returns the geohash of a point, precision characters long.
153//
154// Longitude takes the first bit and the two alternate, so an odd number of
155// characters gives longitude one bit more than latitude and the cell comes out
156// roughly square in degrees. A point sitting exactly on a dividing line goes
157// to the upper, or eastern, half.
158func Encode(lat, lon float64, precision int) (string, error) {
159	if precision < 1 || precision > MaxPrecision {
160		return "", ErrPrecision
161	}
162	if lat < -90 || lat > 90 {
163		return "", ErrLatitude
164	}
165	if lon < -180 || lon > 180 {
166		return "", ErrLongitude
167	}
168
169	latMin, latMax := -90.0, 90.0
170	lonMin, lonMax := -180.0, 180.0
171
172	out := make([]byte, 0, precision)
173	ch, bit, even := 0, 0, true
174	for len(out) < precision {
175		if even {
176			mid := (lonMin + lonMax) / 2
177			if lon >= mid {
178				ch |= 1 << uint(4-bit)
179				lonMin = mid
180			} else {
181				lonMax = mid
182			}
183		} else {
184			mid := (latMin + latMax) / 2
185			if lat >= mid {
186				ch |= 1 << uint(4-bit)
187				latMin = mid
188			} else {
189				latMax = mid
190			}
191		}
192		even = !even
193		if bit < 4 {
194			bit++
195			continue
196		}
197		out = append(out, Alphabet[ch])
198		ch, bit = 0, 0
199	}
200	return string(out), nil
201}
202
203// Decode returns the centre of the cell a geohash names. The centre is the
204// best single point a hash can give: the cell itself is what was encoded, and
205// DecodeBox is how to ask how big it is.
206func Decode(hash string) (lat, lon float64, err error) {
207	b, err := DecodeBox(hash)
208	if err != nil {
209		return 0, 0, err
210	}
211	lat, lon = b.Center()
212	return lat, lon, nil
213}
214
215// DecodeBox returns the cell a geohash names.
216func DecodeBox(hash string) (Box, error) {
217	if hash == "" {
218		return Box{}, ErrEmpty
219	}
220	if len(hash) > MaxPrecision {
221		return Box{}, ErrTooLong
222	}
223
224	b := Box{MinLat: -90, MaxLat: 90, MinLon: -180, MaxLon: 180}
225	even := true
226	for i := 0; i < len(hash); i++ {
227		v, ok := symbol(hash[i])
228		if !ok {
229			return Box{}, ErrInvalidChar
230		}
231		for _, mask := range [5]int{16, 8, 4, 2, 1} {
232			if even {
233				mid := (b.MinLon + b.MaxLon) / 2
234				if v&mask != 0 {
235					b.MinLon = mid
236				} else {
237					b.MaxLon = mid
238				}
239			} else {
240				mid := (b.MinLat + b.MaxLat) / 2
241				if v&mask != 0 {
242					b.MinLat = mid
243				} else {
244					b.MaxLat = mid
245				}
246			}
247			even = !even
248		}
249	}
250	return b, nil
251}
252
253// Neighbor returns the geohash of the cell one step away, at the same
254// precision.
255//
256// It works by walking one whole cell from the centre and re-encoding, which is
257// exact: every cell bound is a binary fraction, so the step lands on another
258// centre rather than near one.
259//
260// Longitude wraps, so the cell east of the last column is the first column
261// again: the antimeridian is a line on a map, not an edge of the world. The
262// classic lookup-table implementations report nothing there, which is a
263// property of the tables and not of the globe. Latitude genuinely stops, and
264// a step past a pole returns ErrNoNeighbor.
265func Neighbor(hash string, d Direction) (string, error) {
266	dLat, dLon, ok := d.step()
267	if !ok {
268		return "", ErrDirection
269	}
270	b, err := DecodeBox(hash)
271	if err != nil {
272		return "", err
273	}
274	lat, lon := b.Center()
275
276	lat += dLat * b.HeightDeg()
277	if lat > 90 || lat < -90 {
278		return "", ErrNoNeighbor
279	}
280	lon += dLon * b.WidthDeg()
281	if lon > 180 {
282		lon -= 360
283	}
284	if lon < -180 {
285		lon += 360
286	}
287	return Encode(lat, lon, len(hash))
288}
289
290// Neighbors returns the cells around a geohash, clockwise from north.
291//
292// The result is short rather than padded when a direction has no cell, which
293// only happens at the poles: a caller iterating the result never has to filter
294// an empty string out of it.
295func Neighbors(hash string) ([]string, error) {
296	if _, err := DecodeBox(hash); err != nil {
297		return nil, err
298	}
299	out := make([]string, 0, 8)
300	for d := North; d <= NorthWest; d++ {
301		n, err := Neighbor(hash, d)
302		if err == ErrNoNeighbor {
303			continue
304		}
305		if err != nil {
306			return nil, err
307		}
308		out = append(out, n)
309	}
310	return out, nil
311}
312
313// symbol maps an alphabet character to its five-bit value. It is a linear scan
314// rather than a map because the alphabet is 32 bytes long and a package-level
315// map would be one more object for every realm that imports this.
316func symbol(c byte) (int, bool) {
317	for i := 0; i < len(Alphabet); i++ {
318		if Alphabet[i] == c {
319			return i, true
320		}
321	}
322	return 0, false
323}