Tutorial: Map Projections

When we look at maps, we are in fact looking at a 2D representation of the globe. If you stop to think about it, this is not as straightforward as it may seem at first. How would you display a perfect sphere in 3D in the 2D plane? In particular, how would you do it if you can use only a bounded square or rectangular portion of the plane? Drawing maps is even harder than this, because the earth is not a perfect sphere, but closer to an ellipsoid.

In the past, people have proposed many different ways of representing the earth on a map. These are called map projections. Wikipedia has a good overview of many of them. When you visit OpenStreetMap, Google Maps, Bing Maps, Maps on your iOS device, navigation in your car, … You are looking at a globe that has been projected into the 2D plane using the Web Mercator projection.

Web Mercator

The Web Mercator projection has been designed to be practical. It does not maintain distances very well, for example. But, it has other nice properties. We will first give an intuition of how it works. The first step is abstraction. Earth is close enough to a sphere to think of it as one, so we pretend to start from a sphere. We now cut off the very top and bottom parts of this sphere, so that we are left with a band. The parts we cut off are the North and South poles. Only few people live there, or close to there, so cutting that away will not impact most map users. Next, we cut the band vertically, so that we are left with a strip. We roll out this strip and stretch it, so that it fits in a square. This will deform the parts of the earth close to the poles, while areas close to the equator are only mildly deformed. This again penalizes the poles, but since only few people live there, the projection will be fine for most map users. A coordinate (longitude, latitude) given as $(\lambda, \phi)$ is mapped to $(x, y)$ as follows:

$$ \begin{align} x &= \frac{128}{\pi} ~ 2^z (\lambda + \pi)~\text{pixels,} \\[1em] y &= \frac{128}{\pi} ~ 2^z \left(\pi - \ln\left(\tan\left(\frac{\pi}{4} + \frac{\phi}{2}\right)\right)\right)~\text{pixels.} \end{align} $$

In this equation, $z$ is the zoom level. When using a zoom level of 0 for now, and assuming cut off north and south poles, everything can be mapped into a square of 256 pixels tall and wide. This is called a tile. When zooming in, the entire world can be represented by $2^z \times 2^z$ tiles. This is by design, and allows implementations such as Google Maps to precompute map renders and serve only parts of the world map that a user is looking at.

Implementation

When working with geographical data, it is inconvenient to work in the space of longitude and latitude of coordinates. It is possible to pretend that this is a two-dimensional space, but it really is not. This is very noticable when you start to work with shapes like discs and want to calculate if two discs overlap.

For this reason, it is useful to be able to easily project coordinates into an actual plane, run any algorithm you want in that space and then unproject back onto Earth.

We provide example code in C++ and Java for exactly this purpose. You can look at the Git project or directly download the source as a (compressed) zip, tar.gz, tar.bz2 or tar archive. The project contains a README file that will help you get up and running quickly.