Hex-tree GPS Encoding

I had the pleasure of attending PyWebSF and struck up a conversation with my old friend Tadhg about the idea of creating a web service (a’la http://bit.ly) that would provide a unique short GPS “tag” for any arbitrary GPS location. You can read Tadhg’s excellent accounting of the discussion here.

I didn’t write any code (yet) but I did have an idea that is a variation on the QuadTree solution that I proposed during the conversation. I call it Hex-tree and have no idea if it’s already been done, but I think it will create very short location identifiers algorithmically.

zoom level 0 At zoom level zero (on a standard Mercator-projection of the globe), we see that every place on earth can be crudely described by the numbers 0-F (hexidecimal). Suppose we are interested in specifying the precise location of San Francisco, CA. It’s in tile 4, so our address is going to start with a “4”. Already we can see that the first digit of a HexGPS coordinate contains enough lat/lon information to know what continent we are referring to.

zoom level 1 Zooming in to tile 4, we see the eastern pacific tile is now recursively subdivided, and that our target is in tile 6. The address so far is “46”.

zoom level 2 Zooming in again (and wishing I had used a higher-res map to begin with), we see that San Francisco is in tile 5. Our address is now “465”. The notion in this system is that you can visually determine if two addresses are nearby by just looking at the initial similarities of the two strings. Two addresses that started with “465…” would be known to be within 100 miles of each other (approximately). If you compare “465…” with “46E…” you can tell that they are within 500 miles of each other.

Advertisements