Original paper

An Algorithm to Generate a Simplified Railway Network through Generalization

[Ein Algorithmus zur Erstellung eines vereinfachten Bahnnetzes durch Generalisierung]

Czioska, Paul; Thiemann, Frank; Sester, Monika; Giese, Robin; Vogt, Hermann

Abstract

Maps play a major role in communicating information in the context of public railway transportation, for instance as route maps. In addition, the current position of the trains can be shown on such a map to enrich the information content (Live Map). For the positioning and routing of the trains on the track, a graph structure of the traffic network is necessary. Since railway tracks are mostly arranged in a parallel manner, it makes sense to merge the track lines into representative (centre-)lines, which reduces significantly the amount of edges and helps to identify possible topological errors in the input data. This work presents an algorithm which merges track data based on topological properties, so that branches and crossings can be distinguished. The implementation uses generalization techniques like an area collapse operator and methods from computational geometry like polygon triangulation. An evaluation shows that the output graph is capable for routing tasks.

Kurzfassung

Karten spielen eine wichtige Rolle bei der Informationskommunikation im Rahmen des öffentlichen Verkehrs, etwa als Liniennetzplan, auf dem zusätzlich die aktuelle Position des Verkehrsmittels dargestellt wird (Live Map). Um solche Karten zu erstellen, ist eine routingfähige Graphstruktur der Gleisdaten nötig. Da Gleise meist parallel verlaufen, ist es sinnvoll, die Gleise zu repräsentativen Linien zu aggregieren, um die Redundanz zu verringern und mögliche Topologiefehler der Eingangsdaten zu beheben. In dieser Arbeit wird ein Algorithmus vorgestellt, der einen Gleisdatensatz nach topologischen Eigenschaften zusammenfasst. Der Implementierungsansatz nutzt hierzu Techniken aus dem Bereich der Skelettierung von Polygonen durch Triangulation. Eine abschließende Evaluation zeigt, dass das Ergebnis für Routinganwendungen geeignet ist.

Keywords

line mergingskeletonisationgeneralizationrailway