What are some efficient Geohash bounding box coverage algorithms?

Question

My requirement is:

Given a lat-lon bounding box, return a set of geohashes such that:

• The number of geohashes in the set should be small (1 to 5 geohash
  rectangles) if possible.
• The coverage should be as closed to the input lat-lon bounding box as possible. Tolerance about +/- 10%. It is ok to under-cover and/or over-cover a little bit.
• It should be efficient and can be carried out on a mobile device

I am most interested in the algorithm or conceptual approach. I plan to implement it in Java/Obj-C for Android and iOS if no open source implementation exists.

Answer 1

This java project on github https://github.com/davidmoten/geo has a documented algorithm for doing what you want. In particular it also works nicely at the limits of the geohash region (namely at the poles and at the -180/180 longitude line).

Keeping the number of geohashes small (1 to 5) as well as the tolerance to about 10% won't fly I'm afraid. With only 5 geohashes many rectangles will be covered with geohashes at 600% of the area of the target rectangle. In fact for the example below getting within 10% of the area requires 667 hashes!

Here's a table taken from the readme on the geo project site:

As a quick example, for a bounding box proportioned more a less like a screen with Schenectady NY and Hartford CT in USA at the corners:

Here are the hash counts for different hash lengths:

m is the size in square degrees of the total hashed area and a is the area of the bounding box.

length  numHashes m/a    
1       1         1694   
2       1         53     
3       4         6.6    
4       30        1.6    
5       667       1.08   
6       20227     1.02   

The algorithm used is efficient and the relevant code has no dependency on other artifacts so this won't be a problem to deploy to a mobile device supporting java (like Android).