Visualisierung des R-Baum-Splittens mit linearem Aufwand anhand von OSM-Datenauzügen und des XFig-Formats

Inhaltsverzeichnis

Verzeichnis der Abkürzungen

Verzeichnis der Abbildungen

Verzeichnis der Tabellen

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.1 Beschreibung des Fig Format
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

Literaturen

Verzeichnis der Abkürzungen

Abbildung in dieser Leseprobe nicht enthalten

Verzeichnis der Abbildungen

Abbildung 1: Struktur eines R-Baums

Abbildung 2 : Suche in R-Bäumen

Abbildung 3: Einfügen in R-Bäumen

Abbildung 4: Löschen in R-Bäumen

Abbildung 5 : Schlechtes Split

Abbildung 6: Gutes Split

Abbildung 7: Identische Aufteilungen

Abbildung 8: Wählen zwei Startknoten bei Linear-Cost Algorithmus

Abbildung 9: Klassendiagramm von dem Programm VisualisierungRBaum

Abbildung 10: Übersicht von einer .osm Datei

Abbildung 11: Vereinfachte Darstellung des OSM Datenmodells

Abbildung 12: Beispiel von einem Node-Objekt

Abbildung 13 : Beispiel von einem Way-Objekt

Abbildung 14 : Beispiel von einem Relation-Objekt

Abbildung 15: Methode von Node

Abbildung 16: Methoden von Element

Abbildung 17: Quellcode von Klasse Util

Abbildung 18: Quellcode zum Einlesen von XML Datei in main Methode

Abbildung 19: Die Längen- und Breitengrade auf der Erde

Abbildung 20: Verzerrung der Objekte in Ost-West-Richtung

Abbildung 21: Quellcode von Klasse Point

Abbildung 22: Quellcode der Bearbeitung der originalen Koordinaten

Abbildung 23: Übersicht von Klasse Building

Abbildung 24: Quellcode der Auswahl zweier Startknoten

Abbildung 25: Quellcode der Zuordnung der übrigen Knoten

Abbildung 26: Flussdiagramm von Splitten-Algorithmus

Abbildung 27: Quellcode der Implementierung der Ausgabe in Fig Format

Abbildung 28: Ausgabe in Winfig

Verzeichnis der Tabellen

Tabelle 1: Die erste Nichtkommentarzeile von Fig Format

Tabelle 2: Objekte von XFig

Tabelle 3: Beschreibung von color pseudo-Objekt

Tabelle 4: Beschreibung der ersten Zeile von Arc-Objekt

Tabelle 5: Beschreibung der Zeile von Vorwärtspfeil oder Rückwärtspfeil

Tabelle 6: Beschreibung der ersten Zeile von Compound-Objekt

Tabelle 7: Beschreibung der nachfolgenden Zeilen von Compound-Objekt

Tabelle 8: Beschreibung von Ellipse-Objekt

Tabelle 9: Beschreibung der ersten Zeile von Polyline-Objekt

Tabelle 10: Zeile für sub_type 5 von Polyline-Objekt

Tabelle 11: Zeile für Punkte von Polyline-Objekt

Tabelle 12: Beschreibung der ersten Zeile von Spline-Objekt

Tabelle 13: Beschreibung von Text-Objekt

Tabelle 14: font_flags bei Text-Objekt

Tabelle 15: LaTeX Schriftart bei Text-Objekt

Tabelle 16: PostScript Schriftart bei Text-Objekt

Tabelle 17: Farbcodes von pen_color und fill_color.

Tabelle 18: Farbcodes von area_fill für fill_color Weiß

Tabelle 19: Farbcodes von area_fill für fill_color Schwarz

Tabelle 20: Farbcodes von area_fill für alle anderen fill_color

Tabelle 21: Farbcodes von line_style

Tabelle 22: Farbcodes von join_style

Tabelle 23: Farbcodes von cap_style

Tabelle 24: Farbcodes von arrow_style

1. Einleitung

1.1 Problemstellung

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.

1.2 Kapitelübersicht

Im zweiten Kapitel wird zunächst die Grundkenntnis des R-Baums dargestellt. Dann werden seine Algorithmen mit Beispielen beschrieben, indem der Linear-Cost Algorithmus im 2.2.4 als wichtigste betrachtet werden soll, denn er ist das Werkzeug der Visualisierung.

Weiterhin stellt sich das dritte Kapitel das Zeichnungsprogramm Xfig vor und beschriebt das Fig Format 3.2.

Im Kapitel 4 wird die Implementierung des Programms VisualisierungRBaum erläutert. Das Programm unterteilt sich in vier Schritten:

