Algorithmen zur Geovisualisierung

Schematisierung von Routen

Kurzbeschreibung

Die visuelle Darstellung von Routen in Straßennetzwerken soll die Orientierung im Straßenverkehr unterstützen. Herkömmliche Straßenkarten (z.B. Google Maps) sind auf Grund des einheitlichen Maßstabs nicht optimal geeignet um diesen Zweck für alle Streckenabschnitte gleichzeitig zu erfüllen.

Um die Nachteile herkömmlicher Routenkarten zu überwinden entwickeln wir ein Verfahren, das Routenskizzen automatisch zeichnet. Dabei soll die Skizze dem groben Verlauf der Route ähneln um die mentale Karte des Nutzers zu erhalten. Das wird erreicht in dem gefordert wird, dass zwischen allen wichtigen Punkten der Route die links-rechts oben-unten Relation erhalten bleibt. Um kleine Details besser sichtbar zu machen wird eine Mindestkantenlänge eingeführt und um die Darstellungskomplexität zu verringern werden die verwendeten Kantenrichtungen eingeschränkt.

Experimentelle Ergebnisse

Drei verschiedene Visualisierungen der gleichen Route. Von links nach rechts: Google Maps, handgezeichnete Routenskizze, automatisch generierte Routenskizze


Unsere Resultate sind an dem Beispiel der kürzesten Route von Karlsruhe nach Konstanz ersichtlich. Vergleicht man die herkömmliche Darstellung von Google Maps mit der handgezeichneten Routenskizze ist offensichtlich, dass in der Skizze Details in Karlsruhe und Konstanz besser zu erkennen sind. Obwohl der Maßstab der Routenskizze nicht mehr einheitlich ist, so ist doch die grundsätzliche Ähnlichkeit mit dem Verlauf der urpsrünglichen Route gegeben. Das von uns entwickelte Verfahren generiert eine Routenskizze die der manuellen Skizze in den Kernpunkten ähnelt. Auch hier sind Details in Karlsruhe und Konstanz deutlich einfacher zu erkennen und auch diese Skizze ähnelt vom Verlauf der geographisch korrekten Route. Eine experimentelle Evaluation führte zum Ergebnis, dass unser Verfahren Routenskizzen guter Qualität in angemessener Zeit generieren kann.

Veröffentlichungen

Artikel in Zeitschriften

  1. Daniel Delling, Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, and Ignaz Rutter.
    On d-regular Schematization of Embedded Paths.
    Computational Geometry: Theory and Applications, 47(3A):381-406, 2014.
    [ html ][ pdf ]

Artikel in Tagungsbänden

  1. Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, and Ignaz Rutter.
    Automatic Generation of Route Sketches.
    In: Proceedings of the 18th International Symposium on Graph Drawing (GD'10) volume 6502 of Lecture Notes in Computer Science, pages 391-392. Springer, 2011.
    [ html ][ pdf ]
  2. Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, and Ignaz Rutter.
    On d-regular Schematization of Embedded Paths.
    In: Proceedings of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'11) volume 6543 of Lecture Notes in Computer Science, pages 260-271. Springer, January 2011.
    [ html ][ pdf ]
  3. Daniel Delling, Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    Path Schematization for Route Sketches.
    In: Proceedings of the 12th Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'10) volume 6139 of Lecture Notes in Computer Science, pages 285-296. Springer, June 2010.
    [ html ][ pdf ]

Diplomarbeiten

  1. Schematized Visualization of Shortest Paths in Road Networks.
    Andreas Gemsa.
    Master's thesis, Universität Karlsruhe (TH), Fakultät für Informatik, November 2009.
    [ pdf ]

Technische Berichte

  1. Daniel Delling, Andreas Gemsa, Martin Nöllenburg, and Thomas Pajor.
    Path Schematization for Route Sketches.
    Technical Report 2010-02, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    [ html ][ pdf ]
  2. Andreas Gemsa, Martin Nöllenburg, Thomas Pajor, and Ignaz Rutter.
    On d-regular Schematization of Embedded Paths.
    Technical Report 2010-21, Faculty of Informatics, Karlsruhe Institute of Technology, 2010.
    [ html ][ pdf ]