An interactive optimization framework for point feature label placement

Abstract

Diese Diplomarbeit beschreibt ein interaktives Benutzer-zentriertes und Web-basiertes Optimierungsframework für das Point Feature Label Placement Problem. Die Arbeit versucht die Lücke zwischen der zeitaufwändigen und teuren manuellen Kartenerstellung und der weniger qualitativen aber wesentlich schnelleren und billigeren automatischen Label Platzierung zu schließen und die Nachteile beider Ansätze auszumerzen. Für ein gegebenes Set an punktuellen Features wollen wir für jedes Feature ein Label auf der Karte so platzieren, dass sich keine Labels überlappen. Da eine Karte mit hoher Qualität zusätzlich noch verschiedene kartographische Richtlinien und Präferenzen erfüllen muss, erlaubt unser entwickeltes Framework einem Expertenbenutzer sein bereichsspezifisches Fachwissen in einem interaktiven Vorgang einzubringen, um so eine initiale Kartenbeschriftung schrittweise zu verbessern. Wir haben dafür durch Interviews mit einer Kartographin diese benutzerdefinierten Bedingungen und Beschränkungen gesammelt und formal definiert. In dieser Arbeit betrachten wir nur achsenparallele, rechteckige Labels mit vordefinierten fixen Positionen in einem fixen Vier-Positionen-Model in statischen geographischen Karten. Wir haben das Point Feature Label Placement Problem mittels eines Konfliktgraphen beschrieben und verwenden diesen als Basis für all unsere Algorithmen. Wir haben in dieser Arbeit sowohl existierende als auch neue Algorithmen für automatisches Point Feature Label Placement präsentiert und implementiert. Dies beinhaltet einfache Algorithmen, exakte Algorithmen und verschiedene Heuristiken für das Problem der Labelmaximierung und dem Problem der Konfliktminimierung. Letztlich untersuchen und evaluieren wir unser Framework und seine Algorithmen bezüglich der Performance und der Qualität der erzeugten Lösungen mit realen Daten. Wir konzentrieren uns hier auch auf performante Algorithmenkombinationen für verschiedenartige Datensätze wie sie im normalen Gebrauch des Frameworks verwendet werden.

This thesis describes an interactive user-centered and web-based optimization framework for the point feature label placement problem. It tries to fill the gap between the time consuming and expensive manual map creation and the less qualitative but much faster and cheaper automatic label placement to eradicate the disadvantages of both approaches. Given a set of point features we want to place for each feature a label on the map such that the labels do not overlap. Since a high-quality map has to furthermore satisfy cartographic guidelines and preferences, our developed framework allows an expert user to add his or her domain knowledge in an interactive way by improving and updating an initial labeling step by step. We therefore collected and formally defined user constraints through interviews with a cartographic expert. In this work we consider axis-aligned rectangular labels with predetermined fixed label candidate positions in a fixed four position model on static geographical maps. We describe the point feature label placement problem with a conflict graph and use it as the basis for our algorithms. We present and implement in this thesis both existing and new algorithms for the automatic point feature label placement. This includes simple algorithms, exact algorithms and several heuristics for the label number maximization problem as well as the minimum number of conflicts problem. Finally, we investigate and evaluate our framework and its algorithms regarding the performance and the quality of the created labeling solutions on real world data. We hereby also concentrate on identifying well performing algorithm combinations for various kind of data sets as they are used in typical use cases of our framework.