Google Maps Deconstructed

Its finally time to apply our new knowledge about coordinate systems to Google Maps. Looking through the google maps newsgroups, you’ll see lots of questions like:

Let’s tackle the first two today, we’ll get to the third item in a future post (alas, it requires a bit more background information first).

From last time, we know that a geodetic coordinate system consists of a datum, a projection,
an origin, a unit system, two axes and perhaps an origin offset. Without further ado, this is what Google is doing:

  • Datum – WGS84 (I’m assuming this, I’ve never seen verification of it)
  • Projection – Mercator
  • Unit system – pixels (believe it or not)
  • Axes – standard east, non-standard south
  • Origin – Near the north pole on the international date line

Mercator Projection

How do I know they use a Mercator projection – by reading the obfuscated code of course! About six months ago I went looking through the code looking for “suspicious” looking equations. If you download the version 1 of the api, you’ll see this code around line 608 (reformatted so its readable):

F.prototype.getLatLng=function(a,b,c,d)
{
  if(!d)
  {
    d=new x(0,0)
  }
  d.x=(a-this.bitmapOrigo[c].x)/this.pixelsPerLonDegree[c]
  var e=(b-this.bitmapOrigo[c].y)/-this.pixelsPerLonRadian[c]
  d.y=(2*Math.atan(Math.exp(e))-Math.PI/2)/Fb
  return d
}

Based on the function name and the use of atan and exp functions this is clearly the projection code. But which one? Well, a quick look through Wikipedia shows its a Mercator projection. With the recent release of version 2 of the api, there is now a public GMercatorClass api (thus proving the point).

Yet there is more to this story. Let’s study the Mercator projection a bit more since its unusual. Here is some JavaScript that I’ve put together that translates from latitude/longitude to x/y and vice versa:

longToX: function(longitudeDegrees)
  {
    var longitude = Math.degreesToRadians(longitudeDegrees);
    return (this.radius * longitude);
  },

  latToY: function(latitudeDegrees)
  {
    var latitude = Math.degreesToRadians(latitudeDegrees);
    var y = this.radius/2.0 * 
            Math.log( (1.0 + Math.sin(latitude)) /
                      (1.0 - Math.sin(latitude)) );
    return y;
  },

  xToLong: function(x)
  {
    var longRadians = x/this.radius;
    var longDegrees = Math.radiansToDegrees(longRadians);
    
    /* The user could have panned around the world a lot of times.
    Lat long goes from -180 to 180.  So every time a user gets 
    to 181 we want to subtract 360 degrees.  Every time a user
    gets to -181 we want to add 360 degrees. */
       
    var rotations = Math.floor((longDegrees + 180)/360)
    var longitude = longDegrees - (rotations * 360)
    return longitude
  },

  yToLat: function(y)
  {
    var latitude =  (Math.PI/2) - 
                    (2 * Math.atan(
                       Math.exp(-1.0 * y / this.radius)));
    return Math.radiansToDegrees(latitude);
  }

Notice how this.radius plays a key part. Unlike most projections which map to a well defined part of the Earth (like British National Grid or the US State Plane system) you can use the Mercator projection to map to any sized surface you want.

Zoom Levels and Tiles

The next key to the puzzle is zoom levels. As you use Google Maps, one thing you’ll notice is that it has predefined zoom levels. In fact, there are 18 of them currently (the number of zoom levels has changed over time). Rummaging through the code a bit more, you’ll also see that Google Maps splits the world into tiles. Each tile is 256 pixels square and the number of tiles across at each zoom level is given by this formula:

 Math.pow(2, zoom)

So at zoom level 0, a single tile covers the Earth. At zoom level 1, four tiles cover the Earth (2 across by 2 down). At zoom level 2, sixteen tiles cover the earth (4 across by 4 down), etc. [Note – this is how version 2 of the api works, in version 1 the zoom levels are reversed].

