Mit dem Siegeszug von Navigationsgeräten und Smartphones finden digitale Karten breite Anwendung im Alltag. Sie lotsen uns zielsicher über die Autobahnen oder zum nächsten Bäcker – solange die Karte gut und übersichtlich ist. Aber die Darstellung von vielen Informationen auf kleinen, mobilen Bildschirmen ist nicht trivial. Am Karlsruher Institut für Technologie (KIT) haben Informatiker nun eine Methode entwickelt, um die mathematisch optimale Anpassung von Beschriftungen an Perspektive und Fahrtrichtung zu gewährleisten.

„Digitale Karten sind Papierkarten vielfach überlegen“, erklärt Martin Nöllenburg vom KIT. „Digitale Karten lassen sich passend drehen oder zoomen; Sehenswürdigkeiten lassen sich thematisch aus Datenbanken hinzuladen.“ Eine Herausforderung sei es jedoch, die Darstellung und Beschriftung übersichtlich zu halten, egal wie der Nutzer den sichtbaren Bereich einstellt und egal wie die Route verläuft. „Wenn die Beschriftungen ständig überlappen, springen oder flackern, ist der Mehrwert dahin und gerade ein durch irritierende Darstellungen abgelenkter Fahrer kann im Straßenverkehr eine Gefahr darstellen.“

Die  Nachwuchswissenschaftlergruppe hat sich mathematisch exakt mit Geovisualisierung beschäftigt, also der Darstellung von Informationen in Karten. Dass dieses Forschungsgebiet nicht nur für Mathematiker und theoretische Informatiker interessant ist, zeigt, dass Nöllenburg für seine Arbeit bereits einen Research Award des Internet- und Kartendienstes Google erringen konnte. „Letztlich lassen sich brauchbare Algorithmen nur programmieren, wenn man das Problem mathematisch verstanden hat“, findet Nöllenburg.

Mittels der mathematischen Beschreibung von digitalen Karten lässt sich zunächst die Schwierigkeit des Problems abschätzen. Zum Beispiel gehört die Maximierung der Zahl der Beschriftungen im gewählten Bildausschnitt eines Navigationsgerätes entlang einer Route zu der rechenzeitintensivsten Gruppe von mathematischen Problemen, den sogenannten NP-vollständigen Problemen. „Wenn man die Zahl der Objekte in der Karte vergrößert, vergrößert man exponentiell die dafür notwendige Rechenleistung“, stellt Nöllenburg fest. „Diese ist natürlich gerade auf mobilen Geräten schnell ausgereizt.“

Vor diesem Hintergrund entwickelt die Arbeitsgruppe Algorithmen, die leistungsfähiger sind, indem sie das allgemeine Problem sinnvoll eingrenzen. „Statt zu versuchen, die Zahl der gleichzeitig eingeblendeten Beschriftungen zu maximieren, kann man einen guten Kompromiss zwischen Lesbarkeit, Rechenzeit und Informationstiefe finden, wenn man sich auf eine konstante Anzahl von Beschriftungen im gegebenen Ausschnitt beschränkt“, erklärt Benjamin Niedermann, der die mathematischen Beweise ausgearbeitet hat. „Mehr als drei bis sieben Objekte kann ein Mensch ohnehin nicht bewusst wahrnehmen.“ Darauf aufbauend lässt sich nicht nur ein einfaches Verfahren finden, das die Beschriftung einer Karte sinnvoll durchführt. Es lässt sich auch zeigen, dass die Rechenzeit des neuen Verfahrens nur moderat wächst, wenn die Objektzahl steigt. „Interessanterweise führt die Einschränkung der Optimierung auf einen passenden Kartenausschnitt dazu, dass die Summe der Beschriftungen über die ganze Route größer wird, also zum Beispiel mehr Sehenswürdigkeiten entlang des Weges erwähnt werden.“

„Je mehr mobile Endgeräte im Alltag genutzt werden, desto fundierter sollten die mathematischen Grundlagen sein“, unterstreicht Nöllenburg. „Nur so können wir Produkte entwickeln, die uns wirklich im Alltag unterstützen und nicht immer mehr Zeit und Mühe für die Bedienung abverlangen.“ Daher will Nöllenburg nun mit seinem Team den Schritt von der Grundlagenforschung in die Anwendung gehen und aus den mathematischen Methoden bald implementierbare Algorithmen entwickeln. „Ich bin mir sicher, dass unsere Methoden sich auch in der Praxis bewähren.“

Originalveröffentlichung:

Andreas Gemsa, Benjamin Niedermann, and Martin Nöllenburg. Trajectory- based dynamic map labeling. In: International Symposium on Algorithms and Computation (ISAAC’13), pp. 413–423. Springer-Verlag, LNCS 8283, December 2013.