Morphing polygonal lines : a step towards continuous generalization

D. Merrick; M. Nöllenburg; A. Wolff; M. Benkert

Morphing polygonal lines : a step towards continuous generalization

D. Merrick, M. Nöllenburg, A. Wolff, M. Benkert

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

72 Downloads (Pure)

Abstract

We study the problem of morphing between two polylines that represent a geographical feature generalized at two different scales. Some cartographical generalizations are not handled well by traditional morphing algorithms, e.g., when three consecutive bends in a river or road are generalized to two bends at a smaller scale. We attempt to handle such cases by modeling the problem as an optimal matching 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 number of characteristic parts of the two polylines. We also show the results of applying this algorithm on real road data.

Original language	English
Title of host publication	Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria
Editors	O. Aichholzer, T. Hackl
Place of Publication	Graz, Austria
Publisher	Verlag der Technischen Universität Graz
Pages	69-5
ISBN (Print)	978-3-902465-62-7
Publication status	Published - 2007
Event	conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21 - Duration: 19 Mar 2007 → 21 Mar 2007

Conference

Conference	conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21
Period	19/03/07 → 21/03/07
Other	EWCG 2007, Graz, Austria

Access to Document

Metis210771Final published version, 688 KB

Cite this

@inproceedings{054ba13315714743a92db62e49ae8a1d,

title = "Morphing polygonal lines : a step towards continuous generalization",

abstract = "We study the problem of morphing between two polylines that represent a geographical feature generalized at two different scales. Some cartographical generalizations are not handled well by traditional morphing algorithms, e.g., when three consecutive bends in a river or road are generalized to two bends at a smaller scale. We attempt to handle such cases by modeling the problem as an optimal matching 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 number of characteristic parts of the two polylines. We also show the results of applying this algorithm on real road data.",

author = "D. Merrick and M. N{\"o}llenburg and A. Wolff and M. Benkert",

year = "2007",

language = "English",

isbn = "978-3-902465-62-7",

pages = "69--5",

editor = "O. Aichholzer and T. Hackl",

booktitle = "Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria",

publisher = "Verlag der Technischen Universit{\"a}t Graz",

note = "conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21 ; Conference date: 19-03-2007 Through 21-03-2007",

}

Merrick, D, Nöllenburg, M, Wolff, A & Benkert, M 2007, Morphing polygonal lines : a step towards continuous generalization. in O Aichholzer & T Hackl (eds), Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria. Verlag der Technischen Universität Graz, Graz, Austria, pp. 69-5, conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21, 19/03/07.

Morphing polygonal lines : a step towards continuous generalization. / Merrick, D.; Nöllenburg, M.; Wolff, A. et al.
Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria. ed. / O. Aichholzer; T. Hackl. Graz, Austria: Verlag der Technischen Universität Graz, 2007. p. 69-5.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

T1 - Morphing polygonal lines : a step towards continuous generalization

AU - Merrick, D.

AU - Nöllenburg, M.

AU - Wolff, A.

AU - Benkert, M.

PY - 2007

Y1 - 2007

N2 - We study the problem of morphing between two polylines that represent a geographical feature generalized at two different scales. Some cartographical generalizations are not handled well by traditional morphing algorithms, e.g., when three consecutive bends in a river or road are generalized to two bends at a smaller scale. We attempt to handle such cases by modeling the problem as an optimal matching 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 number of characteristic parts of the two polylines. We also show the results of applying this algorithm on real road data.

AB - We study the problem of morphing between two polylines that represent a geographical feature generalized at two different scales. Some cartographical generalizations are not handled well by traditional morphing algorithms, e.g., when three consecutive bends in a river or road are generalized to two bends at a smaller scale. We attempt to handle such cases by modeling the problem as an optimal matching 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 number of characteristic parts of the two polylines. We also show the results of applying this algorithm on real road data.

M3 - Conference contribution

SN - 978-3-902465-62-7

SP - 69

EP - 65

BT - Collection of Abstracts of the 23rd European Workshop on Computational Geometry (EWCG 2007) 19-21 March 2007, Graz, Austria

A2 - Aichholzer, O.

A2 - Hackl, T.

PB - Verlag der Technischen Universität Graz

CY - Graz, Austria

T2 - conference; EWCG 2007, Graz, Austria; 2007-03-19; 2007-03-21

Y2 - 19 March 2007 through 21 March 2007

ER -

Morphing polygonal lines : a step towards continuous generalization

Abstract

Conference

Access to Document

Fingerprint

Cite this