Curiosity is bliss    Archive    Feed    About    Search

Julien Couvreur's programming blog and more

Smart map/route drawing


The MSN Maps & Directions site features a very cool technology for displaying navigation maps in a more usable way. To try it, choose the "LineDrive" map style.

It produces results such as this:
LineDrive example

Basically, it performs multiple layout optimizations to avoid having very short roads appear very small because of very long roads and a dumb constant scale factor. This re-ordering is performed while keeping some consistency in the layout (maintain the direction of turns , keep the correct intersections, keep the lengths ordered, and other constraints).

The "Rendering Effective Route Maps: Improving Usability Through Generalization" page (with pdf papers) goes in great details of this very interesting algorithm.

I'd also be interested in finding more details on the actual path finding (that takes place before the above mentioned optimizations). It is probably related to a "shortest path" algorithm like Dijkstra's Algorithm, but there surely are many performance issues that arise when you try to scale up like MapQuest.

comments powered by Disqus