CH-basierte Darstellung von Straßennetzwerken mit optimierter Entfaltungsreihenfolge

Abstract

Echtzeitdarstellungen von Karten sind ohne die Auslassung und Vereinfachung von Kartenelementen nicht performant möglich. Ein Ansatz, um Performanz zu ermöglichen, ist der Einsatz von Kontraktionshierarchien. Um eine visuell ansprechende Darstellung zu garantieren, muss eine Kontraktionshierarchie jedoch bei jeder Anfrage nach einem Kartenausschnitt abhängig von dem gewünschten Detaillierungsgrad in einem gewissen Umfang wieder entpackt werden. Da die Entscheidung, welche Elemente nacheinander entpackt werden sollen, sehr zeitintensiv ist, sollte diese bereits in einem Vorverarbeitungsschritt, vor der eigentlichen Anfragezeit, getroffen werden. Ziel dieser Arbeit ist die Bestimmung von optimalen Entpackreihenfolgen in einem Vorverarbeitungsschritt mittels verschiedener Entpackstrategien und unter Nutzung unterschiedlicher Fehlermetriken. Mithilfe dieser Reihenfolgen werden anschließend bei einer Anfrage die darzustellenden Kanten in Echtzeit ermittelt. Um dies zu ermöglichen, wird eine Graphdatenstruktur durch das Einlesen einer Kontraktionshierarchie aufgebaut. Anschließend werden für die enthaltenen Kanten verschiedene Fehler vorberechnet. Mit diesen Fehlern können im Anschluss optimale Entpackreihenfolgen für verschiedene Entpackstrategien berechnet und in Dateien geschrieben werden. Bei einer Anfrage wird die benötigte Datei mit der optimalen Entpackreihenfolge eingelesen und die darzustellenden Kanten durch einen Entpackprozess basierend auf der eingelesenen Reihenfolge in Echtzeit ermittelt. Zudem wird eine Schnittstelle definiert, über welche Anfragen gestellt werden können. Ebenfalls wird eine Weboberfläche zur Demonstration der Funktionalität implementiert. Des Weiteren besteht die Möglichkeit, die nach einer Anfrage identifizierten Kanten als Ausgabedatei zu exportieren. Abschließend werden die entwickelten Verfahren auf mehreren Testgraphen auf einem Testsystem analysiert und der durch die verschiedenen Entpackreihenfolgen resultierende visuelle Eindruck verglichen.