6 Konzeptionelle Betrachtung eines zeitintegrativen GIS

Für die nun folgende konzeptionelle Diskussion wurden folgende Einschränkungen getrof­fen:

1. Obwohl der Begriff ”Raum” in der Regel mit einem dreidimensionalen Bezugsrahmen assoziiert wird, erfolgt hier eine Beschränkung auf den zweidimensionalen Fall der Ebene. Die Modellierung dreidimensionaler Koordinaten unterscheidet sich nicht prin­zipiell von ebenen Daten, bedeutet aber einen erheblich höheren Verwaltungsaufwand.

2. Als geometrische Datenstruktur werden ausschließlich Vektordaten betrachtet. Die Verarbeitung von Rasterdaten ist nicht vorgesehen.

3. Zeit wird aus Vereinfachungsgründen lediglich in Form der Weltzeit (valid-time) er­faßt. Die zweite in Kapitel 5.2.1 angesprochene Zeitdimension, die Datenbankzeit, soll hier nicht berücksichtigt werden.

4. Die zeitliche Variabilität wird ausschließlich für räumliche Attribute thematisiert. Für eine Diskussion über die Erfassung zeitlicher Bezüge in Standardtypen sei an dieser Stelle beispielsweise auf DYRESON/ SNODGRASS 1992 und JENSEN/SNODGRASS 1996 verwiesen.

Die hier getroffenen Einschränkungen stellen aber nicht das Modell an sich in Frage, son­dern betreffen lediglich theoretisch zwar wünschenswerte, aber nach praxisrelevanter Ein­schätzung nur unter größtem Aufwand realisierbare Eigenschaften. In einem späteren Ab­schnitt sollen einige dieser Aspekte aufgegriffen und mögliche Lösungsansätze vorgestellt werden.

Abbildung 24: Übersicht



Quelle: Eigener Entwurf

Die notwendigen Komponenten der räumlichen Datenverwaltung lassen sich grob in drei Blöcke gliedern (vgl. Abbildung 24):

1. Das geometrische Modell verwaltet die geometrischen Daten in Form von diskreti­sierten Vektoren. Topologische Verknüpfungen werden auf dieser Ebene nicht explizit aufgebaut.

2. Das räumlich-temporale Modell erfaßt die Entitäten hinsichtlich ihrer räumlichen Eigen­schaften sowie ihrem zeitlichen Bezug. Hier wird zwischen einfach strukturier­ten Objekten („Spaghetti-Daten“) sowie topologisch strukturierten Objekten unter­schieden.

3. Das thematische Modell behandelt primär die semantischen Aspekte der Datenmodel­lierung. Hier können die Begriffe der Anwendungsproblematik wie ”Baublock”, ”Straßensegment” oder ”Staatsgebiet” abgebildet und über Attribute beschrieben wer­den.

Im Folgenden sollen die grundsätzlichen Zusammenhänge und spezifischen Probleme der einzelnen Ebenen dargestellt werden, um sie im nächsten Kapitel in ein objektorientiertes Datenmodell zu überführen.

6.1 Verwaltung der Geometrie-Daten

6.1.1 Geometrische Datenbasis

Das geometrische Modell verwaltet die Koordinatenwerte, die durch die Zuordnung zu einem Koordinatensystem als Positionen auf der Erdoberfläche interpretiert werden kön­nen. Zusätzliche Informationen zu den Geometrien finden sich in den Metadaten, die eine Geometriemenge hinsichtlich ihrer Qualität, Herkunft und und weiteren Eigenschaften beschreiben.

Die Vorschläge in der Literatur zur Verwaltung geometrischer und topologischer Daten konzentrieren sich vorrangig auf zwei Ansätze:

Simplizialkomplexe

Der erste Ansatz gründet auf der algebraischen Topologie nach ALEXANDROFF 1961 und verwendet Simplizialkomplexe, um damit die Datenebene auf diskrete Symbole zu reduzieren, die räumliche Konfigurationen repräsentieren (vgl. FRANK/ KUHN 1986).

Abbildung 25: Simplexe

Quelle: HÖLBLING 1996, S.10

Eine endliche Menge der in Abbildung 25 dargestellten Simplexe bilden einen Simplizial­komplex. Räumliche Operationen können damit algebraisch gelöst werden, indem beispielsweise die Suche nach dem Schnittpunkt zweier Linien durch die Bestimmung des gemeinsamen Knoten vollzogen werden kann (SCHNEIDER 1995, S. 55ff.; BITTNER/ FRANK 1997, S.20). Anschaulich betrachtet werden bei diesem Verfahren z.B. Polygon-Coverages durch eine Triangulation in einzelne Dreiecke zerlegt, die durch eine Knoten-Kanten-Struktur repräsentiert sind.

Realms

Das Konzept der Realms (GÜTING/ SCHNEIDER 1993) verwendet eine endliche Punktmenge und schnittpunktfreie Liniensegmente auf einem diskreten Gitter und kann damit als ein planarer Graph angesehen werden. Geo-Objekte können auf dieser Grund­lage definiert werden, indem man aus den Punkten und Liniensegmente die entsprechende Repräsentation kombiniert. (SCHNEIDER 1995, S. 69ff.; vgl. Abbildung 26)

Abbildung 26: Diskrete Geometriedarstellung als Realm

Quelle: SCHNEIDER 1995, S. 70

In der vorliegende Arbeit soll in Anlehnung an GÜTING/ SCHNEIDER 1993 folgende Verfahrensweise angewendet werden:

In Vektorsystemen sind einzelne Punkte die Träger der positionsbezogenen Daten. Zu­sammengehörige Punkte, die eine Linie oder die Umrandung einer Fläche darstellen, wer­den zu geordneten Punktsequenzen zusammengefaßt. In einem objektorientierten GIS können Einzelpunkte als atomare Objekte und Sequenzen als komplexe Objekte modelliert werden, auf die Instanzen der Geo-Objekt-Klassen Referenzen einrichten. Folglich bilden auf dieser Ebene nur Punkte und Linien zulässige Elemente. Die Interpretation, daß eine Punktsequenz eine Polygonumrandung und deshalb eine Fläche darstellt, erfolgt erst auf der Ebene der Geo-Objekte. Eine zusätzliche Integritätsbedingung gilt für die Geometrien der topologisch-strukturierten Geo-Objekte: hier werden sich schneidende Linien unter­brochen und die dabei entstehenden Teilstücke über einen Schnittpunkt miteinander ver­bunden.

6.1.2 Diskretisierung reeller Koordinatenwerte

