November 2016
Note: Master Thesis and an extended abstract is only available in German. Please find a short abstract in English below. Eine deutsche Kurzfassung ist unterhalb des englischen Abstracts zu finden.
The purpose of this thesis is to investigate the automatization of manual post-processing graphical requirements of metro maps. Metro maps should ease the passenger's orientation within the network of a public transport system. For that reason, instead of using topographical maps, a simplified map is usually presented omitting irrelevant information. Probably the most famous metro map is Henry Beck's Tube Map of London City. Most of the today's used layout rules for schematic metro maps trace back to him, e.g. presenting the lines within an angle of 45 degree or a multiple of it (octilinearity). Beside network information, such maps might include graphical elements (signatures) such as landmarks and points of interest.
In the course of his study of literature the author came across variety of papers discussing approaches to generate a metro map. Some of these approaches are beneficial to generate metro maps of a simple network such as a underground train system. However, all of them do not address the issue of route segments with several routes such as often found in continental Europe where sometimes 10 or more routes are running on route segments. In addition, other graphical elements such as landmarks are not taken into account. Starting with an octilinear graph layout of a railway network, the author focusses on problems arising from adding route information. In most of the cases there is not enough space between the given map elements to include more information. The map must be changed to add such elements. This is an iterative process increasing the complexity with each iteration. The author develops an algorithm to solve the problems arising with this use case. He presents a method to determine the necessary space in order to add route information and station signatures. To increase space, neighbouring nodes are iteratively displaced. This process produces non-octilinear edges (lines) which are corrected by the author's algorithm. Based on examples, two approaches are presented. One approach uses scaling and the other moves nodes iteratively until enough space is available. The second approach may require the restoration of the edge's octilinearity with further shift processes.
Problems of metro maps are often varying from map to map. Hence, these individual problems cannot be solved completely with a routine method. This applies also to the author's examples. Whilst implementing, problems are produced which cannot be solved with his approach. The author concludes that in real situations one has always to reckon with problems that require a manual post-processing.
Die vorliegende Masterarbeit beschäftigt sich mit der Automatisierung von Teilaufgaben der manuellen graphischen Nachbearbeitung von Liniennetzplänen. Liniennetzpläne von Verkehrsnetzwerken sollen den Passagieren die Orientierung erleichtern. Zu diesem Zweck werden topographische Karten soweit vereinfacht, dass nur die notwendige Information ersichtlich ist. Weltbekannt wurde der Liniennetzplan der Londoner U-Bahn (Tube Map) von Henry Beck. Auf ihn gehen Regeln für die Darstellung von schematischen Liniennetzplänen zurück, z.B. die Darstellung von Streckensegmenten mit 45 Grad Winkeln oder einem Vielfachen davon (Oktilinearität). Solche Liniennetzpläne enthalten graphische Elemente (Signaturen), welche die Netzwerkinformation sowie Landmarken und eventuell Points of Interest repräsentieren.
Im Zuge seiner Literaturrecherche kommt der Autor zum Ergebnis, dass bereits eine Anzahl von Ansätzen zur automatisierten Erstellung von Liniennetzplänen in der Fachliteratur beschrieben wird. Einzelne dieser Ansätze erweisen sich als nützlich, um einen schematisierten Liniennetzplan zu erstellen, welcher ein Streckennetz abbildet, jedoch keine detaillierten Routeninformationen und auch keine anderen Kartenelemente berücksichtigt. Ausgehend von einem solchen schematisierten Streckennetz beschäftigt sich der Autor mit den Problemen, die entstehen, wenn dem Liniennetzplan Informationen hinzugefügt werden. Die Darstellung des reinen Streckennetzes bietet vielfach zu wenig Platz, um alle benötigten Informationen einzupflegen. Der Platzbedarf dieser Informationen bedingt eine laufende Anpassung der graphischen Darstellung, die immer komplexer wird, je mehr Informationen hinzugefügt werden. Hier setzt der Autor mit seiner Methode der Automatisierung an. Er entwickelt ein Verfahren, um den Platzbedarf der Routeninformationen und Haltestellen-Signaturen zu ermitteln. Um den benötigten Platz zu schaffen, müssen benachbarte Elemente iterativ verschoben (verdrängt) werden. Der Vorgang der Verdrängung erzeugt vor allem mit dem Kriterium der Oktilinearität Konflikte, die der Autor mit Hilfe der von ihm entwickelten Algorithmen korrigiert. Anhand von Beispielen werden zwei Korrekturverfahren demonstriert, wobei eines sich des Verfahrens der Skalierung bedient und das andere Knoten iterativ verschiebt, bis der Konflikt gelöst ist. Das zweite Verfahren erfordert unter Umständen die Wiederherstellung der Oktilinearität durch weitere Verschiebeprozesse.
Die Problemstellungen von Liniennetzplänen sind so unterschiedlich, dass immer wieder Einzelprobleme auftreten, die durch ein Standardverfahren nicht gelöst werden können. Auch im Beispiel des Autors ergeben sich Problemfälle, die mit seinem Ansatz nicht gelöst werden können, was aber erst bei der Implementierung deutlich wird. Für die Praxis bedeutet dies, dass immer mit Sonderfällen bei der Erstellung von Liniennetzplänen zu rechnen ist, die der manuellen Nachbearbeitung vorbehalten bleiben.