- Einlesen der XML Datei von OpenStreetMap(OSM)
- Bearbeitung der originalen Koordinaten
- Der Splitten Algorithmus
- Ausgabe in Fig Format

Dabei werden die Begriffe OpenStreetMap und Document Object Model vorgestellt und verschiedene Ausschnitte des Quellcode angezeigt.

Anschließend folgen die Zusammenfassung und Ausblick im Kapitel 5, in dem die Erkenntnisse und Ergebnisse dieser Arbeit noch einmal wiederholt und die Erweiterungsmöglichkeiten aus eigener Meinung gegeben werden.

2. Der R-Baum

2.1 Struktur des R-Baums

Der R-Baum ist eine mehr dimensionale räumliche Indexstruktur, welcher im Aufbau dem B-Baum ähnlich ist^[1]. Er besteht aus allen Verweisen auf Datenobjekte in seinen Blättern und die Blätter liegen alle auf derselben Höhe. Die Indexstruktur ist dynamisch, deswegen wird die Abwechslung der unterschiedlichen Aktionen wie Suchen und Einfügen erlaubt, ohne die Notwendigkeit einer periodischen Reorganisation des Baumes zu benötigen.

Die räumlichen Datenobjekte werden von minimalen Rechtecken beinhaltet und in den Blattknoten gespeichert. Diese minimalen Rechtecke wird „minimal bounding boxes“ (MBB) oder auf Englisch „minimum bounding rectangle“ (MBR) genannt. Ein MBB wird durch das Minimum und Maximum in jeder einzelnen Dimension repräsentiert.

Die Struktur des R-Baums soll folgende Eigenschaften erfüllen^[2]:

- Alle Blätter haben zwischen m und M Einträge, wobei m €[0, M/2].
- Für jeden Eintrag in einem Blatt ist MBB das kleinste umgebende Rechteck, das das n-dimensionale Datenobjekt beinhaltet.
- Jeder innere Knoten, der kein Blattknoten ist, hat zwischen m und M Söhne.
- Alle inneren Knoten verfügen über Rechtecke, jene die Rechtecke im Kinderknoten beinhalten.
- Die Wurzel hat mindestens zwei Söhne, wenn er kein Blatt ist.
- Alle Blätter befinden sich auf der gleichen Ebene.

Die Abbildung 1 zeigt ein Beispiel einer räumlichen Struktur mit zugehörigem R-Baum.

Es stellen sich wie beim B-Baum verschiedene Algorithmen wie Suchen, Einfügen und Löschen eines Datenobjektes zur Verfügung. Das Splitten eines Knotens wird dann notwendig, wenn die maximale Anzahl an Indexeinträgen überschritten wird. Dann soll das Splitten eines Knoten eingeführt werden. Im Abschnitt 2.2 werden die o.g. Algorithmen näher beschrieben und anhand von Beispielen anschaulich dargestellt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1: Struktur eines R-Baums.

2.2 Algorithmen

2.2.1 Suchen

Ähnlich wie beim B-Baum ist die Suche in einem R-Baum ist ein rekursiver Vorgang bei dem das gesuchte Datenobjekt von der Wurzel zu den Blättern durchsucht wird. Zu einem Zeitpunkt wird ein Pfad durchlaufen. Wenn sich das gesuchte Datenobjekt nicht in diesem Teilbaum befindet, so wird der nächste Suchpfad durchlaufen. Da die Pfadauswahl ist beliebig müssen im schlimmsten Fall alle Pfade durchlaufen werden, bis das gesuchte Datenobjekt gefunden wird.

Gegeben ist ein R-Baum mit einer Wurzel T. Gesucht werden alle Indexeinträge, die das Suchrechteck S schneiden. Der Suchalgorithmus nach Guttman wird nun vorgestellt^[3]:

S1 Suche in inneren Knoten:

- Für jeden Eintrag prüfen, ob seine MBB überschneidet S.
- Für alle überschneidenden Einträge setze die Suche in allen seinen untergeordneten Knoten fort.
S2 Suche im Blattknoten:
- Für jeden Eintrag prüfen, ob seine MBR überschneidet S. Wenn ja, so ist dies der gesuchte Eintrag.

Die Suchalgorithmen für R-Bäume sind die am effizientesten, wenn Überlappung und Bedeckung minimiert werden.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2 : Suche in R-Bäumen

In dem obigen Beispiel befindet das Suchobjekt O auf der Datenseite B. Zunächst wird jeder Eintrag geprüft, ob er O überschneidet. Wenn ja, wird die Suche nach inneren Söhnen fortgesetzt. Wenn nicht, lässt sich der nächste Pfad prüfen, bis O gefunden wird. Hier ist B die einzige Lösung, da nur in B das gesuchte Objekt O schließlich gefunden wird.