Grundlage geometrischer Operationen ist ein robustes numerisches System, das systemimmanente Fehlerquellen nach einem geeigneten Regelwerk behandelt. Geo­metrische Operationen in Geographischen Informationssystemen verwenden üblicher­weise Funktionen der analytischen Geometrie, die auf einem kontinuierlichen Koordinatensystem definiert sind. In der Implementierung muß aber berücksichtigt wer­den, daß Computer Zahlen in endlichen Speicherbereichen ablegen und damit nur diskrete Punkte abbilden können, d.h. reelle Zahlen werden entsprechend gerundet. Dieses Pro­blem betrifft vor allem den Schnitt zweier Geraden, da der gespeicherte Schnittpunkt von dem geometrisch korrekten Punkt abweichen kann. Die Verwendung eines größeren Speicher­bereiches für die Koordinatenwerte, was einer Erhöhung der Anzahl der Nach­kommastellen entspricht, löst das Problem nicht, sondern verringert nur die Häufigkeit des Auftretens (HÖLBLING 1996, S.1f.; GÜTING/ SCHNEIDER 1993, S. 16f.).

Anschaulich betrachtet stellt die Menge der abbildbaren Punkte keine unendliche Menge dar wie in der analytischen Geometrie, sondern ein feines Raster regelmäßig angeordneter Punkte. Kommt der Schnittpunkt zweier Geraden nicht zufällig auf einem Rasterpunkt zu liegen, wird er durch die Koordinatenrundung auf einen solchen verschoben. Da das be­schriebene Raster sehr fein ist, wird diese Verschiebung häufig keine gravierenden Folgen für die Konsistenz der Daten haben. Es sind aber auch Situation möglich, in denen vor allem die topologischen Beziehungen räumlicher Objekte hiervon betroffen sind (GÜTING/ SCHNEIDER 1993, S. 17f.).

Abbildung 27: Kontinuierlicher Geradenschnitt über diskreter Zahlenebene

Quelle: Nach HÖLBLING 1996, S.16, verändert

Abbildung 27 zeigt den Schnitt zweier Geraden a und b und die daraus resultierenden Liniensegmente a´ und b´. Von der Verlagerung des Schnittpunktes S auf das diskrete Raster ist die relative Lage des Punktes P zur Geraden b betroffen, der nach dem Schnitt auf der gegenüberliegenden Seite von b´ liegt. Ist b ein Teil eines Polygonrandes und P zunächst innerhalb des Polygons, so liegt der Punkt P nach dem Schnitt außerhalb des Polygons (z.B. einem Grundstück). Weitere Probleme ergeben sich durch das hinterein­anderfolgende Schneiden einer Geraden mit mehreren anderen Geraden. Wie aus Abbildung 28 ersichtlich kann der Fall eintreten, daß der nächste Rasterpunkt immer oberhalb der Ausgangslinie liegt und die Segmente in eine Richtung ”wegdriften”, wobei sich der Fehler weiter fortpflanzt (HÖLBLING 1996, S. 3f.).

Abbildung 28: Problem des wandernden Geradensegmentes

Quelle: HÖLBLING 1996, S.4

Solche Schnittprobleme mit nachfolgenden Inkonsistenzen sind in einem temporalen GIS dann von höherer Relevanz als in einem konventionellen GIS, wenn die Objektgeometrien für verschiedene Zeitabschnitte nicht vollständig erfaßt werden, sondern als Ver­änderungen zu einem vorhergehenden Zustand. Bei dieser Vorgehensweise muß das System vorhandene Linien mit neu hinzugekommenen Linien schneiden und die Schnitt­punkte als Verbindungen einfügen, damit aus dieser Datenbasis sowohl der Linienverlauf zu jedem gegebenen Zeitpunkt als auch die Veränderungen zwischen zwei Zeitpunkten ableitbar sind.

Grundsätzlich ergibt sich daraus die Notwendigkeit, dieses systembedingte Problem in einer speziellen Softwareschicht zu behandeln und potentielle Fehlerquellen so weit als möglich zu minimieren. In der Literatur findet sich kein Verfahren, das topologische Fehler als Folge diskreter Schnitte vollständig eleminiert (GÜTING/ RIDDER/ SCHNEIDER 1995, S. 219). Die Methode von GREEN/ YAO 1986 beschränkt zwar das Wandern von Liniensegmenten auf einen engen Bereich (Envelope) um die ursprüngliche Linie, innerhalb dieses Bereich können aber immer noch Fehler auftreten. Darüberhinaus ist der damit erzielbare Erfolg gemessen am Rechen- und Speicheraufwand zu gering als daß ein praxisgerechter Einsatz gerechtfertigt scheint. Deshalb soll in Kapitel 7.2 ein ver­einfachtes Verfahren vorgestellt werden, das bei relativ geringen algorithmischen Kosten ebenfalls eine näherungsweise konsistente Basis für geometrische Operationen bietet.

6.1.3 Beschreibung über Metadaten

Metadaten sind Daten über Daten und dienen der Identifizierung und Nutzbarmachung von Informationen in umfangreichen Datenbeständen. Dezidierte Metainformations­systeme sollen wie Kataloge in Archiven und Bibliotheken einen nutzerorientierten Zu­gang zu komplexen Datenbanken ermöglichen (GREVE 1995, S. 207). Nach STROBL lassen sich vier inhaltliche Kategorien unterscheiden (STROBL 1995, S. 277):

• semantische Metainformationen: die inhaltlichen Beschreibungen.

• syntaktische Metainformationen: wie kann auf die Daten zugegriffen werden, auf welchen Datenträgern sind sie gespeichert.

• strukturelle Metainformationen: in welcher Form liegen die Daten vor (Objekt­strukturierung, Hierarchien, Topologien).

• Navigatorische Metainformationen: wie hängen die Daten mit anderen Daten zu­sammen.

In einem objektorientierten System können diese Metainformation unmittelbar den Klas­sendefinitionen entnommen werden, da hier sowohl die zur Verfügung stehenden Daten­felder als auch die Verknüpfungen zu anderen Dateneinheiten, die hier in Form von Objekten vorliegen, angelegt sind. Zudem ist durch die Zuordnung eines Objekts zu einer Klasse eine wichtige Metainformation, nämlich die Klassifizierung als Bestandteil der semantischen Ebene, bereits vorhanden (STROBL 1995, S. 281f.; LEYKAUF/ ALBRECHT 1993, S. 51).

Es existieren eine Vielzahl von Fallstudien zur Standardisierung von Metadaten, wie der Content Standards for Digital Geospatial Metadata des U.S. Federal Geographic Data Committee (FGDC) oder den Catalogue of Data Sources (CDS) der European Environmental Agency, die verschiedenste Aspekte sowohl der räumlichen als auch der thematischen Daten abdecken (STROBL 1995, S. 281f.). Aus Vereinfachungsgründen soll hier angenommen werden, daß sich die Metainformationen auf die Geometrie-Daten be­schränken.

6.1.4 Koordinatensysteme

