<div class="csl-bib-body">
<div class="csl-entry">Löffler, R. (2018). <i>An interactive optimization framework for point feature label placement</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2018.55340</div>
</div>
-
dc.identifier.uri
https://doi.org/10.34726/hss.2018.55340
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/7717
-
dc.description.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.
de
dc.description.abstract
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.
en
dc.language
English
-
dc.language.iso
en
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
master thesis
en
dc.subject
interactive optimization framework
en
dc.subject
user-centered
en
dc.subject
label placement
en
dc.subject
point feature
en
dc.subject
conflict graph
en
dc.subject
quadtree
en
dc.subject
optimization algorithms
en
dc.subject
user constraints
en
dc.title
An interactive optimization framework for point feature label placement
en
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.identifier.doi
10.34726/hss.2018.55340
-
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Raphael Löffler
-
dc.publisher.place
Wien
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Klute, Fabian
-
tuw.publication.orgunit
E192 - Institut für Logic and Computation
-
dc.type.qualificationlevel
Diploma
-
dc.identifier.libraryid
AC15141200
-
dc.description.numberOfPages
80
-
dc.identifier.urn
urn:nbn:at:at-ubtuw:1-114869
-
dc.thesistype
Diplomarbeit
de
dc.thesistype
Diploma Thesis
en
dc.rights.identifier
In Copyright
en
dc.rights.identifier
Urheberrechtsschutz
de
tuw.advisor.staffStatus
staff
-
tuw.assistant.staffStatus
staff
-
tuw.advisor.orcid
0000-0003-0454-3937
-
item.openaccessfulltext
Open Access
-
item.openairecristype
http://purl.org/coar/resource_type/c_bdcc
-
item.grantfulltext
open
-
item.mimetype
application/pdf
-
item.languageiso639-1
en
-
item.openairetype
master thesis
-
item.fulltext
with Fulltext
-
item.cerifentitytype
Publications
-
crisitem.author.dept
E192-01 - Forschungsbereich Algorithms and Complexity