Writing your own Geohash algorthim, part 2

Ok, so earlier, I started investigating how to write a geohash algorithm in Javascript. I’m sure you’ve been waiting in eager for the results. Well dear readers, now is the time.

Below, is a geohash algorithm, based on the Maidenhead Locator system but with a few tweaks.

Firstly to get more accuracy with less characters, I replaced the complicated Maidenhead codes for different characters with one set of 64 different characters for each character. They range from the lowercase alphabet to the uppercase, then the base 10 numbers, and the greater than and less than symbols.

With this method, effectively the globe is split into 4096 squares (64×64) and then the longitude and latitude are interleaved together, so every odd character is Longitude and every even character is Latitude. The process is then recursive, based on the level of precision you set. So after the first square is picked – 2 characters, the selected square is then split again into 4096 squares and stored as another 2 characters, this goes on so on and so forth.

A 1 degree arc of the earth’s surface is roughly 111,000 meters long, which means you need 5 decimal places to get around 1 meter worth of accuracy with your location. The following code takes a 5 decimal place longitude and effectively transforms it into a geohash and back again.

The result it, we can take the latitude, 47.64932, convert it into a geohash of kwGK and then back again to 47.64932.

In part 3, I will looking at creating a formal proof of this algorithm, possibly using induction proofs.

var lat,
latMin = -90;
latMax = 90;
base64A = "<>0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
lat = 47.64932;
reduce = function(boundaries, bucketSize, value, precision, geohash) {
	boundaries = calculateBoundaries(boundaries, bucketSize, geohash);
	var bucket = Math.floor((value - boundaries.min)*(bucketSize/(boundaries.max-boundaries.min)));
	return precision-1 > 0 ? base64A[bucket] + reduce(boundaries, bucketSize, value, precision-1, base64A[bucket]) : base64A[bucket];
calculateBoundaries = function(boundaries, bucketSize, geohash) {
	if(geohash.length > 0) { 
		var lastGeoHash = base64A.indexOf(geohash[geohash.length-1]);
		var range = boundaries.max-boundaries.min;
		boundaries.max = (lastGeoHash+1)*(range/bucketSize)+boundaries.min;
		boundaries.min = (lastGeoHash*(range/bucketSize))+boundaries.min;
	return boundaries;
reverseGeoHash = function(boundaries, bucketSize, geohash) {
	for(var i = 0; i < geoHash.length; i++) {
		boundaries = calculateBoundaries(boundaries, bucketSize, geohash[i]);
	return Math.round((((boundaries.max-boundaries.min)/2)+boundaries.min)*100000)/100000;

geoHash = reduce({min:latMin, max:latMax}, base64A.length, lat, 4, 0);
reversed = reverseGeoHash({min:latMin, max:latMax}, base64A.length, geoHash);		
console.log(geoHash, reversed, lat);