Um die gespeicherten Koordinatenwerte in Bezug zu einer Position auf der Erdoberfläche zu setzen, müssen entsprechende Koordinatensysteme zur Verfügung stehen. Erst die Kombination eines numerischen Wertes mit den zugehörigen Interpretationsregeln er­geben die Information über Form und Position eines Objektes im Raum. Im GIS-Bereich ist die Beschreibung von Bezugssystemen insbesondere bei der Verwendung unterschied­licher Datenquellen von Bedeutung. In Navigationssystemen sind die Grundkarten häufig in Form von projezierten Koordinaten angegeben, während Positionsdaten über GPS in der Regel in geographischen Koordinaten (World Geodetic System 84) in das System ge­langen. Das GIS dient in diesem Fall als eine Integrationsschicht für heterogene Daten­quellen und deren Koordinatensysteme (BILL 1996, S. 204). In Kapitel 7.2.4 wird dazu ein Klassenmodell vorgestellt, das die für die Konvertierung notwendigen Parameter be­reitstellen kann.

6.2 Repräsentation von Geo-Objekten

6.2.1 Grundsätzliche Struktur

Auf der Ebene der Geometrie-Datenverwaltung kann eine Beschränkung auf Punkte und Linien erfolgen, aber um Geo-Objekte adäquat abzubilden, müssen hier Flächen einge­führt werden. Zusätzlich erscheint aus praktischen Erwägungen eine Trennung in Spaghetti-Daten und topologisch strukturierte Geo-Objekte sinnvoll. Obwohl Vektordaten mit expliziten Verweisen auf benachbarte Geo-Objekte räumliche Strukturen präziser ab­bilden, ist der Aufbau solcher Daten sowie deren Verwaltung mit einem Aufwand ver­bunden, der nicht für jeden Anwendungszweck gerechtfertigt ist. Deshalb wird hier eine Möglichkeit angeboten, für jedes Objekt unabhängig von seinen Nachbarschaftsgeo­metrien die vollständige geometrische Beschreibung aufzunehmen.

Da sich die Betrachtung in dieser Arbeit auf die Ebene beschränkt, können drei Gruppen an Geo-Objekten definiert werden:

• 0-dimensionale Punkte

• 1-dimensionale Linien

• 2-dimensionale Flächen

6.2.2 Unstrukturierte Geo-Objekte der Spaghetti-Ebene

Für einfache Anwendungszwecke können Objekte verwendet werden, die die voll­ständigen Geometrien besitzen. Für Linien werden keine Schnittbedingungen überprüft und Flächen können sich überlappen. Darüberhinaus können Flächen Löcher enthalten, die semantisch beispielsweise Inseln oder Enklaven andeuten. Für die Darstellung von be­nachbarten Flächen ergibt sich hier der Nachteil, daß jedes Geo-Objekt für die Randdar­stellung eine vollständige Liste der Stützpunkte enthält, wobei die gemeinsame Be­grenzung damit doppelt erfaßt ist. Diese Redundanz vereinfacht zwar die Datenhaltung, vergrößert aber das Datenvolumen.

6.2.3 Topologisch-strukturierte Geo-Objekte

Die topologisch strukturierten Geo-Objekte bilden Inzidenz und Adjazenz explizit ab. Ein Knoten ist durch seine Koordinaten positioniert und wird durch die mit ihm inzidenten Kanten charakterisiert. Eine Kante ist durch ihre beiden Endknoten sowie ihren geo­metrischen Verlauf festgelegt. Eine Facette besteht aus einer äußeren Umrandung, die aus einer oder mehreren Kanten besteht, sowie 0 oder mehreren Löchern, die durch andere Facetten gebildet werden. Da Flächen hier ausschließlich über Kanten gebildet werden, kann man die Betrachtung auf einen zusammenhängenden Graphen reduzieren. Hierzu wird auf eine Methode von DAVID/ RAYNAL/ SCHORTER 1993 zurückgegriffen, um sie in einem weiteren Schritt um den zeitlichen Bezug zu erweitern. Dort sind für Kanten drei Permutationen definiert (S. 271ff.; vgl. Abbildung 29):

1. Die  - Permutation führt zu der gegenüberliegenden Kante, die die beiden Knoten in entgegengesetzter Richtung verbindet.

2. Über die  - Permutation erhält man für jede Kante dasjenige “Gegenstück”, das den­selben Endknoten teilt. Besitzt ein Knoten mehr als zwei eingehende Kanten, so liefert die  - Permutation die nächste Kante gegen den Uhrzeigersinn. Ein vollständiger  - Kreis beschreibt alle in einen Knoten einmündenden Kanten und damit den Knoten selbst.

3. Die  - Permutation entspricht der Kombination von  und . Damit wird die unmit­telbar nachfolgende Kante bezeichnet, die den Endknoten gegen den Uhrzeigersinn als erste verläßt. Folgt man dieser Reihe bis zur Ausgangskante, erhält man die Um­randung einer Fläche.

Abbildung 29: Topologische Karte



Quelle: Nach DAVID/ RAYNAL/ SCHORTER 1993, S. 271, verändert

Diese Erweiterung der Graphen-Theorie bietet sich für die vorliegende Arbeit an, da die -Permutation Flächen bzw. Facetten definiert und zum anderen die Permutationen in einem objektorientierten System relativ einfach über Objektreferenzen realisierbar sind. Im Unterschied zu der Arbeit von DAVID/ RAYNAL/ SCHORTER 1993 werden hier aber nicht alle Verknüpfungen über die Kanten gebildet, sondern teilweise sind die Knoten die Träger der entsprechenden Information. Diese Veränderung wird durch die später auf­zuzeigende Integration zeitlicher Verläufe notwendig.

6.3 Beziehungen zwischen räumlichen Objekten

6.3.1 Besonderheiten räumlicher Beziehungen

Die Definition von räumlichen Beziehungen zwischen Objekten in einem GIS weisen einige Besonderheiten auf, die diese Systeme deutlich von anderen Informationssystemen unterscheiden. Einfache numerische Prädikate und Operatoren sind eindeutig definiert und bedürfen keiner weiteren Erläuterung (EGENHOFER/ SHARMA 1993, S. 316).
Beispielsweise ist die Datenbankabfrage „Zeige alle Angestellten mit einem Jahresgehalt > 80.000 DM“ ausreichend präzise formuliert, um sie ohne Widersprüchlichkeiten auszu­führen. Dahingegen kann das Prädikat „nördlich von Mannheim“ unterschiedlich interpretiert werden: alle Objekte auf einer nach Norden gerichteten Achse durch Mannheim, alle Objekte im 90° - Fächer nördlich von Mannheim oder alle Objekte in der 180° - Halbebene nördlich von Mannheim. Andere Operatoren sind zwar für Punkte ein­deutig definiert, aber nicht für Flächen und Linien. Die Entfernung zwischen Linien oder Flächen kann auf unterschiedliche Weise durch Reduzierung auf Punkte ermittelt werden (Mittelpunkte, Schwerpunkte usw.) (BÄHR/ SINGER/ KIESSLING 1994, S. 14). Diese Beispiele illustrieren die Probleme, die sich bei der Interpretation umgangssprachlich ge­bräuchlicher räumlicher Prädikate ergeben. Um diese Unschärfe zu bewältigen, werden in der Literatur formale Modelle eingeführt, die Begriffe wie „ist benachbart“, „schneidet“ oder „überlappt“ mengentheoretisch definieren (MARK 1999, S. 84ff.).

