TY - JOUR
T1 - Morphing polylines: A step towards continuous generalization
AU - Nöllenburg, M.
AU - Merrick, D.
AU - Wolff, A.
AU - Benkert, M.
PY - 2008
Y1 - 2008
N2 - We study the problem of morphing between two polylines that represent linear geographical features like roads or rivers generalized at two different scales. This problem occurs frequently during continuous zooming in interactive maps. Situations in which generalization operators like typification and simplification replace, for example, a series of consecutive bends by fewer bends are not always handled well by traditional morphing algorithms. We attempt to cope with such cases by modeling the problem as an optimal correspondence problem between characteristic parts of each polyline. A dynamic programming algorithm is presented that solves the matching problem in O(nm) time, where n and m are the respective numbers of characteristic parts of the two polylines. In a case study we demonstrate that the algorithm yields good results when being applied to data from mountain roads, a river and a region boundary at various scales.
AB - We study the problem of morphing between two polylines that represent linear geographical features like roads or rivers generalized at two different scales. This problem occurs frequently during continuous zooming in interactive maps. Situations in which generalization operators like typification and simplification replace, for example, a series of consecutive bends by fewer bends are not always handled well by traditional morphing algorithms. We attempt to cope with such cases by modeling the problem as an optimal correspondence problem between characteristic parts of each polyline. A dynamic programming algorithm is presented that solves the matching problem in O(nm) time, where n and m are the respective numbers of characteristic parts of the two polylines. In a case study we demonstrate that the algorithm yields good results when being applied to data from mountain roads, a river and a region boundary at various scales.
U2 - 10.1016/j.compenvurbsys.2008.06.004
DO - 10.1016/j.compenvurbsys.2008.06.004
M3 - Article
SN - 0198-9715
VL - 32
SP - 248
EP - 260
JO - Computers, Environment and Urban Systems
JF - Computers, Environment and Urban Systems
IS - 4
ER -