2.2.2 Einfügen

Bei dem Einfügen eines Datenpunktes oder eines Datenobjektes in einem bestehenden R-Baum stehen folgende Schritte zur Verfügung^[4]:

- Zunächst wird die beste Kindseite (ChooseLeaf) nach bestimmten räumlichen Kriterien gesucht. (bei mehreren Kandidaten zuerst den mit der geringeren Gesamtfläche, dann den mit weniger Einträgen)
- Der Datenpunkt oder Datenobjekt wird dann eingefügt, wenn auf der Kindseite Platz ist, d. h. wenn die maximale Anzahl M an Einträgen nicht überschritten wird.
- Wenn kein Platz auf der Kindseite ist, wird die Kindseite anhand einer Überlaufbehandlung gesplittet .Hierfür kommen verschiedene Split-Algorithmen, die in Abschnitt 2.2.4 näher eingegangen werden. Bei dem Splitten soll der tote Raum möglichst klein und die Überlappung minimal sein, damit die Performance nicht unnötig eingeschränkt wird.
- Das neue Objekt im Vaterknoten wird rekursiv angepasst (AdjustTree)
- Es kann passieren, dass der Baum bis zur Wurzel gesplittet werden muss. Bei dem Splitten der Wurzel wird dann eine neue Wurzel erstellt, deren Kinder die beiden neuberechneten Knoten sind.

Abbildung 3 stellt das Einfügen zwei neuer Knoten F und G dar, indem G als der Überlauf behandelt werden soll.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3: Einfügen in R-Bäumen^[5]

2.2.3 Löschen

Das Löschen eines Eintrages wurde von Antonin Gutman wie folgende dargestellt^[6]:

- Zunächst wird das Blatt, das den zu löschenden Eintrag enthält, gesucht.
- Dann wird der Eintrag aus dem Blatt gelöscht.
-Falls das Blatt weiterhin über mehr als m Einträge verfügt: wird die Vaterknoten aktualisiert - Falls der Knoten kleiner als die minimale Anzahl m ist, wird der Baum wie folgt reorganisiert: Zunächst werden alle Knoten außer der Wurzel, die zu wenig Einträge haben, gesucht. Danach werden diese entfernt und die Vaterknoten angepasst. Anschließend werden die Einträge der entfernten Knoten mittels des Einfügen- Algorithmus im Abschnitt 2.2.2 auf gleicher Ebene wieder eingefügt.
- Wenn die Wurzel nur noch einen Sohn hat, nachdem der Baum angepasst wurde, wird dieser zur neuen Wurze zugeordnetl.

Im Folgenden Beispiel wird der Eintrag 5 gelöscht (m=2, M=4).

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4: Löschen in R-Bäumen

2.2.4 Splitten des Knotens

Wie bereits in Abschnitt 2.2.2 erwähnt, kann ein Knoten durch das Einfügen eines Datenobjektes überlauft werden. Wenn die maximale Anzahl M der Einträge überschritten wird, müssen die Einträge auf zwei Knoten verteilt werden. Bei der Behandlung des Knotenüberlaufs sollen zwei Kriterien erfüllt werden. Zum einen soll die Gesamtfläche der beiden neuen Knoten möglichst klein gehalten werden, damit der tote Raum möglichst klein sein kann, und zum anderen soll die Überlappung der Knoten minimiert werden^[7]. Jedoch ist es nicht immer möglich beide Ziele zu erreichen, wie in die beiden folgenden Abbildungen.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 5 : Schlechtes Split

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 6: Gutes Split

Bei der Abbildung 5 gibt es keine Überlappung zwischen beiden Knoten, jedoch ist der tote Raum groß. Umgekehrt ist der tote Raum in Abbildung 6 minimiert, obwohl dieses Split Überlappung verursacht.

Manchmal ist es schwierig das gute Split zu finden. Im schlechtesten Fall sind die beiden neuen Knoten mit dem Vaterknoten identisch.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 7: Identische Aufteilungen

Im obigen Fall sind die beiden neue Knoten , egal wie die vier Knoten in zwei Gruppen unterteilt werden, identisch mit dem Vaterknoten .Die Überlappung ist somit unvermeidbar.

Guttman hat die drei Algorithmen für das Splitten eines Knotens, der Exhaustive Algorithmus, der Quadratic-Cost Algorithmus und der Linear-Cost Algorithmus, entwickelt. Der Schwerpunkt liegt auf dem Linear-Cost Algorithmus, denn er wird für unser Hauptprogramm verwendet.

