Vereinfachung von polygonalen Ebenenunterteilungen unter Topologieeinschränkungen

Abstract

Verschiedene Geoinformationen, wie beispielsweise Straßenverläufe, Höhenlinien und Grenzverläufe, liegen häufig in großen Datenmengen vor. Zur Darstellung auf einem Bildschirm wird jedoch selten die volle Auflösung benötigt, sondern eine geringere Auflösung, die vom gewählten Zoombereich und von der Bildschirmauflösung abhängt. Daher müssen die Rohdaten vor der Übertragung und Darstellung bis zu einer gegebenen Fehlertoleranz vereinfacht werden. In dieser Arbeit wird das Problem der Vereinfachung von polygonalen Ebenenunterteilungen untersucht. Dabei soll bei der Vereinfachung eine Fehlertoleranz eingehalten und die Topologie der Eingabe erhalten werden. Weitere Einschränkungen an die Vereinfachung können als Topologieeinschränkungspunkte gegeben sein, die nach der Vereinfachung in der topologisch selben Facette liegen müssen. Es werden bekannte theoretische Ergebnisse sowie verschiedene Heuristiken zur Ebenenvereinfachung vorgestellt. Eine neue Heuristik, die mittels einer eingeschränkten Delaunay-Triangulierung das Problem auf viele kleine und lokale Teilprobleme reduziert, wurde im Rahmen dieser Arbeit implementiert. Zum Testen der Heuristik wurden sowohl verschiedene OpenStreetMap-Datensätze von Hamburg und von Baden-Württemberg verwendet als auch konstruierte Datensätze um die Laufzeit abzuschätzen. Anhand der ermittelten Laufzeiten für die Vereinfachung kann man von einer Laufzeit ausgehen, die superlinear jedoch nicht quadratisch ist.