Has a light bulb gone off in your head yet? Here’s the first trick Google uses – each zoom level maps to its own Mercator projection! The projection is calculated like this:

var TILE_SIZE = 256
var tiles = Math.pow(2, zoom)
var circumference = TILE_SIZE * tiles
var radius = circumference/ (2 * Math.PI)
var mercatorCoordinateSytem = createMercatorCS(radius)

Pixel Space

Yet there is still more. Remember we said that each tile is 256 pixels square? What that means is that Google is mapping latitude/longitude values into an imaginary pixel space. This is quite unusual. Most projections map latitude and longitude values into feet (for the US) or meters (for the rest of the world). A good example is the road atlas in your car. You want your road atlas to be in miles so you can quickly figure out the distance between where you are at and where you are going. If it told you it was 1.7 billion pixels from Denver to San Francisco you’d soon be buying someone else’s road atlas.

But on a computer screen pixels reign supreme. And by using pixels Google gets two big benefits. First, the map tiles, which are just bitmaps, are in pixels so using pixel space makes it much easier to line them up. Second, and this is more technical, it avoids having to convert pixels to feet or
meters. That’s problematic because a pixel is not a set size – it varies across monitors (let alone printers). Thus you usually “assume” a value (72 pixels per inch) knowing full well that your assumption is wrong. By working in pixels, and not feet or meters, Google avoids the issue entirely.

Origin Shift

But we’re still not done. If you’ve ever done any computer programming, you know that the top left of the screen is considered the origin (0,0) and y values increase downwards.

For Mercator projections, the natural origin is in the middle of the pixel space. Thus at zoom level one, it’s at 128,128 pixels (which maps in the real world to where the equator intersects the prime meridian in the Atlantic Ocean west of Africa). In addition, y-values increase upwards.

Wouldn’t it be easier though if the origin could be moved to the top left of the map and the y-value flipped? Well – from the last post time we already know how to shift the origin – use a false northing and easting. This is exactly what Google does:

var falseEasting = -1.0 * circumference/2.0,
var falseNorthing =  circumference/2.0, 

The false Easting is the circumference in pixel space divided by two and then multiplied by negative one. Thus it moves the origin to the left edge of the first tile. In the real world, its on the international date line in the Pacific ocean.

The false northing is simply the circumference divided by two. This moves the origin to slightly north of 85 degrees.

Which leaves us with one problem. Y values on a computer screen increase downwards, y values in the Mercator projection increase upwards. This can actually be solved quite easily – multiply all y values by negative 1.

Putting it All Together

So let’s review. Google divides the world into square bitmaps that are 256 square pixels. They use one bitmap to cover the world at zoom level 0, two bitmaps at zoom level 1, four bitmaps at zoom level 2, etc. For each zoom level, they create a Mercator projection, offset the origin to the west and north, and flip the y-axis.

Why do they do this? Because it means you can can divide the world into tiles, pre-render those tiles, and throw them onto a web server for fast access. Why is that important – because rending maps is SLOW. If you ever used an online GIS system or mapping site before Google you spent
most of your time waiting for the map to show up.

Rending is so slow because the amount of information on a map is staggering. Let’s take a typical Enterprise application – seeing if an item is in stock. Perhaps there’s a few tens of million of parts in your database and you want to look one up by name. With the appropriate indices, your database will return at most a few dozen records to you.

Now imagine you’re looking at a street map, say for Denver. Each one of those streets consists of multiple records in your database. Thus your database has tens, even hundreds, of millions of records. To render a map your database has to sift through them, and come up with the several
thousand relevant records that make up the map. So you’re already dealing with several orders of magnitude more information than with a standard database query. Next, a rendering engine needs to take those records and draw a map. This is a time consuming process because its usually done in software (2d vector graphics in GIS systems generally don’t make use of the built-in routines in graphics cards). Thus generating maps on the fly just isn’t fast. Although I can’t vouch for this information (so don’t hold me to it), I’ve heard that it takes Google several weeks to pre-render the United States to bitmaps (if anyone has more accurate information let me know).