Der Exhaustive Algorithmus ist der einfachste Algorithmus:

- Zuerst werden alle möglichen Splits berechnet.
- Der beste Split mit der geringsten Gesamtfläche wird ausgewählt.

Allerdings beträgt die Anzahl der Möglichkeiten -1, deswegen ist dieser Algorithmus die schlechte Auswahl für eine Implementierung eines R-Baums.

Der Quadratic-Cost Algorithmus versucht eine gute Aufteilung mit einer möglichst kleinen Gesamtfläche zu finden:

- Bestimmen der zwei Startknoten (PickSeeds): Für jedes Paar von Objekten soll der Flächeninhalt seiner MBB berechnet werden Das Paar mit dem größten MBB wird ausgewählt. Wenn diese Objekte dem gleichen Knoten nicht gehören, werden sie als zwei Startknoten verwendet.
- Zuordnung der übrigen Objekte(PickNext): Für alle anderen Objekte wird die Differenz von zwei Gesamtflächenvergrößerungen der neue MBBs berechnet, wenn das Objekt zu den beiden Startknoten hinzugefügt wird. Das Objekt mit der größten Differenz wird ausgewählt und zu einem von beiden Knoten mit der geringsten Flächenvergrößerung eingefügt. Die beiden Startknoten sollen dadurch aktualisiert werden. Für alle übrigen Objekte soll der Vorgang wiederholt werden, bis alle Objekte den zwei Gruppen zugeordnet sind.

Der Quadratic-Cost Algorithmus garantiert nicht wie beim Exhaustive Algorithmus die kleinstmögliche Fläche. Die Kosten des Quadratic-Cost Algorithmus liegen bei O( ).

Der Linear-Cost Algorithmus Dieser Algorithmus ähnelt dem Quadratic-Cost Algorithmus, aber der PickSeed Schritt wird durch andere Kriterien durchgeführt.

- Bestimmen der zwei Startknoten (PickSeeds):
- Finde nach extremen Rechtecken in allen Dimensionen: In jeder Dimension wird der Eintrag mit der höchsten unteren und der tiefsten oberen Ecke gesucht. Der Abstand wird gespeichert.
- Berechne den Abstand und normalisiere ihn: Die Abstände werden durch Dividieren durch gesamte Breite der Rechteckmenge entlang der entsprechenden Dimensionen normiert.
- Wahl des extremsten Paares: Wähle das Paar mit der größten normalisierten Distanz in einer Dimension.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 8: Wählen zwei Startknoten bei Linear-Cost Algorithmus

In Abbildung 7 würden B und D als Startknoten ausgewählt, wenn x/X größer als y/Y wäre. Sonst wird das Paare A und C ausgewählt.

- Zuordnung der übrigen Objekte(PickNext): Der PickNext Schritt in dem Linear-Cost Algorithmus ist ähnlich wie beim Quadratic-Cost Algorithmus.

Die Laufzeit ist linear zu M und der Anzahl der Dimensionen. Ähnlich wie Quadratic-Cost Algorithmus wird hier die Überlappung minimiert. Wegen der genannten Vorteile wird er den anderen beiden meist vorgezogen. Wie bereits erwähnt, bei der Visualisierung des R-Baum-Splits wird dieser Algorithmus verwendet, um viele Knoten in zwei Gruppen zu unterteilen. Dieser Algorithmus spielt eine wichtige Rolle in dieser Arbeit, um die R-Baum-Split zu visualisieren. Im Abschnitt 4.3.2 werden die beiden Schritte PickSeeds und PickNext durch zwei Methoden LinearPickSeeds und FindNext in Java Sprache programmiert.

2.2.5 Updates

Wird ein Datenobjekt aktualisiert und dadurch sein minimal umgebendes Rechteck sich verändert, muss sein Eintrag im Baum durch das Löschen Algorithmus in 2.2.3 entfernt, durch das Einfügen Algorithmus in 2.2.2 neu eingefügt werden, damit das Datenobjekt den richtigen Platz im Baum bekommen kann.

3. XFig

3.1 Einführung

Xfig ist ein interaktives Zeichenprogramm, das unter dem X-Window-System Version 11 Release 4 (X11R4), auf den meisten UNIX-kompatiblen Plattformen und z. B. unter Darwin auf dem Macintosh und einem X-Server unter Microsoft Windows läuft.