Im Folgenden werden ausschließlich topologische Beziehungen betrachtet. Vorschläge zur Abbildung metrischer Beziehungen wie Distanzen und Richtungsprädikate finden sich bei THEODORIDIS/ PAPDIAS 1995 und BREUNIG 1996.

6.3.2 Topologische Beziehungen

Die grundsätzliche Methodik geht von der sog Punktmengen-Topologie aus. In diesem Formalismus werden einfache geometrische Objekte in der Ebene (²) als Mengen be­trachtet, deren einzelnen Elemente Punkte sind. Die Notation P, L und A bezeichnet je­weils die Menge der Punkte, Linien und Flächen. Jedes Objekt stellt eine abgeschlossene Menge dar, d.h. es enthält alle Punkte, die dieses Objekt bilden, und Objekte können nicht aus anderen, unabhängigen Objekten zusammengesetzt sein. Desweiteren gelten folgende Bedingungen (FLORIANI/ MARZANO 1993, S. 116ff.; SCHNEIDER 1995, S.49ff.):

1. Flächenobjekte besitzen keine Löcher;

2. Linienobjekte dürfen sich nicht selbst schneiden und sind entweder geschlossene Kurven (d.h. der Endpunkt ist gleich dem Anfangspunkt) oder sie besitzen genau zwei Endpunkte;

3. Punktobjekte enthalten genau einen Punkt.

Es ist eine Funktion „dim(x)“ definiert, die die Dimension eines Arguments ermittelt. Ein Punkt besitzt die Dimension 0, eine Linie die Dimension 1 und eine Fläche die Dimension 2. Für jedes Objekt  aus P, L oder A ist die Begrenzung (boundary ) folgendermaßen definiert:

1. P : die Begrenzung eines Punktes ist immer die leere Menge;

2. L: die Begrenzung einer geschlossenen Linie (Anfangspunkt = Endpunkt) ist die leere Menge, während in den sonstigen Fällen die beiden Endpunkte die Begrenzung darstellen;

3. A: die Begrenzung einer Fläche ist die sie umschließende Linie.

Das Innere (interior) eines Objektes (⁰) ergibt sich aus

⁰ =  -  .

Daraus folgt, das der Kern eines Punktes und einer geschlossenen Linie die Objekte selbst sind.(CLEMENTINI/ FELICE/ OOSTEROM 1993, S. 279f.)

Tabelle 4: Schnittmengen zur Bestimmung topologischer Beziehungen

Quelle: Nach CLEMENTINI/ FELICE/ OOSTEROM 1993, S. 280

Die Klassifizierung binärer topologischer Beziehungen basiert auf dem Schnitt von Be­grenzung und Innerem geometrischer Primitive, welche durch vier Mengen repräsentiert wird (CLEMENTINI/ FELICE/ OOSTEROM 1993, S. 280; vgl. Tabelle 4) .Jede dieser Mengen kann entweder leer () oder nicht-leer () sein. Die Kombination aller Möglichkeiten ergibt 2⁴ = 16 Fälle. Beschränkt man sich zunächst auf die Betrach­tung von Flächen, sind 8 Fälle nicht möglich und 2 Fallpaare beschreiben dieselbe topologische Beziehung, wobei sie sich lediglich in der Operandenfolge unterscheiden (vgl. Tabelle 5).

Tabelle 5: Mögliche Schnittergebnisse bei Flächen

Quelle: Nach CLEMENTINI/ FELICE/ OOSTEROM 1993, S. 281, verändert

Die ursprüngliche Methode unterscheidet nur, ob das Ergebnis die leere oder die nicht-leere Menge ist. So wird nicht unterschieden, ob die Berührung zwischen zwei Flächen in einem Berührungspunkt oder in einer Linie resultiert. Wird nun auch die Dimension des Schnittergebnisses ausgewertet, erhält man für die Ebene 4⁴ = 256 mögliche Schnitt­kombinationen. Verwirft man die nicht möglichen Kombinationen für die Beziehungen Fläche - Fläche, Linie – Fläche, Punkt – Fläche, Linie – Linie, Punkt – Linie und Punkt – Punkt, so reduziert sich die Anzahl auf 52 mögliche Fälle (CLEMENTINI/ FELICE/ OOSTEROM 1993, S.280ff; VOIGTMANN 1997, S. 64ff).

Eine handhabbare Methode liefern CLEMENTINI/ FELICE/ OOSTEROM 1993, die die Operandentypen auf Flächen ohne Löcher, Linien und Punkte erweitern. In der Ziel­setzung wird aber neben der Formalisierung toplologischer Beziehungen auch deren An­wendung betont. Im Vordergund steht demnach eine Beschränkung auf einige wenige Beziehungen, die von einem Benutzer auch in sinnvoller Weise angewendet werden kön­nen. Gerade diese Anwendbarkeit ist bei einer Fülle von 52 möglichen Beziehungen sehr in Zweifel zu ziehen.

Dazu sind die fünf topologischen Beziehungen „berührt“, „ist innerhalb“, „kreuzt“, „überlappt“ und ist „disjunkt“ definiert (CLEMENTINI/ FELICE/ OOSTEROM 1993, S. 285):

• „berührt“ (touch): betrifft Fläche/ Fläche, Linie/ Linie, Linie/ Fläche, Punkt/ Fläche, Punkt/ Linie Situationen. Da Punkte per Definition keine Begrenzung besitzen sind Punkt/ Punkt Situationen hier nicht möglich. Die formale Definition ist gegeben durch

d.h. ₁ berührt ₂ genau dann, wenn sich ₁ und ₂ ausschließlich in ihrer Begrenzung schneiden.

• „ist innerhalb“ (in): dieser Fall ist in allen Situationen möglich und ist definiert durch

d.h. ₁ ist innerhalb von ₂ genau dann, wenn ₁ vollständig in ₂ liegt und ₁ darüber­hinaus nicht ausschließlich Teil der Begrenzung von ₂ ist. Beispielsweise ist die erste Bedingung wahr, wenn eine Linie Teil der Begrenzung einer Fläche wäre, aber die zweite Bedingung ist in diesem Fall nicht erfüllt. Stattdessen liegt hier eine Berührung zwischen Linie und Fläche vor.

• „kreuzt“ (cross): die „kreuzt“-Beziehung gilt für Linie/Linie und Linie/Fläche:

d.h. ₁ kreuzt ₂ genau dann, wenn das Schnittergebniss der inneren Punktmengen der beiden Objekte von einer niedrigeren Dimension ist als die Dimension mindestens eines Operanden (der Schnitt Linie-Linie resultiert in einem Punkt und der Schnitt Linie – Fläche ergibt einen gemeinsame Linie) und darüberhinaus keine „ist innerhalb“ – Situation vorliegt.

