Beschriftung von Bildschirmkarten in Echtzeit

Abstract

Diese Arbeit stellt neuartige Konzepte zur Beschriftung von punkt-, linien- und flächenhaften Objekten in Karten vor. Der Fokus liegt dabei auf Bildschirmkarten. Im Unterschied zu traditionellen Papierkarten müssen für Bildschirmkarten die Funktionalitäten Zoomen (freie Maßstabswahl), Scrollen (Änderung des Kartenausschnitts) und Zusammenführen und Beschriften heterogener Daten (freie Kombination von Beschriftungslayern/-themen) unterstützt werden. Jede dieser Aktionen verursacht eine Neubeschriftung, die in Echtzeit erfolgen muss. Obwohl die Auflösung und Größe von Bildschirmkarten geringer ist als die von traditionellen Karten, ist die Beschriftung von Bildschirmkarten sehr aufwendig. Für die Informatik ist dieses Problem np-hart; das bedeutet, dass es vermutlich keinen wirklich schnellen Algorithmus gibt. Um trotzdem eine Beschriftung in Echtzeit zu erzielen, müssen Heuristiken eingesetzt werden. Gleichzeitig müssen kartographische Gestaltungsregeln in sehr schnellen Algorithmen integriert werden, um gut lesbare Bildschirmkarten zu erhalten. <br /> Das Konzept zur Erreichung dieser Ziele integriert explizit kartographische Anforderungen, wie die Beschriftung in bevorzugter Position, die Minimierung des Informationsverlustes und die Berücksichtigung topologischer Trennlinien. Die Beschriftung in Echtzeit wird durch die Trennung in zwei Phasen erzielt. In die erste Phase, die vor einer Interaktion des Nutzers stattfindet, erfolgt die Verlagerung möglichst vieler zeitintensiver Berechnungen. Das führt zu einer Entlastung der zweiten Phase und somit zu einer schnelleren Beschriftung für den Nutzer. Die erste Phase wird als Präprocessingphase und die zweite Phase als Interaktionsphase bezeichnet. <br /> Beide Phasen sind eng gekoppelt. Für die effiziente Unterstützung der Funktionen Scrollen und Zoomen erfolgt in der Präprocessingphase die Generierung einer Datenstruktur, auf die die Interaktionsphase aufbaut. Aus dieser maßstabsunabhängigen Datenstruktur, dem reaktiven Konfliktgraphen, werden passend zu jedem spezifischen Maßstab und Kartenausschnitt alle nötigen Informationen für den Beschriftungsprozess effizient abgeleitet.<br /> Eine wichtige neuartige Heuristik, die für dieses Konzept entwickelt wurde, ist dabei das Kriterium zur Bestimmung der Beschriftungsschwierigkeit. Es ermöglicht eine Vorselektion der zu beschriftenden Objekte in Abhängigkeit von Maßstab und Objektpriorität in der Präprocessingphase. Dazu wurden verschiedene Kriterien entwickelt, analysiert und evaluiert. <br /> Im Unterschied zu traditionellen, automatischen Beschriftungskonzepten ist in dem entwickelten Konzept die Beschriftung nicht auf vorgegebene diskrete Beschriftungspositionen beschränkt, sondern auf einen Beschriftungsraum, wie es den kartographischen Beschriftungsmethoden entspricht. Diese Modellierung wird mit „sliding labels“ bezeichnet. <br /> Im Rahmen dieser Arbeit wurde ein komponentenbasiertes System entwickelt, das die wesentlichen Konzepte erfolgreich umsetzt und evaluiert. Die Umsetzung der Beschriftung punkthafter Objekte erfolgte nahezu vollständig. Die implementierte Visualisierungskomponente, die kartographisch angemessen Kartenobjekte darstellt, ermöglicht eine visuelle Verifikation der umgesetzten Verfahren, inklusive der Visualisierung der Konfliktgraphen. Eine Schnittstellenkomponente, die sich am OGC-Konzept der „Simple Features“ orientiert, ermöglicht den Datenimport von kommerziellen GIS.

This work presents new concepts for labeling of point, line and area objects. The focus is on screen maps. In contrast to traditional paper maps, screens maps have to provide the functionalities of scrolling (changing the map clipping), zooming (free choice of scale), and integrating and labeling of heterogonous data (free combination of labeling-layers/-themes). Each action causes a new labeling, which has to be performed in real-time. Although resolution and size of screen maps are lower than those of traditional maps, the labeling of screen maps is still very time-consuming. From a computer science perspective, this problem is np-hard, which means that most likely there exists no fast algorithm. Nevertheless, to achieve a labeling in real time, heuristics must be used. Simultaneously, consideration of cartographic rules is essential in order to receive well readable screen maps.<br /> To obtain these targets, the concept explicitly integrates cartographic rules, such as labeling in preferred position, minimization of information loss and consideration of topological separation lines. The labeling in real-time is achieved by dividing the labeling process into two phases. Calculations are shifted in the first phase as far as possible. Thus, the number of time consuming operations in the time critical second phase is reduced and leads to faster labeling for the user. The first phase is called the preprocessing-phase and the second phase is called the interaction-phase.<br /> Both phases are linked closely. In order to efficiently support scrolling and zooming functions in the second phase, a data-structure is generated during the first phase. This scale independent data-structure is called reactive conflict graph and allows an efficient derivation of all information necessary for the labeling process for any scale and map clipping.<br /> An essential new heuristic, which was developed for this concept, is a criterion to measure labeling difficulty. It allows a pre-selection of objects to be labeled in dependence of the object’s scale and priority during the preprocessing-phase. Thus, different criteria are developed, analyzed and evaluated.<br /> In contrast to traditional automatic labeling algorithms, the developed labeling concept is not restricted to discrete positions. Instead, sliding labels in labeling spaces are used, which satisfies cartographic principles.<br /> The feasibility of the main concepts is demonstrated by the successful implementation and evaluation of a component-based system. The consideration of point labeling is realized completely. The implemented visualization component enables verification of the results of the labeling process, in particular by presenting the underlying reactive and static conflict graphs as well as the cartographic visualization of the map objects. An interface component provides data-import from commercial GIS, based on the OGC-concept of “Simple Features”.