Geoinformationssysteme werden in vielen Anwendungsbereichen verwendet, wie z.B in Kartographie, Bildverarbeitung, Stadtplanung usw. Um diese mehrdimensionale räumliche Datenbank effizient zu verwalten, sind räumliche Indexstrukturen wie Quadtree, Grid File, BSP Baum usw., die als räumliche Speicherstrukturen bezeichnet werden, von großer Bedeutung. In dieser vorliegenden Arbeit wird nur den R-Baum betrachtet, der eine räumliche dynamische Indextruktur ist. Darüber hinaus wird das Splitten der R-Baum mit XFig Programm visualisiert. Die Visualisierung soll durch die Nutzung der reellen Daten von OpenStreetMap erfolgen und das Splitten soll mit dem linearen Aufwand durchgeführt werden.
Inhaltsverzeichnis
1. EINLEITUNG
1.1 Problemstellung
1.2 Kapitelübersicht
2. DER R-BAUM
2.1 Struktur des R-Baums
2.2 Algorithmen
2.2.1 Suchen
2.2.2 Einfügen
2.2.3 Löschen
2.2.4 Splitten des Knotens
2.2.5 Updates
3. XFIG
3.1 Einführung
3.2 Das Fig Format 3.2
3.2.1 Beschreibung des Fig Format 3.2
3.2.2 Beschreibung des Fig Objekte
3.2.3 Erklärung der Attributen
4. DAS PROGRAMM VISUALISIERUNGRBAUM
4.1 Einlesen der XML Datei von OpenStreetMap
4.1.1 Was ist OpenStreetMap?
4.1.2 DOM in Java
4.1.3 Implementierung des XML Einlesens
4.2 Bearbeitung der originalen Koordinaten
4.2.1 Ursprungsverschiebung
4.2.2 Skalierung unter Berücksichtigung der Geographische Breite
4.2.3 Ursprungsveränderung
4.2.4 Skalierung für eine bessere Auflösung bei Xfig
4.2.5 Implementierung der Koordinatenbearbeitung
4.3 Das R-Baum lineare Splitten
4.3.1 Klasse Building.java
4.3.2 Implementierung des Linear-Cost Algorithmus
4.4 Ausgabe in Xfig
5. ZUSAMMENFASSUNG UND AUSBLICK
Zielsetzung & Themen
Das Hauptziel dieser Arbeit ist die Entwicklung einer Java-Anwendung zur Visualisierung des R-Baum-Splitt-Algorithmus mit linearem Aufwand, wobei reale Geodaten aus OpenStreetMap als Grundlage dienen und die Ausgabe in einem für das XFig-Programm kompatiblen Format erfolgt.
- Grundlagen räumlicher Indexstrukturen am Beispiel des R-Baums.
- Methodik zur effizienten Aufteilung von räumlichen Datenknoten (Splitting-Algorithmen).
- Verarbeitung und Transformation von geografischen XML-Daten.
- Implementierung einer Schnittstelle für das vektorbasierte Grafikformat FIG.
- Visualisierung der berechneten Bounding Boxes und Split-Operationen.
Auszug aus dem Buch
4.3.2 Implementierung des Linear-Cost Algorithmus
Die detaillierte Beschreibung des Algorithmus befindet sich im Abschnitt 2.2.4. Der Linear-Cost Algorithmus erfolgt in zwei Schritten: Zuerst sollen zwei Startknoten durch Methode LinearPickSeeds in der Abbildung bestimmt werden. Dann wird die Methode FindNext in der Abbildung erstellt werden, um den nächsten Knoten für die Gruppierung auszuwählen. Der Vorgang wiederholt sich, bis alle Knoten zugeordnet werden.
• Bestimmen der zwei Startknoten
Die Methode LinearPickSeeds wird wie in der Abbildung implementiert. Mit Hilfe von die vier Methoden getMaxX(), getMinX(), getMaxY(), getMinY() von Klasse Building können alle unteren und oberen Ecken der MBBs berechnet werden(Zeile 10 bis Zeile 31). In jeder Dimension x und y sollen der Abstand der höchsten unteren und der tiefsten oberen Ecke durch Dividieren durch die entsprechende Extremrechteckseite normalisiert werden(Zeile 33). Zwei MBBs mit der größten normalisierten Abstand sind die Rückgabewerte dieser Methode, die relativ weitesten voneinander entfernt sind.
Zusammenfassung der Kapitel
1. EINLEITUNG: Es wird die Problemstellung der effizienten räumlichen Datenverwaltung beschrieben und das Ziel definiert, R-Baum-Splits mit linearem Aufwand unter Verwendung von OpenStreetMap-Daten zu visualisieren.
2. DER R-BAUM: Dieses Kapitel erläutert die dynamische Indexstruktur des R-Baums und beschreibt die grundlegenden Algorithmen zum Suchen, Einfügen, Löschen und zum Splitten von Knoten.
3. XFIG: Hier wird das Zeichenprogramm XFig sowie die Spezifikationen des nativen, textbasierten FIG-Formats 3.2 detailliert eingeführt.
4. DAS PROGRAMM VISUALISIERUNGRBAUM: Dieses Hauptkapitel beschreibt die Implementierung des Visualisierungsprogramms in Java, von der XML-Datenverarbeitung bis zur Koordinatentransformation und dem Splitting-Algorithmus.
5. ZUSAMMENFASSUNG UND AUSBLICK: Die Ergebnisse der Arbeit werden zusammengefasst und Möglichkeiten zur Erweiterung der Anwendung, wie etwa das Hinzufügen weiterer Objekttypen, aufgezeigt.
Schlüsselwörter
R-Baum, Geoinformationssysteme, Visualisierung, OpenStreetMap, XML, DOM, Linear-Cost Algorithmus, XFig, FIG-Format, Koordinatentransformation, Bounding Box, Java, Raumindex, Splitting, Geodaten.
Häufig gestellte Fragen
Worum geht es in dieser Studienarbeit grundsätzlich?
Die Arbeit befasst sich mit der Visualisierung von R-Baum-Splitting-Operationen unter Verwendung realer Gebäudedaten aus OpenStreetMap, die in einem XFig-kompatiblen Format ausgegeben werden.
Welche zentralen Themenfelder werden bearbeitet?
Die zentralen Themen sind räumliche Indexstrukturen (R-Bäume), die Verarbeitung von XML-basierten Geodaten und die automatisierte Generierung von Grafikdateien.
Was ist das primäre Ziel der Arbeit?
Ziel ist die Entwicklung einer Java-Anwendung, die Knoten in einem R-Baum effizient splittet und diesen Vorgang grafisch nachvollziehbar macht.
Welche wissenschaftliche Methode wird verwendet?
Es wird primär der Linear-Cost-Algorithmus zur Optimierung des Splittens von R-Baum-Knoten implementiert und analysiert.
Was wird im Hauptteil der Arbeit behandelt?
Der Hauptteil widmet sich der Implementierung des Programms "VisualisierungRBaum", einschließlich der XML-Analyse mittels DOM, der mathematischen Bearbeitung von Geokoordinaten und der XFig-Ausgabelogik.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind unter anderem R-Baum, OpenStreetMap, Linear-Cost-Algorithmus, Bounding Box und XFig-Format.
Warum spielt die Skalierung der Koordinaten eine so wichtige Rolle?
Da das Zielformat XFig eine spezifische Auflösung voraussetzt und Geodaten in Mercator-Projektion verzerrt sind, ist eine präzise Transformation notwendig, damit die Gebäude korrekt dargestellt werden.
Wie werden die zwei Startknoten für das Splitten bestimmt?
Die Methode "LinearPickSeeds" wählt jene zwei Knoten aus, die in einer Dimension den größten normalisierten Abstand zueinander aufweisen, um eine optimale Trennung zu erreichen.
- Quote paper
- Phuoc Trac (Author), 2013, Visualisierung des R-Baum-Splittens mit linearem Aufwand anhand von OSM-Datenauzügen und des XFig-Formats, Munich, GRIN Verlag, https://www.grin.com/document/273651