Users Love It, Cartographers Hate It

So Google has done us all a great service by showing how to make interactive, fast maps online. So we’re all happy, right?

Nope, we’re not. Any cartographer worth his salt will tell you that using the Mercator projection for a world map is a terrible idea. Go look a the latToY equation above again. Now remember your high school trigonometry. What’s sin(90) equal? One. So the equation becomes undefined at the North pole. What does that mean? It means that as you move towards the poles the Mercator projection gets worse and worse and worse. The example people always point out is Greenland. It looks the same size of South America, but is really 8 times smaller. Ouch. For those who want to know more, here is a good writeup on the problem.

So, Google has traded ease of implementation for accuracy. In reality though, its probably ok since most of the world’s population doesn’t live near the poles so it doesn’t come into play. Also, when using Google Maps you’re usually closely zoomed in so the distortions become less important.

Scale

Let’s close this post with a word about scale. As you pan and zoom around on Google maps you’ll see that the scale in the bottom left constantly changes. This strikes most people as truly weird since they are used to maps with set scales. But there ain’t no such thing. The scale on projected
maps always varies across the map. Usually this doesn’t matter since the covered area is small so the variation in scale is miniscule. But when you can pan the whole world, then it starts to become noticeable.

Intuitively its easy to see why the scale changes. Let’s think about Google Maps zoom level 0. At zoom level 0 the world is fit into a 256 pixel wide image. But we know that the earth’s circumference is the largest at the equator and dwindles down to zero at the poles. So as you move north or south away from the equator, the Earth has to be “stretched” to fit into the 256 wide bitmap. Thus as you move north or south the scale gets larger and larger because the same number of pixels on the screen are showing you a larger and larger percentage of the Earth’s surface.

Ok – enough for today, this post is already long enough. Next time we’ll talk about how to convert from mouse (ie, screen) coordinates to latitude and longitude.

Update 1: Thanks to Mike Williams who provided some great feedback. I’ve made a couple of updates, described in the link, based on his suggestions.

Update 2: A number of people asked how I got the width variable in the radius calculation. Sorry, that was a typo. It was meant to be the circumference. Equation is now fixed.

Update 3: Thanks to Morten Nielsen for providing some clarity on the datum that Google and Microsoft both use. Above I mentioned that I thought the datum Google uses is WGS84 – but it is not.

Instead, quoting from Morten:

Google Maps / Virtual Earth / Yahoo Maps(?) all use a spherical datum based on WGS84. That is, it has the same center, orientation and scale as WGS84, but has no flattening. The radius of the sphere is the same as the semi-major axis of WGS84 (6378137 meters).

The map extents one can calculate using the formulas you provide gives you in degrees:

85. 05112877980659 to 180,85.05112877980659

…gives you a perfect square in Mercator units of size:

-20037508.342789, -20037508.342789 to 20037508.342789, 20037508.342789

I’m guessing it is more likely that this is the real reason behind the weird ‘85.05112877980659’, and the other formula just follows from this.

Someone in your comments got a different extent which is the extent that you get using WGS84 (which is several miles off at the top and bottom).

Having a perfect equal-sided square also makes a lot more sense, since this also goes for the map tiles in pixel units.

Update 4: Agreement from Melita Kennedy and David Burrows that Google Maps and Virtual Earth use spherical equations for the Mercator projection. The correct proj4 settings are:

+proj=merc +latts=0 +lon0=0 +k=1.0 +x0=0 +y0=0
+a=6378137.0 +b=6378137.0 +units=m

Note this is different than using the ellipsoidal equations which would be:

