Morphing of Polygonal Lines

Depending on the scale objects in a map are displayed with different levels of detail. In cartography the simplification process that finds the right level of detail is known as generalization. Classical (paper) maps are designed for a fixed single scale and generalization is optimized such that the map is as readable as possible at the given scale. In today's web-based and interactive maps, however, the user can zoom in and out and fix his/her own scale. One can observe in current systems that linear objects like rivers or roads do not change smoothly. In our work we use dynamic programming in order to transform (or morph) a polygonal line as smooth as possible from one representation to another. To this end we identify characteristic segments of the two polygonal lines and match them optimally.

The example below shows the morphing of a road section. (Gray lines indicate the animation.)

(a) simple linear interpolation

(b) result of our algorithm

Joint work with Damian Merrick.