• „überlappt“ (overlap): die „überlappt“-Beziehung unterscheidet sich von der „kreuzt“-Beziehung dadurch, daß sowohl die Operanden als auch das Schnittergebnis dieselbe Dimension besitzen müssen, und ist für Fläche/ Fläche - und Linie/ Linie - Situationen folgendermaßen festgelegt:

d.h. ₁ überlappt ₂ genau dann, wenn identische Dimensionen vorliegen und keine „ist innerhalb“ – Beziehung festgestellt ist. Daraus ergibt sich indirekt, daß sowohl die „kreuzt“ als auch die „überlappt“-Beziehung für einen Punkt-Operanden nicht zutref­fen kann, da das nichtleere Schnittergebnis in einem solchen Fall der Punkt selbst ist und somit eine „ist innerhalb“-Situation vorliegt.

• „disjunkt“ (disjoint): die „disjunkt“-Beziehung komplettiert die Beschreibungs­möglichkeiten des Modells und wird festgelegt durch:

d.h., ₁ und ₂ sind genau dann disjunkt, wenn sie keinerlei gemeinsamen Punkte be­sitzen.

Mit Ausnahme der „ist innerhalb“-Beziehung sind die Beziehungen symmetrisch, dh. es gilt:

Ausschließlich die „ist innerhalb“-Beziehung ist transitiv, d.h. es gilt:

Abbildung 30: Die fünf topologischen Beziehungen



Quelle: Nach VOIGTMANN 1997, S. 69, verändert

Nach der Definition der möglichen topologischen Beziehungen wird ein Entscheidungs­baum eingeführt, mit dessen Hilfe die Beziehung zwischen zwei Objekten bestimmt wer­den soll. An jedem Knoten des Baumes wird eine Schnittbedingung überprüft und dann entsprechend weiterverzweigt (vgl. Abbildung 31).

Abbildung 31: Der topologische Entscheidungsbaum



Quelle: VOIGTMANN 1997, S.72

Anhand dieses Entscheidungsbaumes kann man zeigen, daß sich zum einen die fünf definierten topologischen Beziehungen gegenseitig ausschließen und zum anderen kein Fall auftreten kann, in dem sich keine der definierten Beziehungen anwenden läßt. Der gegenseitige Ausschluß leitet sich daraus ab, daß an jedem inneren Knoten des Baumes ein Prädikat zu überprüfen ist und im „wahr“-Fall nach links und im „falsch“-Fall nach rechts verzweigt wird. Dieses Vorgehen wird solange wiederholt bis ein Blatt des Baumes erreicht wird, das für eine der fünf definierten Beziehungen steht.¹ Für jede Objektkom­bination kann nur ein Pfad durchlaufen werden, der immer in einem Blatt endet, so daß nie zwei oder mehrere Beziehungen gelten können. Da jeder innere Knoten zwei Äste besitzt, gibt es für jedes Ergebnis der Bedingungen einen Pfad und dieser Pfad endet immer in einem mit einem topologischen Prädikat bezeichneten Blatt. Damit ist gesichert, daß für jede Objektkombination eine Beziehung festgestellt wird und kein undefinierter Fall ein­treten kann (CLEMENTINI/ FELICE/ OOSTEROM 1993, S. 282ff; VOIGTMANN 1997, S. 67ff). Damit ist diese Methode in sich eindeutig und abgeschlossen.²

Für eine Verwendung dieser Definition in einem GIS sprechen folgende Punkte:

1. Die topologischen Beziehungen zwischen raumbezogene Objekten werden mit Hilfe von bekannten Begriffen beschrieben. Ein Benutzer hat schon im Vorfeld eine Vor­stellung, was die Beziehung ausdrückt und wie er sie für seine Problemstellung inter­pretieren und anwenden kann.

2. Die den Begriffen im sprachlichen Umgang anhaftende Unschärfe wird durch die prä­zise formale Definition beseitigt. Dabei hält sich der Abstraktionsgrad (Beschreibung geographischer Objekte als Punktmengen und der Schnitt zwischen diesen Mengen) noch in Grenzen und baut auf bekannten sowie nachvollziehbaren Abstraktionen auf.

3. Das Modell ist in sich konsistent und eindeutig. Jedes Objekt steht in genau einer Be­ziehung zu einem anderen Objekt. Mehrere gleichzeitig erfüllte Beziehungen sind nicht möglich.

4. Aus den gegebenen Prädikaten können durch Kombinationen neue Prädikate definiert werden. Beispielsweise könnte ein einfaches „schneiden“-Prädikat dadurch gebildet werden, daß man überprüft ob sich die betreffenden Objekte überlappen, kreuzen oder ein Objekt innerhalb des anderen Objekt liegt.

5. Wie bei VOIGTMANN 1997 (S. 72f.) gezeigt, kann das Modell auch auf den drei­dimensionalen Raum und auf Objekte mit Löchern erweitert werden, ohne daß Inkon­sistenten auftreten.

6.4 Darstellung der zeitlichen Variabilität

Zur Darstellung zeitlich variabler räumlicher Objekte verfolgt die vorliegenden Arbeit zwei unterschiedliche Ansätze, die aber nebeneinander bestehen können. Die Unter­scheidung ergibt sich aus daraus, daß bei der Verwendung der topologischen Struktur ein anderes Prinzip angewendet werden kann als bei der einfacheren Spaghetti-Ebene. Beiden Ansätzen gemeinsam ist, daß Zeit als eine zusätzliche Dimension orthogonal zu zwei räumlichen Achsen aufgefaßt wird. Die zeitbezogene Komponente wird in diskreten Schritten aufgezeichnet, d.h. jeder Objektzustand wird durch ein Ereignis, das eine Ver­änderung verursacht, in einen Folgezustand überführt, der bis zum Eintreten des nächsten Ereignisses gültig bleibt. Da die Zustände zeitlich unmittelbar benachbart sind und ledig­lich durch das auslösende Ereignis, welches durch einen Zeitpunkt gegeben ist, vonein­ander getrennt werden, entsteht ein Quasikontinuum, in dem für jeden Zeitpunkt und jedes Geo-Objekt ein Zustand definiert ist (vgl. Abbildung 32).

Abbildung 32: Abfolge unterschiedlicher Zustände



Quelle: Eigener Entwurf

Zur Erläuterung des Konzepts soll hier von folgendem Beispiel ausgegangen werden (vgl. Abbildung 33). Dabei ist die Betrachtung der Veränderungen im Zeitablauf bei Flächen von besonderem Interesse, da dieser Fall die größte Komplexität in sich birgt.

Abbildung 33: Veränderung



Quelle: Eigener Entwurf

