I was born at Tsrrtrsqsqqqrqrtsst

[Last updated July 2011]

I’ve been playing around with the marvellous Google Earth and Google Maps, and just noticed how elegant the system for addressing image tiles is [specifically from Google Maps].

Google Maps now offers a satellite view as well as a map view, and does so using the former Keyhole database. The view is built using tiles– 256 pixel square JPEGs fetched from the the kh.google.com server.

As of this writing, the image URLs take the form:

http://khm.google.com/kh?v=version&t=address

version is between 85 and 88, and I’ve no idea why. It doesn’t really seem to affect the projection like it once did, but it does seem to change the particular images used in some cases. It may be simply a number which must be raised occasionally to correspond with newer data– eg it once accepted 45 as a valid argument and now it doesn’t. Unfortunately leaving it out altogether results in a 404 error.

quadtree recursive subdivisionaddress is a short string of letters encoding the location of a particular map square. The addressing mode is quite elegant, with the world recursively quartered until the desired detail level is reached. This simple heirarchical structure is known as a quadtree, and is commonly used in computer graphics. For whatever reason, Google labels the four quadrants q, r, s & t.

The topmost tile contains the entire world map, and is referenced with an address of t. Adding an s to this selects the lower-right quadrant of the map, and adding a further r selects the upper-right of that map, resulting in a tile containing most of Australasia. Each time an extra letter is added, we descend into a new quadrant, and this continues until the maximum detail is reached. So, for example, the hospital where I was born can be uniquely addressed [to within a hundred metres or so] using the URL:

http://khm.google.com/kh?v=88&t=tsrrtrsqsqqqrqrtsst

Converting between Quadtree addresses and Longitude/Latitude

This page contains Javascript to returns all tiles containing a particular location, with each yellow quadrant marking the region occupied by the subsequent map. If you’d like to copy the code you can view the page source, or simply use the excerpts shown below. The first two functions are based on equations from Wikipedia’s entry on the Mercator Projection.

function MercatorToNormal(y)
{
y = -y * Math.PI / 180; // convert to radians
y = Math.sin(y);
y = (1+y)/(1-y);
y = 0.5 * Math.log(y);
y *= 1.0 / (2 * Math.PI); // scale factor from radians to normalized
y += 0.5; // and make y range from 0 – 1
return y;
}
function NormalToMercator(y)
{
y -= 0.5;
y *= 2 * Math.PI;
y = Math.exp(y * 2);
y = (y-1)/(y+1);
y = Math.asin(y);
y = y * –180/Math.PI;
return y;
}
function GetCoordinatesFromAddress(str)
{
// get normalized coordinate first
var x = 0.0;
var y = 0.0;
var scale = 1.0;
str = str.toLowerCase();
str = str.substr(1); // skip the first character
while (str.length > 0)
{
scale *= 0.5;
var c = str.charAt(0); // remove first character
if (c == ‘r’ || c == ‘s’)
{
x += scale;
}
if (c == ‘t’ || c == ‘s’)
{
y += scale;
}
str = str.substr(1);
}
var ret = new Object();
ret.longmin = (x – 0.5) * 360;
ret.latmin = NormalToMercator(y);
ret.longmax = (x + scale – 0.5) * 360;
ret.latmax = NormalToMercator(y + scale);
ret.long = (x + scale * 0.5 0.5) * 360;
ret.lat = NormalToMercator(y + scale * 0.5);
return ret;
}
function GetQuadtreeAddress(long, lat)
{
// now convert to normalized square coordinates
// use standard equations to map into mercator projection
var x = (180.0 + parseFloat(long)) / 360.0;
var y = MercatorToNormal(parseFloat(lat));
var quad = “t”; // google addresses start with t
var lookup = “qrts”; // tl tr bl br
for (digits = 0; digits < 24; digits++)
{
// make sure we only look at fractional part
x -= Math.floor(x);
y -= Math.floor(y);
quad = quad + lookup.substr((x>=0.5?1:0) + (y>=0.5?2:0), 1);
// now descend into that square
x *= 2;
y *= 2;
}
return quad;
}