/dijkstra-cartography

Using Dijkstra's algorithm ("finding the shortest paths between nodes in a graph") to draw maps :earth_africa:.

Primary LanguageC++OtherNOASSERTION

Dijkstra Cartography

Introduction

I was fascinated by the project "Roads to Rome" by Moovellab but sad that it isn't opensource. Helped by this project (thanks @tristramg ) I started to build my own map.

I did not have any GIS background but it was very interesting to discover what we can do with. The code isn't very good (I'm not a C++ guru).

The project is named "Dijkstra Cartography" but sometimes BFS algorithm is better (if all the edges have the same weight).

This code can be useful for cartographer, as I found a lot of errors for the river Amazon (see here) or.. to have your own poster 😉.

Extract

You may not want to use the planet.osm file (644GB - all the openstreetmap data in one file). Choose the right file here and extract what you really need with openstreetmap's tools : osmconvert, osmfilter, osmosis, osmium...

One interesting way is that you can extract all the data within a polygon with osmconvert, and here are some cities polygons.

Routing

Map Routing system used
Paris Graphhopper - "Dijkstrabi"
Amazon Dijkstra's algorithm
Railway OSRM
Flights Dijkstra's algorithm

The first thing to do is to gather the statistics of usage of all paths : for each location, execute the routing algorithm you chose to your root location (your home for example). Merge all and sort the data by the most used path.

Projections

Map Projection
Paris Lambert 93-I EPSG:27571
Amazon ESRI:102032 (South America Equidistant Conic)
Railway Mercator
Flights WSG84

You can follow this guide, search SpatialReference or ESPG.io.

Drawing

Considering the data is sorted and well projected.

The width and height of the image are defined like this :

width = (maxX-minX)/scale;
height = (maxY-minY)/scale;

To draw these paths, I used this function (plotted using R) : ./results/function.jpg

as it gives me a percent (between [0;1] here) of how the line width must be important. Also I can accentuate the decreasing by modifying parameters inside exp().

I used cairo and I was really suprised that I can understand these map without using any shapefile.

Details for each map

Bonus

./results/paris.gif

License

See here.