Zu drei unterschiedlichen Zeitpunkten t₁, t₂ und t₃ ergibt sich die oben dargestellte Konstellation. Von den Änderungen sind nur die Flächen F1 und F2 betroffen, da sich ihre gemeinsame Grenzlinie verschiebt. Die grau dargestellten Flächen bleiben in allen Zeit­schnitten unverändert.

6.4.1 Lokaler Schappschuß

Sind die Flächen als Spaghetti-Daten abgelegt, so wird für jede veränderte Fläche eine neue Objektversion mit der neuen und vollständigen Umrandung angelegt (vgl. Abbildung 34). Ähnliche Versionierungsansätze finden sich im CAD-Bereich. Damit ergeben sich Parallelen zu dem oben angesprochenen Schnappschußmodell für ein konventionelles Layer-GIS, wobei hier aber nicht für alle Geo-Objekte einen neue Version angelegt wird, sondern nur für diejenigen, die tatsächlich von einer Änderung betroffen sind. Deshalb soll hierfür die Bezeichnung „lokaler Schnappschuß“ verwendet werden, wobei der Begriff „lokal“ unmittelbar auf ein einzelnes Geo-Objekt zu beziehen ist.

Abbildung 34: Lokaler Schnappschuß



Quelle: Eigener Entwurf

Dieses Vorgehen erweitert das unstrukturierte Spaghetti-Prinzip in die hinzugefügte orthogonale t-Achse. Datenbestände, die nach diesem Prinzip aufgebaut sind, können re­lativ einfach verwaltet werden. Abfragen, die den Zustand einer Objektmenge zu einem bestimmten Zeitpunkt betreffen, können ebenfalls mit geringem Aufwand ausgeführt wer­den. Dazu sucht das System die jeweils für diesen Zeitpunkt gültige Objektversion aus und fügt sie in die Ergebnismenge ein. Nachteilig wirkt sich die hohe Redundanz aus. Da­durch, daß nur die tatsächlich veränderten Objekte versioniert werden, ist der Speicherbe­darf gegenüber dem ursprünglichen Snapshotmodell zwar geringer, dennoch müssen viele Geometriedaten nach wie vor doppelt erfaßt werden.

6.4.2 Diskretes temporales Netzwerk

Für das topologisch-strukturierte Datenmodell wird eine andere Vorgehensweise vorge­schlagen, bei der prinzipiell ein Basiszustand festgehalten wird und nachfolgende Zeit­schnitte lediglich hinsichtlich der erfolgten Veränderung zu erfassen ist. Das Grundprinzip verwendet einen Zerlegungsprozeß in kleinste geometrische Einheiten und einer an­schließenden Rekombination zu komplexen Geo-Objekten. Damit bestehen Parallelen zu dem Space-Time Composit von LANGRAN 1992 bzw. den kleinsten gemeinsamen Geo­metrien von SWIACZNY/OTT 1999. Die vorliegenden Arbeit orientiert sich dabei an folgenden Prämissen:

1. Die kleinsten relevanten geometrischen Elemente sind einzelne Punkte sowie geord­nete Punktsequenzen, die einfache Linien und Umrandungen von Flächen darstellen. In der Geometrie-Schicht sind deshalb keine Polygone definiert.

2. Die geometrische Repräsentation einerseits und ihre Interpretation als Geo-Objekte andererseits ist in unterschiedliche Softwareschichten voneinander getrennt. Die Ver­waltung der Geometrien erfolgt zunächst ohne einen expliziten zeitlichen Bezug, der erst über die Verbindung zu Geo-Objekten hergestellt wird. Die redundanzfreie Be­schreibung zeitlich veränderlicher Geo-Objekte wird durch eine daraufhin ausge­richtete Verwaltug der Geometrien ermöglicht. Dazu werden auf der Geometrie-Ebene alle Linien in die kleinsten, schnittpunktfreien Linienstücke zerlegt, die dann zu neuen Verbindungslinien zu kombinieren sind.

3. Auf der Ebene der Geo-Objekte wird eine topologische Knoten-Kanten-Struktur auf­gebaut, mit deren Hilfe auch Flächen bzw. Facetten definiert werden können. Diese Struktur wird hier als diskretes temporales Netzwerk bezeichnet, da die Erfassung der zeitlichen Veränderungen in diskreten Schritten erfolgt und die Kanten ein drei­dimensionales Netzwerk bilden, wobei die Verbindung unterschiedlicher Zeitebenen über die Knoten hergestellt wird.

Da auf der Geometrie-Ebene die Linien an Schnittpunkten in einzelne Linienstücke auf­getrennt werden, ergibt sich für die Darstellung der Flächen F1 und F2 aus obigem Bei­spiel folgende Konstellation (vgl. Abbildung 35):

Abbildung 35: Geometrieschicht



Quelle: Eigener Entwurf

Durch eine Rekombination der Linienstücke kann die Flächenumrandung für jeden Zu­stand zusammengesetzt werden. Dies erfolgt redundanzfrei, da die jeweilige Be­grenzungslinie zwischen F1 und F2 nur einmal in der Geometrie-Ebene gespeichert wird und die Flächen lediglich Verweise darauf einrichten.

Die Zerlegung in die kleinsten, schnittfreien Linienstücke erleichtert auch das Nachvoll­ziehen der flächenmäßigen Veränderung eines Geo-Objektes zwischen zwei beliebigen Zeitpunkten. Dazu betrachtet man jede Fläche zum Zeitpunkt t als eine Menge, deren Elemente die kleinsten Abschnitte der Umrandung sind. Soll nun die Fläche ermittelt wer­den, um die ein flächiges Geo-Objekt gewachsen bzw. geschrumpft ist, bildet man die symmetrische Differenz der beiden Mengen über eine logische XOR – Verknüpfung (exklusives Oder), d.h. in die Ergebnismenge gelangen diejenigen Linienstücke, die ent­weder nur in der ersten Menge oder nur in der anderen enthalten sind (vgl. Abbildung 36).

Abbildung 36: Veränderung ermitteln



Quelle: Eigener Entwurf

Durch diese einfache Mengenoperation erhält man für zwei beliebige Zustände die flä­chenmäßige Veränderung in Form der kleinsten Linienstücke, die diese Fläche begrenzen. In Abbildung 36 ist diese Operation schematisch für die Fläche F1 dargestellt. Ausgehend von der Konfiguration, wie sie sich nach der Aufnahme aller Linien ergibt, kann die Fläche F1 für jeden der betrachteten Zeitpunkte als Menge definiert werden. Wie die Bei­spiele in der unteren Reihe zeigen, ist das Ergebnis der Mengenverknüpfung unabhängig davon, ob unmittelbar aufeinanderfolgende Zustände oder beliebige Situationen mit­einander verglichen werden . Auch der Vergleich zwischen t₁ und t₃ ist direkt möglich und liefert das korrekte Ergebnis. In dem logischen Objektmodell soll die Operation dahin­gehend ergänzt werden, daß für das Ergebnis nachvollziehbar ist, ob es sich um einen Zu­wachs oder einen Verlust handelt.

