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?