Algorithmen für Geovisualisierung / vertikal

Bei der kartografischen Generalisierung wird eine Karte in eine Karte mit kleinerem Maßstab umgewandelt. Eine Möglichkeit der Verallgemeinerung von Kartenmerkmalen ist die Vereinfachung. Ein vereinfachtes Merkmal stellt dasselbe Objekt der realen Welt dar, allerdings in einer weniger komplexen Form. (Zum Beispiel müssen Geometrien beim Zoomen auf einen kleineren Maßstab vereinfacht werden, um eine klare Visualisierung zu erhalten).

In dieser Arbeit befassen wir uns mit der Vereinfachung von polygonalen Objekten, z. B. Ländergrenzen oder Gebäudegrundrisse. (Die Vereinfachung einer polygonalen Form stellt das gleiche Objekt dar, aber in einer weniger komplexen Weise). Ein allgemeines Ziel bei der Vereinfachung von Polygonen ist die Verringerung der Anzahl der Scheitelpunkte des Polygons. In dieser Arbeit wollen wir außerdem, dass das Ausgangspolygon (1) kreuzungsfrei ist, (2) im Außenbereich des Eingangspolygons liegt, (3) auf die Scheitelpunkte des Eingangspolygons beschränkt ist, (4) und nur Kanten hat, die aus einer vordefinierten Menge von Abkürzungen stammen. Wir nennen ein solches Polygon eine Shortcut-Hülle. Wir zeigen, wie Shortcut Hulls berechnet werden können, die ein Gleichgewicht zwischen dem Umfang und der abgedeckten Fläche optimieren. Wir bieten einen dynamischen Programmieransatz zur Berechnung der optimalen Shortcut Hulls in polygonaler Zeit.

Linienpläne sind schematische Karten für Transportnetze wie zum Beispiel für U-Bahn- oder Straßenbahnnetze. Im Gegensatz zu Straßenkarten liegt allerdings der Fokus auf der klaren Darstellung der Netzwerktopologie und weniger auf der akkurat geographischen Widergabe des Netzwerkes. Dementsprechend umfasst das Zeichnen von Liniennetzen zwei anspruchsvolle Schritte, nämlich das Zeichnen des Netzes selbst sowie das Platzieren von überlappungsfreien Stationsnamen.

Ausgehend von einem bereits gezeichneten Netzplan, wird in dieser Arbeit das automatische Platzieren von Stationsnamen betrachtet. Im Gegensatz zu anderen Beschriftungsproblemen dürfen Beschriftungen nicht ausgespart werden, sondern jede Station muss beschriftet werden. In der Arbeit wird ein automatischer Arbeitsablauf zur Beschriftung eines beliebigen Netzwerks präsentiert. Zwar können für diesen keine mathematischen Gütegarantien gegeben werden, allerdings belegt eine experimentelle Evaluation, dass die erzielten Ergebnisse nahezu die mathematisch optimale Lösung erreichen.

Durch die zunehmende Verbreitung von interaktiven Kartenanwendungen im Internet und auf mobilen Endgeräten eröffnen sich neue Anforderungen für die Beschriftung von Karten. Durch Grundoperationen wie Rotieren, Zoomen und Verschieben der Karte muss die Platzierung der Beschriftungen an die Änderungen der Karte angepasst werden. In diesem dynamischen Szenario reicht es nicht aus, die Anzahl der Beschriftungen zu maximieren, sondern es müssen weitere Anforderungen, sogenannte Konsistenzkriterien, erfüllt werden. So dürfen Beschriftungen nicht springen oder durch häufiges sichtbar bzw. unsichtbar werden "flackern''. In der Arbeit wird ein allgemeines Modell für die Beschriftung von dynamischen Karten eingeführt, das die drei genannten Operationen miteinander vereint. Hierfür wird angenommen, dass der Anwender nur einen Ausschnitt der Karte sieht - als würde er die Karte mithilfe einer Kamera betrachten. Da bereits der statische Fall für das Beschriftungsproblem aus berechnungstheoretischer Sicht sehr komplex ist, ist es nicht verwunderlich, dass in dieser Arbeit auch für den betrachteten dynamischen Fall eine hohe Berechnungskomplexität gezeigt werden kann.

Schränkt man allerdings die Anzahl gleichzeitig angezeigter Beschriftungen ein, so kann, wie in der Arbeit gezeigt wird, das Problem mithilfe sogenannter dynamischer Programmierung effizient gelöst werden. Diese Einschränkung ist insbesondere für die Anwendung auf Navigationsgeräten interessant, die zumeist nur einen kleinen Bildschirm besitzen und den Anwender nicht mit zu vielen angezeigten Zusatzinformationen überfordern sollen