CSE Roadmap

Specialist tier · about 5 hours · 7 parts

Part 3 of 7 · 2 min read

Basics

Tiles, geohash and graphs.

Projection. A globe becomes a flat map through a projection, which always distorts something. Web maps use a variant of the Mercator projection.

Geocoding. Turning an address into a latitude and longitude is geocoding. The reverse is reverse geocoding. A place table (a key-value store, read often and written rarely) answers it.

Geohash. A geohash splits the flat world into four cells, then each cell into four, again and again. Each cell gets a short string. A longer string means a smaller cell. Level 11, page 6 uses it for nearby places. Here it names tiles and routing tiles.

Map tiles. The map is cut into square pictures of 256 × 256 pixels, at 21 zoom levels. At level 0, one tile shows the whole world. Each level doubles the tiles in each direction, so there are 4 times as many tiles. The client downloads only the tiles it needs at its zoom level and stitches them together.

Roads as a graph. Intersections are nodes and roads are edges. Routing algorithms such as Dijkstra's algorithm and A* find paths on this graph. A graph of the whole world is too big for memory.

Routing tiles. The world is divided into grids, and each grid holds a small graph of its own roads, plus links to neighbour grids. The algorithm loads only the tiles it needs. There are three levels of detail:

  • Small tiles with local streets.
  • Larger tiles with main roads between districts.
  • Very large tiles with highways between cities.

A route of 500 km starts on local streets, climbs to highways, and comes down near the end, using links between the levels.

A worked example (made up). A trip across a country touches 30,000 street-level tiles if only the detailed graph is used. With three levels, the search uses a few hundred local tiles near each end and a few dozen highway tiles in the middle. Memory and time drop by orders of magnitude.

Routing tile

A routing tile is a small piece of the road graph that covers one grid cell and links to its neighbours.

Example: the tile for one city district holds its intersections and roads, plus a link to the highway tile that its main road joins.

Check yourself: 1. What does a longer geohash string mean? 2. Why are routing tiles in three levels of detail? 3. What are the nodes and edges of the road graph?