About geohash
Geohash is one of many encoding systems for geographic positions. Geohash positions have some advantages. It provides a short code instead of the two usual numbers for latitude and longitude.
The challenge
Given two numbers, the latitude and longitude, compute and return or print the geohash string of length 8. A longer geohash would give more accurate positions, here we use length 8. Latitudes and longitudes are given as floating point numbers (degrees). Latitudes are between -90 and +90 (south to north) and longitudes between -180 and +180 (west to east).
Algorithm with example
A geohash code is a base32 encoded bitstring. In this example the conversion goes the other way than the challenge, we convert geohash ezs42
into latitude and longitude. Geohashes uses a set of 32 digits represented by 5 bits. The 32 digits are 0 – 9
for the first 10 and the lower case letters between b – z
except i
, l
and o
for the next 22. That is: 0123456789bcdefghjkmnpqrstuvwxyz
.
The first char in ezs42
is e which is at the 0-indexed position 13, which has the 5 bits 01101. The chars have these bits:
e
→ 13 → 01101z
→ 31 → 11111s
→ 24 → 110004
→ 4 → 001002
→ 2 → 00010
When joining the bits we get 0110111111110000010000010.
Starting from left, the even bits (2nd, 4th, 6th, ...) are for latitude (101111001001) and the odd bits (1st, 3rd, 5th, ...) are for longitude (0111110000000).
With each bit we go left or right to narrow down the number by halving the range. The first bit of the longitude bits (0
) are used to decide if the longitude is between -180 – 0 or 0 – 180. Bit 0
means we go left, that is -180 – 0. The next bit of the longitude decides if we chose -180 – -90 or -90 – 0. Since it's 1
here we go right for the next range: -90 – 0. For every bit we go left(0) or right(1) halving the min-max range. When all bits are spent, we return the mid position (average) of the last min and max.
We repeat for latitude, except now we start at choosing between -90 – 0 and 0 – 90 with the first bit.
The latitude for 101111001001 becomes +42.605.
The longitude for 0111110000000 becomes -5.603.
This example is taken from https://en.wikipedia.org/wiki/Geohash#Algorithm_and_example which has a more visual walk-through.
When encoding 0° (equator or zero meridian) you can choose between 01111... and 10000... The http://geohash.co/ site have chosen 01111...
Test cases
(+48.8583, +2.2945) → u09tunqu # Eiffel Tower
(+40.68925, -74.04450) → dr5r7p62 # Statue of Liberty
(+29.9753, +31.1377) → stq4s8cf # The Great Sphinx at Giza
(-22.95191, -43.21044) → 75cm2txp # Statue of Christ, Brazil
(+71.17094, +25.78302) → usdkfsq8 # North Cape
(+90, +180) → zzzzzzzz # North Pole
(-90, -180) → 00000000 # South Pole
(+42.605, -5.603) → ezs42s00 # Léon, Spain from example above
More tests can be created or checked with http://geohash.co/ and Google Maps.
(GPS positions are also often written as degrees, arcminutes and arcseconds. The position of the Eiffel Tower is latitude 48° 51' 29.88" N, longitude 2° 17' 40.20" E. For north (N) and east (E) positive numbers are used so we get position [48 + 51/60 + 29.88/3600, 2 + 17/60 + 40.20/3600] = [+48.8583, +2.2945]. Geohash codes can be stored and indexed in databases for quick proximity searches. Nearby positions share the same code prefixes, but edge cases needs to be dealt with. A single index search on the geohash code on one or a small set of code prefixes is normally much quicker than using two indexes, i.e. one for latitude and one for longitude.)
01111...
or10000...
, or are both acceptable? There doesn't seem to be a way to encode "go straight to the middle". \$\endgroup\$