Joachim Breitner

Distance Map Morpher

Published 2008-04-03 in sections English, Digital World.

In my last blog entry, I was asking for algorithms to morph a picture so that contour lines would become circles. I then started to write some python/gtk/cairo code to actually visualize my thought. It came out relatively pretty, so I made the GUI around it usable (although far from nice, I guess) and put the current, early version in a darcs repostory (DarcsWeb browser available).

This is a screenshot (click for full version) of a map of my part of town, shamlessly stolen off the internet. The red shading shows the distance from the thick point of the graph – the redder, the closer. On the right the image is morphed so that all points on a circle around the center have the same distance to it. The blue shape on the left and the blue circle on the right are points with distance 205.

Below the user can

  • manually select the distance to highlight,
  • open a new image (with graph and cached calculations along, if present),
  • save the graph (and the cached calculations),
  • go to graph editing mode or get a short usage summary of that,
  • set the offroad penalty,
  • recalculate the distance function (which can be quite slow ATM),
  • recalculate the red height map,
  • set the interpolation method and the zoom level for the morphin,
  • recalculate the morved image,
  • or do all recalculations in one step.

Currently, there is one algorithm to determine the distance of a point to the center: Travel along the graph to the most suitable edge, leave at the point closest to the target and then go “crossroads”, which comes at a greater cost.

There are some things to do, most notable:

  • Faster distance generation, by better graph representation (e.g. so that it’s easier to find the nearest vertex)
  • Faster drawing
  • Better, less distorting morph algorithms. Some ideas are in the comments to my previous post.

Comments and patches are, as always, welcome. If you want to try it out make sure you have python2.5, pygtk and numeric-python installed.


Lass raten, Prüfungen sind rum und du hast bis zum Semesteranfang nix mehr zu tun? ;-)
Sieht echt witzig aus, ich staune wie schnell man sowas hinkriegt!
#1 keke am 2008-04-04
Quite contrary, Ich sollte eigentlich auf AlgoTech nächsten Donnerstag lernen und lasse mich ablenken.

Aber ich kann sogar Stoff aus der Vorlesung anwenden, so enthält der Code den Djikstra-Algorithmus für kürzeste Wege...
#2 Joachim Breitner (Homepage) am 2008-04-04
There are probably SVG maps of your town[1] if you want to transform something else.. (or of Stockholm[2])

For similar examples see the applet version of London subway map[3] done by Tom Carden.

But I like you map a lot more... ;-) Keep it up

#3 Erik Johansson am 2008-04-04

Have something to say? You can post a comment by sending an e-Mail to me at <>, and I will include it here.