Auf dieser zunächst rein geometrischen Grundlage soll nun die Erweiterung um topo­logische Strukturen und den expliziten zeitlichen Bezug erfolgen. Ziel dieser Betrachtung ist die Darstellung der räumlichen Daten in Form eines dreidimensionalen Netzwerks, das auf der gegebenen geometrischen Basis aufbaut. Das Beispiel in Abbildung 36 zeigt, daß man hierbei drei Punktarten unterscheiden kann:

1. Stützpunkte liegen innerhalb einer Punktsequenz und besitzen hinsichtlich der Geo-Objekte keine topologische Bedeutung.

2. Geometrische Schnittpunkte entstehen, wenn Linien aus verschiedenen Zeitschnitten in der Geometrie-Schicht abgelegt und in kleinste Linienstücke unterteilt werden.

3. Topologische Knoten können nur auf der Ebene der Geo-Objekte gebildet werden, da nur hier die Informationen zur Verfügung stehen, welche Linienstücke zu einer Kante zusammenzufassen sind. Im Unterschied zu reinen Schnittpunkten, die aus der Inte­gration von Linien aus unterschiedlichen zeitlichen Ebenen resultieren und der Re­kombination der kleinsten Linienstücke zu neuen Verbindungslinien dienen, sind Knoten dadurch gekennzeichnet, daß sich hier Linien aus identischen Zeitschichten schneiden.

Das Netzwerk besteht aus Knoten und Kanten³. Im obigen Beispiel bildet die sich ver­ändernde Begrenzung zwischen F1 und F2 einen topologische Kante, die die beiden Knoten D und C miteinander verbindet. Der geometrische Verlauf dieser Kante variiert und ändert damit auch die Eigenschaften der Flächen F1 und F2. Diesen zeitlichen Verlauf kann man sich anschaulich so vorstellen, daß eine dreidimensionale Struktur auf der drit­ten Achse angibt, welche Verbindung zwischen zwei Knoten zu einem gegebenen Zeit­punkt gültig ist . Die Konfiguration des Netzwerks zu einem bestimmten Zeitpunkt läßt sich in einem Gedankenmodell derart ermitteln, daß man eine Halbebene durch die drei­dimensionale Darstellung zieht. Die resultierenden Schnittlinien zeigen alle gültigen Kan­ten zu diesem Zeitpunkt (vgl. Abbildung 37).

Abbildung 37: Diskretes temporales Netzwerk

Quelle: Eigener Entwurf

Für diese Art der Datenorganisation kommt den Knoten eine zentrale Bedeutung zu. Während eine Kante nur für einen zusammenhängenden Zeitabschnitt gültig ist und dann durche eine andere Repräsentation ersetzt wird, verknüpft ein Knoten mehrere Kanten aus unterschiedlichen Zeitebenen miteinander. Dadurch eignen sich die Knoten zur Navigation durch das Netzwerk, in dem Kanten aus sich überlappenden Zeitabschnitten präsent sind. Beispielsweise sind die in Abbildung 38 grau dargestellten Kanten für den gesamten be­trachteten Zeitraum gültig, während die farbig dargestellten Kanten lediglich Unterab­schnitte markieren.

Abbildung 38: Temporaler Knoten



Quelle: Eigener Entwurf

6.4.3 Temporale Beziehungen

Um die Relation zwischen zwei Zeitintervallen zu bestimmen, müssen entsprechende Prä­dikate gegeben sein. Die in Abbildung 18 gezeigte Möglichkeit besitzt den Nachteil, daß die Anzahl der Prädikate unnötig groß ist, da auch Fälle aufgenommen sind, die lediglich die Umkehrung eines bereits definierten Prädikats darstellen. Beispielsweise läßt sich aus „U overlaps T“ durch einen einfachen Operandentausch das Prädikat „T overlapped-by U“ herleiten. Hier soll auf einen Vorschlag von VOIGTMANN 1997 zurückgegriffen werden, da die dort definierten Prädikate sowohl von der Anzahl her praktikabel als auch in ihrer Ausdrucksfähigkeit ausreichend sind.

Gegeben sind zwei Zeitintervalle X = [a,b] und Y = [c,d], wobei a,b,c und d die Anfangs- und Endzeitpunkte repräsentieren. Nach VOIGTMANN lassen sich hier vier Prädikate formulieren (S. 101; vgl. Tabelle 6).

Tabelle 6: Definition temporaler Beziehungen

Quelle: Nach VOIGTMANN 1997, S. 101, verändert

Diese Prädikate können auch für den Vergleich von Zeitpunkten verwendet werden, indem man diese als Intervalle mit identischem Anfangs- und Endzeitpunkt interpretiert.

Abbildung 39: Beispiele für temporale Beziehungen

Quelle: Nach VOIGTMANN 1997, S. 102, verändert

6.5 Indizierung der Geo-Objekte

Neben der Selektion anhand der thematischen Attribute muß es möglich sein, die räum­lichen Eigenschaften als Selektionskriterium zu spezifizieren. Ein typisches Beispiel ist eine Bereichsabfrage in der Form ”Finde alle Objekte, die durch das Rechteck R überdeckt werden.”. Ab einer gewissen Datenbankgröße ist es nicht mehr effizient möglich, alle ge­speicherten Geo-Objekte zu durchlaufen und für jedes den erforderlichen geometrischen Test auszuführen (OOSTEROM 1999, S. 385).

Indizes sollen die zielgerichtete Suche in großen Datenbeständen beschleunigen, indem sie die Datensätze anhand eines Attributes vorsortieren. Durch diese Vorsortierung kann das Datenbanksystem schnell mittels entsprechender Suchalgorithmen auf die relevanten Daten­sätze zugreifen. Konventionelle DBMS verwenden hierzu in der Regel einfache Strukturen wie Binärbäume, die die Daten in einer Dimension sortieren können. Räum­liche Daten benötigen aber eine Indizierung in mindestens zwei Dimensionen bzw. bei dreidimensionalen Daten und zeitvariablen räumlichem Bezug in drei bzw. vier Dimen­sionen. (WORBOYS 1995, S. 64; OOI 1990, S. 4f.)

Angenommen, in einem kommunalen GIS soll ermittelt werden, durch welche Grund­stücke die Versorgungsleitung 4711 läuft. Die Abfrage würde vom Anwender –unabhängig von der darunterliegenden Datenstruktur- in einer SQL-ähnlichen Syntax folgender­maßen aussehen:

”SELECT X FROM Grundstück WHERE Cross(Grundstück X, 4711) = TRUE ”

Entsprechend der Organisation der Daten stehen zwei Strategien zur Verfügung :