+proj=merc +latts=0 +lon0=0 +k=1.0 +x0=0 +y0=0
+ellps=WGS84 +datum=WGS84 +units=m no_defs 
  1. Brian Flood
    May 3, 2006

    Great post!

    Reply
  2. Charlie
    May 3, 2006

    Thanks Brian. Think your blog is great by the way – I enjoy reading it.

    Reply
  3. p3n
    May 5, 2006

    thx

    Reply
  4. gisdudester
    May 8, 2006

    this was very informative. considering I have a certificate in GIS, i still get Geographic Coordinates Systems and Projected Coordinate Systems mixed up. but these are very logical and progress in an intuitive way.

    Reply
  5. Charlie Savage –
    June 30, 2006

    Hi Charlie,

    I think your wgs84 assumption is accurate. I have reproduced Google’s top level tile (world in 256×256) using mapserver and this proj.4 definition:

    World Mercator
    <54004> +proj=merc +lat_ts=0 +lon_0=0 +k=1.000000 +x_0=0 +y_0=0 +ellps=WGS84 +datum=WGS84 +units=m no_defs <>

    and with the following extents:

    -20037508.342789, -19994875.249796, 20037508.342789, 19994875.249796

    which is reprojected from the lonlat extents -180,-85.05112877980660,180,85.05112877980660

    The image produced is essentially identical (less antialiasing and taking some generalization into account).

    Cheers

    Paul

    Reply
  6. Charlie Savage –
    June 30, 2006

    Hi Paul,

    That’s great, thanks for the verification. I suspected it was true for the US since I can take GPS tracks and overlay them perfectly ontop of Google Maps (its pretty cool).

    What data are you generating the tiles from – Tiger?

    Reply
  7. July 8, 2006

    The reason Google Maps uses the Mercator projection isn’t because it’s easy to implement. One of the major features, arguably the primary one, of GMaps is providing directions from point A to point B. Usability studies showed that the angle of turns is very important, much more than displayed distance. The Mercator projection preserves angles.

    I picked this information up from Bret Taylor, who gave a tech talk on GMaps during my visit to Google two weeks ago.

    Reply
  8. Charlie Savage –
    July 9, 2006

    Hi Nikolas,

    Thanks for the comment – that’s really interesting. Makes me curious how far you’d have to be zoomed out (i.e, how far are you travelling) for the angles to be distorted – have to check that out.

    Google could have used other conformal projections (angle preserving) – I seems to me that the Mercator projection does make implementation easier. Was there any mention of that in the talk?

    Reply
  9. James
    February 20, 2008

    Hi There,

    Does anyone know how to calculate the bitmap x,y cordinates in a tile given latitude and longitude?

    Cheers!

    James

    Reply
  10. naimulah
    March 20, 2008

    very informative and interesting article you have written.
    Thanks Charlie.

    Keep up the good work.

    Reply
  11. June 21, 2008

    Mercator doresn’t distort angles as you zoom out; it bends straight lines (i.e. great circles) instead.

    They *could* have used a Mercator projection based on the center of your screen, but that’d require a new set of tiles for every PoV, or (assuming a current large screen with room for 5*8 tiles), 40 times the computing power required to render these things, and 40 times the storage requirement. Which is already *huge*.

    They get around the problem in Google Earth by distorting the tiles on the client machine, but you can’t do that in a web server.

    Reply
  12. October 22, 2008

    One problem. The maps at the higher zoom levels are not horribly distored.

    Case in point, Barrow Alaska, 71.3 lat, -156.8 lon.

    If you look at the images and other things which are supposed to be square, they are square. cos(70) is under .5 so they should be badly stretched sideways if it was true Mercator.

    This is also true of cities and counties laid out on a grid (a street every mile) – they look square and not like rectangles or rhombuses. Mercator projections of the states near the Canadian border should have this very visible but are not.

    I assume a 1-mile north = 1 mile east map of barrow (or MI or MN) looks like the image on google maps and google earth (whose ruler says 1 mile for the same distance north or east).

    Something is wrong, or at the highest zooms something more is being done. It all works well, but is not a mercator projection at some point.

    Reply
  13. cc
    November 16, 2008

    great post, thanks!

    Reply

Leave a Reply

Your email address will not be published.

Top