Ableitung eines routingfähigen Verkehrsnetzes aus nutzergenerierten Geodaten durch Generalisierung
| Leitung: | Thiemann |
| Team: | Paul Czioska |
| Jahr: | 2013 |
| Laufzeit: | 2013 |
| Ist abgeschlossen: | ja |
Mobilität ist ein wichtiger Bestandteil unserer heutigen Gesellschaft. Insbesondere der Anteil des öffentlichen Personenverkehrs mit der Bahn nimmt dabei stetig zu und spielt eine immer bedeutendere Rolle. Um einen fahrgastfreundlichen und reibungslosen Ablauf zu ermöglichen, sind verlässliche Informationen über Verbindungen, Verspätungen und den Streckenverlauf ein gutes Hilfsmittel zur Unterstützung der Reisenden. Im Zeitalter der mobilen Kommunikation besteht dieses Informationsangebot neben der reinen Verbindungssuche immer häufiger auch aus Echtzeit-Informationen über Status und Position der aktuell verkehrenden Züge, dessen Position und befahrene Route auf einer Karte dargestellt werden (Live-Map, z.B. www.bahn.de/zugradar).
Für solche Anwendungen ist es erforderlich, dass die zugrunde liegende Gleisgeometrie als routingfähiger Graph vorliegt. Nutzergenerierte Geodaten, etwa aus OpenStreetMap, bieten hier eine zuverlässige und detailreiche Quelle. Für ein schnelles Routing und adäquate Kartendarstellungen ist es allerdings erforderlich, die große Anzahl an (meist parallel verlaufenden) Gleisen zu repräsentativen Linien zu bündeln und dadurch die Redundanz deutlich zu verringern und gleichzeitig eventuell bestehende Topologiefehler beheben zu können.
Im Rahmen dieser Masterarbeit wurde ein Algorithmus entwickelt, der Gleise (als Liniendatensatz) im zweidimensionalen Raum nach topologischen Eigenschaften aggregiert und als Ergebnis einen routingfähigen, ungerichteten Graphen mit Geokoordinaten erzeugt. Parallel verlaufende Linien werden zu einer repräsentativen Geometrie zusammengefasst. Die zugrunde liegende Topologie wird dabei gewahrt, um bei Abzweigungen eine Verbindung einzufügen, jedoch bei Kreuzungen ohne Übergang (z.B. Brücken) keinen Knotenpunkt zu erzeugen.
Es wurden vier verschiedene Methoden implementiert, um dieses Ziel zu erreichen, darunter ein trivialer Ansatz und zwei Varianten des Sweepline-Paradigmas. Die Methode mit den besten Ergebnissen nutzt Techniken aus dem Bereich der Skelettierung von Polygonen (Area Collapse) auf der Basis von Dreiecken.
Der Algorithmus wurde abschließend umfangreich analysiert und getestet. Eine Evaluierung, bei der mehrere Relationen des Personenverkehrs in Norddeutschland geroutet wurden, zeigte eine hohe Ergebnisqualität. Durch eine lineare Zeit- und Speicherkomplexität ist der Algorithmus auch auf große Datensätze gut skalierbar.
