intepid » Latitude & Longitude to Quadtree

Latitude & Longitude to Quadtree

Saturday, June 10th, 2006

Someone asked me recently how to convert from a latitude & longitude to a Google Maps quadtree address (an URL to a particular image tile, as previously discussed in this entry), and I realized that I didn’t actually know. So I decided to work it out, and further realized that because it uses the Mercator projection it’s not as simple as I thought it would be.

One drawback of the Mercator projection is that it can never be complete, because at the upper and lower extremes of the map the magnification approaches infinity— which means that on an almost complete Mercator projection you would be able to read Santa’s newspaper, because it would appear as large as the Pacific Ocean!

For real world applications, if you want a map that’s not taller than it is wide you need to cut off the poles… but how much to cut off? Not really knowing this meant that I had to screw around comparing visual reference points (like the Empire State Building) in order to tweak the numbers to account for this, but I think I’ve got it almost right now. UPDATE: It was late, I was tired, and on second look I realized that the scale factor I had been zeroing in on (to seven decimal places) was in fact a natural one, in this case 1/2π. This should have been obvious to me from the equations in the Wikipedia entry. Also I know that the Mercator projection is conformal, which means you can’t go applying arbitrary scaling factors willy-nilly without screwing that up.

So go visit this page to see all the image tiles (from big to small) that contain a given set of coordinates, and feel free to view the source if you want to see the details of the conversion.

Javascript source:

              function GetQuadtreeAddress(long, lat)
            
              {
            
              var PI = 3.1415926535897;
            
              var digits = 18; // how many digits precision
            
              // now convert to normalized square coordinates
            
              // use standard equations to map into mercator projection
            
              var x = (180.0 + parseFloat(long)) / 360.0;
            
              var y = -parseFloat(lat) * PI / 180; // convert to radians
            
              y = 0.5 * Math.log((1+Math.sin(y)) / (1 - Math.sin(y)));
            
              y *= 1.0/(2 * PI); // scale factor from radians to normalized
            
              y += 0.5; // and make y range from 0 - 1
            
              var quad = "t"; // google addresses start with t
            
              var lookup = "qrts"; // tl tr bl br
            
              while (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;
            
              }

This entry was posted on Saturday, June 10th, 2006 at 12:45 am and is filed under Programming. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

9 Comments

sc says:
June 16th, 2006 at 8:19 pm
very good,if I have convert from a latitude & longitude to a Google Maps quadtree address (an URL to a particular image tile.How can I get all image tiles in one range from latitude to latitude and longitude to longitude.
sc says:
June 16th, 2006 at 8:44 pm
https://intepid.com/stuff/gmkh/
In that url,I think the tip in one image to show address is wrong!
mark says:
June 17th, 2006 at 2:02 pm
There are several ways to approach a range of images… one way is to step from one tile to the next using a fairly simple algorithm. Visit the sample page again and you will see a 3×3 image built using tiles, you can see how by checking the source.
sc says:
June 19th, 2006 at 9:58 pm
HI,Thanks for your source.
It is very good .
Can you tell me another ways,I want to learn it.
Why v=2 is disable now?
Do you know?
mark says:
June 19th, 2006 at 10:20 pm
v=2 is not a very useful projection for google, because it is not conformal, which means that the further you get from the equator, the more distortion there is.
sc says:
June 20th, 2006 at 2:00 pm
I see,Thanks.
sc says:
June 21st, 2006 at 8:06 pm
Can you tell me another ways to get a range ,I want to learn it.
mark says:
June 23rd, 2006 at 1:44 am
It’s hard to say without actually writing the code, but basically you want to expand on the 3×3 method used in the sample. You need to get the tile address for your top-left coord system, and then just step out as many tiles as you need.
andré says:
February 15th, 2008 at 10:27 am
hi,
many thanx for your work! it gives me good hints for a quads based generalizing algorithm i want to implement ontop of Google Maps (but totally independent of their quadrant system).

did you happen to check for tile borders coordinates in lat/long?

gretings from tyrol/austria

Latitude & Longitude to Quadtree

9 Comments

Leave a Comment