Xfig Dateien kann auch auf anderen Betriebssystemen genutzt werden. Beispielsweise können .fig-Dateien mit Hilfe des Programms JFig auf allen Plattformen, auf denen Java zur Verfügung steht, genutzt werden. Außerdem können Xfig Dateien mit WinFig bearbeitet werden, bei dem Windows-Funktionen wie Zwischenablage, Drucker Vorschau, mehrere Dokumente usw. genutzt werden.

Mit Xfig kann Figuren aus den Objekten wie Kreise, Rechtecke, Linien, Splinte, Texte usw. gezeichnet werden. Es ist auch möglich, Bilder in Formaten wie GIF, JPEG, EPS, PostScript, usw. zu importieren. Diese Objekte können erstellt, gelöscht, verschoben oder ergänzt werden. Attribute wie Farben oder Linienstil (line_style) kann auf verschiedenen Arten ausgewählt werden. Für den eingefügten Text stehen 35 Schriftarten zur Verfügung

Xfig speichert Figuren in seinem textbasierten, nativen Fig Format, das kann aber mit Hilfe des Transfig Programmes in verschiedene andere Formate wie PostScript, PDF, GIF, JPEG usw. exportiert werden. Durch die Einbindung von Transfig Paket http://www.xfig.org/userman/installation.html können die Zeichnungen mit LaTeX Beschriftungen versehen werden können, so dass die Ausgabe in ein graphischer Teil (PostScript , PDF) und ein textueller Teil mit LaTeX-Kommandos erfolgen kann.^[8]

Um den R-Baum zu visualisieren soll ein XFig Datei mit Fig Format 3.2, das in dem nächsten Abschnitt näher beschrieben wird, erstellt werden. Eine detaillierte Beschreibung des Fig Formats kann unter http://www.xfig.org/userman/fig-format.html gefunden werden.

3.2 Das Fig Format 3.2

3.2.1 Beschreibung des Fig Format 3.2

(1) Die erste Zeile ist eine Kommentarzeile, die den Name und Version zeigt: #FIG 3.2
(2) Die erste Nichtkommentarzeile besteht aus folgenden Komponenten:^[9]

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Die erste Nichtkommentarzeile von Fig Format.

Fig_resolution ist die Auflösung der Figur in der Datei. Fig Datei ist immer mit einer Auflösung von 1200ppi, deshalb werden die Figuren mit der anderen Auflösung skaliert. Pixel werden als quadratisch sein.

Die coordinate_system Variable wird ignoriert, d.h. der Ursprung ist immer die obere linke Ecke. Die Koordinaten werden in "fig_resolution" Einheiten angegeben. Die Linienbreite (thickness) wird in 1/80 Zoll (0.3175mm) oder 1 Bildschirm-Pixel angegeben. Beim Export in EPS, PostScript oder Bitmap-Format wird Linienbreite auf 1/160 Zoll (0.159mm) auf "heller" Aussehen reduziert.

(3) Der Rest der Fig Datei enthält verschiedene Objekte, die sich in sieben Klassen unterscheiden:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Objekte von XFig.

Eine detaillierte Beschreibung von allen oben genannten Objekten kommt im Abschnitt 3.2.2 in Betracht. Danach werden die verschiedenen Werte von ihren zugehörigen Attributen im Abschnitt 2.2.3 erläutert.

3.2.2 Beschreibung des Fig Objekte

3.2.2.1 Color pseudo-Objekt

Diese wird für benutzerdefinierten Farben verwendet, die nicht unter der 32 Standardfarben sind und soll vor allen anderen Fig Objekte definiert werden.

- Erste Zeile:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 3: Beschreibung von color pseudo-Objekt.

3.2.2.2 Arc

- Erste Zeile:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 4: Beschreibung der ersten Zeile von Arc-Objekt.

- Außerdem können sich die Zeile von Vorwärtspfeil(sowie Rückwärtspfeil) befinden, wenn foward_arrow(backward_arrow) 1 beträgt.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 5: Beschreibung der Zeile von Vorwärtspfeil oder Rückwärtspfeil.

3.2.2.3 Compound- Objekt

- Erste Zeile:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 6: Beschreibung der ersten Zeile von Compound-Objekt.

- Nachfolgende Zeilen:

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 7: Beschreibung der nachfolgenden Zeilen von Compound-Objekt.

[...]

---

^[1] Vgl. (Guttman, 1984)

^[2] Vgl. (Guttman, 1984)

^[3] Vgl. (Guttman, 1984)

^[4] Vgl. (Guttman, 1984)

^[5] Vgl. (fergi.uni-osnabrueck.de/module/geodatenbanksysteme/)

^[6] Vgl. (Guttman, 1984)

^[7] Vgl. (Guttman, 1984)

^[8] Vgl. (xfig.org)

^[9] Vgl. (xfig.org)