1. Sequentielle Suche: Jedes Grundstück in der Datenbank wird daraufhin überprüft, ob das Prädikat ”Cross(X, ”4711”) zutrifft. Diese Strategie wäre höchst ineffizient und der Zeitbedarf für die Ausführung wächst linear mit der Anzahl der gespeicherten Grundstücke. Jedes Grundstück muß aus der Datenbank ausgelesen werden, und für jede Seite und jeder Eckpunkt ist ein Schnittest mit der Linie von ”4711” auszuführen.

2. Indexgestützte Suche: Die Suche kann dann auf eine Teilmenge aller Grundstücke eingeschränkt werden, wenn im System einen Struktur existiert, die zumindest näherungsweise die relative Lage der Geo-Objekte zueinander abbildet. Solche räum­lichen Indizes ermöglichen eine zweistufige Suche: über den Index als Grobfilter kön­nen ohne den aufwendigen geometrischen Schnitt diejenigen Kandidaten ermittelt werden, die aufgrund ihrer relativen Lage überhaupt in Frage kommen können. Diese Auswahl ist deshalb grob, weil die Objekte anhand einer Approximation wie z.B. dem kleinsten umgebenden Rechteck erfaßt werden. Grundstücke, deren Approximation disjunkt zu ”4711” sind, können von vorneherein ausgeschlossen werden. Die vor­selektierten Kandidaten werden dann im zweiten Schritt dem genauen Test für alle Seiten und Eckpunkte unterzogen und nur die tatsächlich betroffenen Grundstücke in die Ergebnismenge aufgenommen.

Beide Verfahren führen zwar zum gleichen Ergebnis, weisen aber in der Ausführungsge­schwindigkeit signifikante Unterschiede auf. Es ist offensichtlich, daß die Performanz der Abfrageausführung wesentlich davon beeinflußt wird, wie groß die zu überprüfende Kan­didatenmenge für den aufwendigen Feintest ist.

In der Literatur wird dazu eine Vielzahl spezieller Datenstrukturen angebotenen. Jede Methode weist für unterschiedliche Situationen spezifische Vor- und Nachteile auf, wobei sich Baumstrukturen in einem objektorientierten Umfeld anbieten, da sich die Knoten, Verzweigungen und Blätter eines Baumes direkt in Form von Objekten und entsprechen­den Pointern implementieren lassen. Ein bekannter Vertreter dieser Art im GIS-Bereich ist der Quadttree, der auch zur komprimierten Speicherung von Rasterdaten Verwendung findet.(SAMET 1995a, S. 2f.)

Abbildung 40: Der Point-Quadtree

Quelle: SAMET 1995b, S. 11.

Die Grundidee bei der Verwendung einer Baumstruktur wie dem Quadtree besteht in der rekursiven Zerlegung des Raumes. Auf jeder Stufe wird ein Raumausschnitt in vier Quadranten unterteilt. Die Unterteilung wird dadurch ausgelöst, daß nacheinander Geo-Objekte entsprechend ihrer Lage in den Baum eingefügt werden, bis ein zuvor festgelegter Schwellenwert überschritten wird. Die Objekte des ursprünglichen Blattes werden auf die einzelnen Folgeblätter aufgeteilt. Dieses Verfahren gewährleistet ein dynamisches Wachsen des Baumes mit unterschiedlich tiefen Ästen, so daß kein regelmäßiges Gitter entsteht, sondern ein an die räumliche Verteilung der erfaßten Geo-Objekte angepaßtes Suchmuster (BARTELME 1995, S. 220ff.). Abbildung 40 zeigt diese Zerlegung für punktförmige Objekte.

Problematischer ist die Indizierung ausgedehnter Objekte wie Linien und Polygone. Hier werden in der Literatur drei Strategien vorgeschlagen (GÜNTHER 1992, S. 18f.):

1. Clipping: die Blätter des Baumes teilen den Raum in disjunkte Teilräume und die ausgedehnten Geo-Objekte werden entlang der Partitionslinien unterteilt (”geclippt”). Dadurch kann ein Polygon mehrfach indiziert werden.

2. Überlappende Partitionen: die durch die Blätter abgebildeten Partitionen müssen nicht disjunkt sein, sondern können sich gegenseitig überlappen. Jedes Objekt ist aber nur genau einer Partition zugewiesen.

3. Transformationsansatz: ausgedehnte räumliche Objekte werden funktional auf höher­dimensionale Punkte abgebildet und diese Punkte werden indiziert. Ein um­schließendes Rechteck in der Ebene wird durch die Abbildung zu einem vierdimen­sionalen Punkt.

Hier soll aber eine andere Methode verwendet werden, die die Verwaltung der Elemente im Baum erleichtert. Um die Ergebnismenge einer räumlichen Abfrage zu bilden, ist es günstig, wenn jedes Geo-Objekt nur einmal im Baum enthalten ist. Entspricht das Objekt dem Abfrageprädikat, müßte das System andernfalls noch überprüfen, ob das Element nicht bereits in der Ergebnismenge enthalten ist. Ähnlich ist die Situation beim Löschen eines Objektes, da zunächst alle Blätter gesucht werden müssen, die dieses Objekt referen­zieren. Überlappende Partitionen sind insofern ungünstig, als auch hier eine Mehrfach­indizierung auftreten kann. Der Transformationsansatz scheidet aus, da die relativen Be­ziehungen zwischen den Geo-Objekten zum Teil verloren gehen.

Günstiger scheint hier eine Erweiterung der Datenstruktur zu sein, indem Geo-Objekte nicht nur von Blättern, sondern auch von inneren Knoten referenziert werden können. Kann bei einer Überlaufsituation ein Objekt nicht an einen der Nachfolgerknoten weiter­gegeben werden, da es nicht vollständig innerhalb der durch den Nachfolger abzudecken­den Raumeinheit enthalten ist, so verbleibt es im Knoten. Dazu muß man lediglich deb Suchalgorithmus erweitern, so daß auch die inneren Knoten nach Ergebniselementen durchsucht werden.

In der vorliegenden Arbeit ist eine Indizierung der Geo-Objekte in drei Dimensionen not­wendig. Dazu bietet sich die dreidimensionale Erweiterung des Quadtrees, der Octtree, an (SAMET 1995a, S. 4ff.). Jeder Knoten erfaßt alle Geo-Objekte, die innerhalb eines be­stimmten Tetraeders liegen. Kommt es zu einem Überlauf, teilt sich das Blatt in acht Nachfolger und überträgt die von ihm referenzierten Geo-Objekte.

Abbildung 41: Raumaufteilung durch einen Octtree



Quelle: Eigener Entwurf

Der Octtree paßt sich ebenfalls dynamisch an die Verteilung der Daten an und unterteilt sich nur dort, wo einen vorbestimmte Anzahl an Elementen überschritten wird. Damit ist eine effiziente Datenstruktur gegeben, die die räumliche Suche für zweidimensionale Daten mit einer dritten temporalen Achse unterstützt.

© 2014 Zeit in Geografischen Informationssystemen (GIS), Frank Hellwich