Mise à jour le 2020-12-26
I rewrote everything in rust for much more simplicity and explained it a blog post in french.
All roads lead to Rome and it makes great maps! The project Roads to Rome made a small buzz with their gorgeous maps showing a superposition of many routes that lead to Rome.
They well deserve their success. The representation looks like a human cardiovascular system, whose heart is Rome.
I was somewhat jealous for not having that idea first. Nor did I have the aesthetic talent to make a beautiful representation, so I was slightly condescending: “Meh. It’s only 20 lines of code for a Dijkstra and some plotting”.
Having some free time in Perpignan with my family for a week, I tried to copy their work. Here is a journal of what I did.
Since my laptop is a 4 years old netbook and due to my laziness to optimise my code, the example will only cover France and not Europe on the whole.
Data from OpenStreetMap under ODbL
# 1. Get the data
Of course I used OpenStreetMap. However, processing all the data of France was too much for my modest project osm4routing. I used the extraction part from OSRM.
I read the binary representation in the .osrm files. This
is not portable at all as the format is a temporary file format.
Actually, my code does not work anymore on their develop branch.
The street network of France consists of a little more than 30 millions nodes and about the same amount of edges. As a pleasant bonus, OSRM also reads ferry routes. This allows us to reach Corsica and other islands.
# 2. Compute all the routes
So we extracted a nice graph, with realistic travel durations. We now want to compute all the routes that start from Notre-Dame. Indeed, while all roads lead to Rome, all roads start from Notre-Dame (FR).
The starting point is the node 677151951 in OpenStreetMap.
Luckily, computing all routes from a single node to every other has been solved more than half a century ago.
This is exactly what Dijkstra’s algorithm does. In fact, I used the Bellman-Ford algorithm as I did not care about performance and I preferred its trivial implementation.
# 3. Count the use of every edge
Once we have all the routes from Notre Dame to all the nodes in France, we take each single route from Notre-Dame to every node in France and we count how many routes each edge occurs in.
All the edges are inserted into a PostGIS database (Postgres with a geographical extension) with their coordinates and use count.
All the steps until now were implemented in Rust and are available here.
Initially I planned to use QGis or Mapbox to make the rendering. However, the size of the data made that impossible for any area larger than the greater Paris.
# 4. Draw everything on a image
The coordinates are given as [(longitude; latitude)]. If you
plot them directly as [(x; y)] on a picture the result is
horrible at higher latitude. It is called the plate carrée
projection.
(By the way, if you plot [(lat; lon)] it will be even worse😉)
The official projection for continental France is Lambert 93. With Postgis and a lot of waiting, I could trivially reproject all the coordinates.
As I could not find how to use a graphics library in Rust, I ended up drawing the edges in C++ using Cairo.
But first I dumped all the edges in a binary file in order to save some time when experimenting around.
With a lot of trial and error I found a reasonable balance between the width of each edge and its darkness.
For the pictures with the largest resolution, I drew every edge that was used by more than 10 routes. That represents about 18 million edges.
# 5. Scale for Europe
So I got a nice representation of all the roads from Notre-Dame in France. What about Europe, like in the project I ripped off? My 4 years old netbook was mistreated enough.
I would need a better machine (much more RAM, an SSD disk would be nice), and to make some improvements:
- Use Dijkstra’s algorithm instead of Bellman-Ford
- Find a more effective way to count every edge use
- Skip the intermediate step with PostGIS; dump directly into a binary file
- Find a proper way to draw 100 million little dashes?