Browsing by Author "Krumpe, Filip"

Now showing 1 - 3 of 3

Open Access
Hierarchisierung und Darstellung von Geodaten
(2014) Krumpe, Filip
Die vorliegende Arbeit beschäftigt sich mit der Darstellung von geographischen Basisdaten im Gebiet der Bundesrepublik Deutschland. Die Arbeit basiert auf zwei Datensätzen des Bundesamtes für Karthographie und Geodäsie und visualisiert sowohl Namen verschiedener geographischer Objekte (u.a. Ortsnamen, Namen von Verwaltungsgebieten) als auch den Verlauf der Grenzen von Verwaltungsgebieten (u.a. Staatsgrenzen, Bundeslandgrenzen, Gemeindegrenzen). Die Darstellung ermöglicht eine Navigation innerhalb der Daten durch Zoom und Verschieben des dargestellten Datenausschnitts und das Hinzufügen und Entfernen von Details. Um die Übersichtlichkeit der Darstellung zu gewährleisten, wurde eine Hierarchisierung der zugrundeliegenden Datensätze entwickelt und eine Filterung der anzuzeigenden Details implementiert. Zudem wurde, zur Beschleunigung der interaktiven Operationen, eine Approximation der Verwaltungsgebietsgrenzen implementiert. In der vorliegenden Arbeit werden die zugrundeliegenden Datensätze GN250 und VG250 und das UTM-Koordinatensystem, in welchem die geographischen Daten referenziert sind, beschrieben. Der Algorithmus für die Approximation der Grenzverläufe sowie die Hierarchisierung der Daten wird erläutert. Zudem wird der grundsätzliche Ablauf des Programms skizziert und zentrale Aspekte des Programms, wie der Aufbau der SHAPE-Datei, welche die Grenzverläufe enthält, und die interne Verwaltungsstruktur der geographischen Daten, beschrieben. Des Weiteren wird die Datenbank beschrieben, welche die initialen Daten bereitstellt, die beim Programmstart geladen werden. Eine Zusammenfassung und ein Ausblick auf weitere Forschungsfragen schließen die Arbeit ab.
Open Access
Labeling interactive maps
(2020) Krumpe, Filip; Funke, Stefan (Prof. Dr.)
Navigationssysteme, beziehungsweise digitale Kartenapps, haben sich zu alltäglichen Begleitern entwickelt. Waren digitale Karten vor einem Jahrzehnt ein wertvolles Gut - Updates für Navigationssysteme wurden für viel Geld verkauft- sind sie heute durch die Verbreitung von Google Maps und Co. eine Selbstverständlichkeit. Neben der Verfügbarkeit und der Möglichkeit einfacher Updates, ermöglichen digitale Karten eine einfache, intuitive Interaktion. Das Zoomen, Verschieben und Drehen des Kartenausschnitts zum Erkunden von Details und der Ausrichtung in Blickrichtung des Nutzers, sind wohlbekannte Funktionen. Letzteres ist vor allem bei Navigationssystemen zentral. Dort wird die Kartenausrichtung generell in Fortbewegungsrichtung gewählt. Insbesondere für die Darstellung von Kartenbeschriftung, stellen diese Möglichkeiten eine Herausforderung dar. In der vorliegende Arbeit wird ein Konzept zur Gestaltung von Beschriftungen in interaktiven Karten, die stufenloses Zoomen, Verschieben und Rotieren des Kartenausschnitts ermöglichen, vorgestellt. Dabei wird insbesondere die Beschriftung von sogenannten ”Points of Interest” - also zu beschriftenden Punkten - thematisiert. Derartige Beschriftungen sind gewöhnlich horizontal ausgerichtet und überlappen sich somit tendenziell bei der Kartenrotation. Vor allem beim Zoomen der Karte sind verschiedene Konsistenzkriterien zu beachten - so soll beispielsweise eine Beschriftung während eines kontinuierlichen Zoomens nicht mehrfach hinzugefügt und wieder entfernt werden. Außerdem sollen Beschriftungen von wichtigeren Punkten länger sichtbar sein, als solche von weniger wichtigen Punkten. Bei der Beschriftung von Gebieten gilt, dass sich die Beschriftung im Gebiet befinden und die grobe Form des Gebiets adaptieren soll. Um letzteres zu erreichen, darf die Beschriftung entlang eines Kreisbogens gebogen sein. Rotation ist in diesem Szenario einfach - die Beschriftung muss lediglich in ihrer Ausrightung umgekehrt werden, sodass sie nicht auf dem Kopf steht. Beim Zoomen des Kartenausschnitts sollten Gebiete als Ganzes oder ihre Untergebiete beschriftet werden, abhängig von der Kartenskala der Gebietsbeschriftung. Für der Beschriftung von Punkten werden sogenannte ”Disk-Label” eingeführt. Bei diesen wird für jede Beschriftung ein kreisförmiger Bereich um den zu beschriftenden Punkt reserviert. Die Beschriftung des Punkts bleibt in beliebigen Ausrichtungen der Karte vollständig in diesem Bereich enthalten. Indem als Beschriftung in einer beliebigen Kartenskala eine überschneidungsfreie Untermenge der ”Disk-Label” gewählt wird, ist die lesbare Darstellung bei Rotation gewährleistet. Beim Herauszoomen aus dem Kartenausschnitt, werden die Beschriftungen bei konstanter Größe beibehalten. Entsprechend wachsen die zugehörigen Disks relativ zur Karte - entsprechend schrumpfen die Distanzen zwischen den Disks. Bei fortschreitendem Zoomen, kommt es zu Berührungen der Disks. Dabei muss eine der beteiligten Beschriftungen muss entfernt, um bei weiterem Zoomen die überschneidungsfreiheit zu erhalten. Wird der entsprechende Zoomprozess von ”unendlich 107weit hineingezoomt” zu ”unendlich weit herausgezoomt” betrachtet, ergibt sich eine sogenannte Eliminationssequenz der Beschriftungen. Diese kann für einen Datensatz im Voraus berechnet werden und ermöglicht dann eine einfache, effiziente Ableitung einer Kartenbeschriftung für ein gegebenes Darstellungszenario. Das Problem der Berechnung der Eliminationssequenzen kann verallgemeinert in einem d-dimensionalen Hyperraum betrachtet werden. Entsprechend der Disks in 2D, wachsen d-dimensionalen Hyperbälle. Eine Eiminationssequenz ist dabei nicht eindeutig - kollidieren Bälle der selben Wichtigkeit, ist die Entscheidung welcher der beiden Bälle eliminiert wird, essentiell für den weiteren Verlauf der Sequenz. Das Ziel ist die Berechnung einer optimalen Sequenz, in der die Summe aller Eliminationszeitpunkte maximiert wird. Es wird gezeit, dass die Berechnung einer solchen optimalen Sequenz N P − hart ist. Für ein vereinfachtes Szenario - in welchem die Sequenz eindeutig ist - wird ein effizientes Berechnungsverfahren vorgestellt und analysiert. Dieses Verfahren hängt stark von einer effizienten Methode zur Berechnung des nächsten Nachbarn sowie der Suche nach Punkten mit einer maximalen Distanz zu einem gegebenen Punkt ab. Je nach Szenario können diese Operationen effizienter oder weniger effizient gelöst werden. Für 2D und für höhere Dimmensionen werden zwei verschiedene theoretische Laufzeitschranken bewiesen. Für die praktische Beschriftung von digitalen Karten, werden Punkte auf einem virtuellen Globus betrachtet. Eine Berechnung der Sequenz für 13 Millionen Punkte ist auf einem herkömmlichen Computer in etwa 15 Minuten möglich. Das ursprüngliche, unvereinfachte Problem kann mittels eines Mixed-Integer Linearen Programms für wenige Punkte exakt gelöst werden. Allerdings nur mit erheblichem Rechen- und Speicheraufwand. Eine gute Approximation der optimalen Sequenz bieten Heuristiken. Mittels dieser kann der vorgestellte Algorithmus für das vereinfachte Szenario Lösungen für das unvereinfachte Problem berechnen. In der Güte liegen die Heuristiken bei 5% − 10% unter dem Optimum. Bei Berechnungszeiten von 15 − 20 Minuten auf einem herkömmlichen Computer. Eine Gebietsbeschriftung liegt vollständig innerhalb des Gebiets und ahmt die Form des Gebiets nach, indem sie entlang eines Kreisbogens plaziert ist. Für eine gute Beschriftung ist eine entsprechende Platzierung gesucht, welche die Größe der Beschriftung maximiert. Abhängig davon kann eine maximale und minimale Kartenskala berechnet werden, bei welcher die Beschriftung lesbar dargestellt werden kann. Entsprechend kann das Gebiet bei größeren Skalen in einer weiteren Verfeinerung dargestellt, oder bei kleineren Skalen durch eine Punkt-Beschriftung oder die Darstellung eines umfassenden Gebiets ersetzt werden. Für die Berechnung einer solchen guten Beschriftung wird in der vorliegenden Arbeit ein effizienter Algorithmus vorgestellt. Dieser basiert auf einem Algorithmus von 2001, von M. Barrault in [Mat01] publiziert. Durch verschiedene Optimierungen kann diese Berechnung auf Quasi-Echtzeit verbessert werden.
Open Access
Offline-Speicherung und Darstellung von Geodaten auf Mobilgeräten
(2014) Krumpe, Filip
Die Visualisierung von großen Mengen geographischer Basisdaten, wie Stadtnamen und Verwaltungsgebieten, ist mit verschiedenen Problemen verbunden. Werden zu viele Daten und Details auf zu kleinem Raum dargestellt, kann die Übersichtlichkeit der Darstellung leiden oder Überdeckung die Wahrnehmbarkeit einzelner Objekte stören. Ist eine Interaktion mit der Visualisierung möglich (beispielsweise durch verschieben, rotieren und zoomen des betrachteten Ausschnitts), kann eine große Menge an darzustellenden Daten Performanceprobleme verursachen und eine verzögerungsfreie Interaktion verhindern. Die vorliegende Diplomarbeit beschäftigt sich mit der Visualisierung von Ortslagen und Grenzsegmenten von Verwaltungsgebieten der Bundesrepublik Deutschland. In der Arbeit werden zwei Methoden entwickelt, um die entsprechenden Daten zu strukturieren und zu speichern. Die entwickelten Datenstrukturen ermöglichen eine einfache Ableitung von Teilmengen der gespeicherten Daten, die in einer Visualisierung konfliktfrei und gut wahrnehmbar dargestellt werden können. Für die Speicherung der Daten wird ein binäres Dateiformat entwickelt, das eine kompakte Speicherung der Datenstrukturen ermöglicht. Die Grenzsegmente der Verwaltungsgebiete können abhängig von ihrer Zugehörigkeit zu verschiedenen Verwaltungsebenen abgefragt werden. Um den Aufwand für das Zeichnen der Segmente zu verringern, können sie in verschiedenen Generalisierungsstufen abgefragt werden. Im Rahmen der Diplomarbeit wurden, basierend auf den entwickelten Datenstrukturen, zwei Visualisierungen der Daten entwickelt. Sie ermöglichen ein interaktives Erkunden der Datensätze mittels Verschiebung, Rotation und Zoom des dargestellten Datenausschnitts in Echtzeit auf einem PC und einem Android Gerät.