Grouping and ordering constraints in boundary labeling

Abstract

Illustrationen beinhalten oft Merkmale mit einem Label für deren Name oder Beschreibung. Um zu verhindern, dass wichtige Teile der Illustration mit einem Label verdeckt werden und trotzdem ansprechende und verständliche Abbildungen zu erstellen, können wir die Labels um die Illustration herum platzieren und kreuzungsfreie Führungslinien verwenden, um eine eindeutige Zuordnung zwischen dem Label und dem Merkmal sicherzustellen. Vor allem in medizinischen und technischen Zeichnungen wenden wir häufig diese Methode der externen Beschriftung an. Jedoch gibt es in diesen Gebieten auch weitere Beschränkungen, welche aus der Semantik, die die Merkmale tragen, hervorgehen. Ein Beispiel hierfür ist eine Gruppe von Merkmalen, die zusammen ein größeres Objekt darstellen und daher nebeneinander beschriftet werden sollen. Obwohl die Literatur eine Vielzahl von Ansätzen zur Erstellung von externen Beschriftungen beschreibt, berücksichtigt kaum eine davon diese semantischen Beschränkungen. In dieser Masterarbeit betrachten wir daher nochmal Randbeschriftungen, eine Unterart von externen Beschriftungen, bei der die Labels entlang eines rechteckigen Randes um die Illustration herum platziert werden. Wir erweitern diese um Gruppierungs- und Ordnungsbeschränkungen, welche die Menge der gültigen Beschriftungen einschränken. Gruppierungsbeschränkungen verlangen, dass ein Teil der Labels nacheinander auf dem Rand platziert wird. Ordnungsbeschränkungen definieren eine partielle Ordnung auf den Merkmalen. Um diese Beschränkungen darzustellen, schlagen wir PQ-A-Graphen vor, eine Erweiterung von PQ-Bäumen. Durch die Interpretation einer Beschriftung als eine Permutation der Merkmale, lässt sich zeigen, dass wir alle relevanten Beschränkungen als PQ-A-Graphen darstellen können. Wir präsentieren einen Algorithmus, um einseitige Randbeschriftungen mit achsenparallelen Führungslinien, welche höchstens eine Biegung aufweisen, zu erstellen. Mithilfe von echten und künstlichen Instanzen evaluieren wir die Performance des Algorithmus und analysieren die erzeugten Beschriftungen. Des Weiteren werden mögliche Interpretationen unserer Beschränkungen in mehrseitigen Randbeschriftungen diskutiert und wir zeigen, dass das Finden einer gültigen Randbeschriftung in unserem Interpretationsvorschlag bereits für zwei Seiten NP-vollständig ist. Abschließend schlagen wir Variationen unseres Problems vor, welche wir als interessant und relevant für praktische Anwendungen erachten, und präsentieren, als Anstoß für weitere Forschung, hierfür erste Ergebnisse.

Illustrations often include features with a label for their name or description. To avoid obstructing crucial parts of the illustration with a label and still create appealing and comprehensible figures, we can place the labels around the illustration and use non-crossing leader lines to ensure that the connection between a label and the feature is unambiguous. Especially in medical and technical drawings, we frequently apply this external labeling technique. However, in these domains, we can encounter additional constraints arising from the semantics of the features, such as groups of features that constitute parts of a larger object and should be labeled next to each other. Despite the fact that the literature proposes a multitude of approaches to compute external labelings, hardly any of them take semantic constraints into account. In this thesis, we revisit boundary labeling, a branch of external labeling, where all labels are placed along a rectangular boundary around the illustration. We enrich it by grouping and ordering constraints that restrict the set of feasible labelings. Grouping constraints enforce that a subset of the labels must appear consecutively on the boundary while ordering constraints define a partial order on the features. We propose PQ-A-Graphs, an extension of PQ-Trees, to represent our constraints. By interpreting a labeling as a permutation of the features, we are able to show that all relevant grouping and ordering constraints can be encoded as PQ-A-Graphs. We present an algorithm to compute a one-sided boundary labeling with axis-aligned leader lines that have at most one bend. Using real-world and artificial instances, we evaluate the performance of the algorithm and analyze the resulting labelings. Furthermore, we discuss an interpretation of our constraints in multi-sided boundary labelings and show that finding a feasible labeling in the suggested interpretation is NP-complete, even if we only consider two sides. Finally, we propose variations of our problem that we deem interesting and relevant for practical applications and provide preliminary results as starting points for future research.