Geohash

:"Not to be confused with the random coordinate generator described in xkcd."

Geohash is a latitude/longitude geocode system inventedby Gustavo Niemeyer when writing the web service at "geohash.org", andput into the public domain.

Geohashes offer properties like arbitrary precision and the possibility ofgradually removing characters from the end of the code to reduce its size(and gradually lose precision).

As a consequence of the gradual precision degradation, nearby places willoften present similar prefixes.

Service

The purpose of the "geohash.org" service, launched in February 2008, is tooffer short URLs which uniquely identifypositions on the Earth, so that referencing them in emails,
forums, and websites is more convenient.

To obtain the Geohash, the user provides an address to be geocoded,or latitude and longitude coordinates, in a single input box (most commonlyused formats for latitude and longitude pairs are accepted), and performs the request.

Besides showing the latitude and longitude corresponding to the given Geohash,users who navigate to a Geohash at geohash.org are also presented with anembedded map, and may download a GPX file, or transferthe waypoint directly to certain GPS receivers. Links are also providedto external sites that may provide further details around the specifiedlocation.

Example

Using the hash "ezs42" as an example, here is how it is decoded into a decimal latitude and longtitude

Decode from base 32

The first step is decoding it from base 32 using the following character

This operation results in the bits 01101 11111 11000 00100 00010. Assuming that countingstarts at 0 in the left side, and that 0 is even, the even bits are taken for the longitudecode (0111110000000), while the odd bits are taken for the latitude code (101111001001).

Decode binary to decimal

Each binary code is then used in a series of divisions, considering one bit at a time,again from the left to the right side. For the latitude value, the interval-90 to +90 is divided by 2, producing two intervals: -90 to 0, and 0 to +90. Sincethe first bit is 1, the higher interval is chosen, and becomes the current interval.The procedure is repeated for all bits in the code. Finally, the latitude value isthe center of the resulting interval. Longitudes are processed in an equivalent way,keeping in mind that the initial interval is -180 to +180.

Finishing the procedure should yield approximately latitude 42.6 andlongitude -5.6.

Worked example

Here's a worked example decoding 101111001001 into 42.6. To start with, we know the latitude is somewhere in the range -90 to 90. With no bits, we'd have to guess the latitude was 0, giving us an error of +/- 90. With one bit, we can decide whether its in the range -90 to 0, or 0 to 90. The first bit is high, so we know our latitude is somewhere between 0 and 90. Without any more bits, we'd guess the latitude was 45, giving us an error of +/-45

Each subsequent bit halves this error. This table shows the effect of each bit. At each stage, the relevant half of the range is highlighted in green - a low bit selects the lower range, a high bit the upper range.

The last column shows the latitude, simply the mean value of the range. Each subsequent bit makes this value more precise.

(The numbers in the above table have been rounded to 3 decimal places for clarity).

License and patents

The Geohash geocode has been put in the public domain by its inventor inthe public announcement date, in February 26th, 2008. [ [http://forums.groundspeak.com/GC/index.php?showtopic=186412 geohash.org announcement post in groundspeak.com forum] ]

While comparable algorithms have been successfullypatented [ [http://www.freepatentsonline.com/20050023524.html Compact text encoding of latitude/longitude coordinates - Patent 20050023524] ] andhad copyright claimed upon [ [http://www.gps-practice-and-fun.com/nacgeo.html#Microsoft Does Microsoft Infringe the Natural Area Coding System?] ] [ [http://www.nacgeo.com/nacsite/licensing/ The Natural Area Coding System - Legal and Licensing] ] , GeoHash is based on an entirely different algorithm and approach.

ee also

*Morton number (number theory)
*Natural Area Code
*Maidenhead Locator System

External links

* [http://geohash.org geohash.org]
* [http://search.cpan.org/dist/Net-Geohash/ Perl module to interact with geohash.org]
* [http://github.com/davetroy/geohash-js/ Javascript module for encoding and decoding geohashes without interacting with geohash.org] and [http://openlocation.org/geohash/geohash-js/ Demo]
* [http://geohash.rubyforge.org Ruby gem for encoding and decoding geohashes without interacting with geohash.org]
* [http://search.cpan.org/dist/Geo-Hash/ Perl module for encoding and decoding geohashes without interacting with geohash.org]
* [http://blog.dixo.net/downloads/geohash-php-class/ PHP class for encoding and decoding geohashes without interacting with geohash.org]
* [http://pypi.python.org/pypi/Geohash/ Python module for encoding and decoding geohashes without interacting with geohash.org]
* [http://lists.burri.to/pipermail/geowanking/2005-February/001399.html Proposal for a similar encoding and associated 'geo' URL scheme]

References