Einleitung

 

Im Rahmen des an der Universität Bonn angesiedelten Sonderforschungsbereichs 350 wird vom Institut für Informatik III in Zusammenarbeit mit dem Geologischen Institut die Entwicklung eines objektorientierten 3D/4D-Geoinformationssystems (GIS) betrieben. Der erste Prototyp GEOSTORE ([BBC94]) wird momentan schon rege von den Geowissenschaftlern der Universität Bonn genutzt und dient der Datenhaltung für die rechnergestützte Rekonstruktion und Bilanzierung der Entwicklung der Niederrheinischen Bucht (vgl. [Sie93]).

Die im Untersuchungsgebiet vorliegende Datenlage ist aufgrund vieler Bohrungen und der Tagebaue sehr gut. GEOSTORE verwaltet sowohl räumliche und zeitliche, als auch die damit verbundenen thematischen Informationen und gibt dem Geologen die Möglichkeit, diese Daten zu visualisieren, interaktiv zu bearbeiten, oder effiziente Analysen vorzunehmen. Bislang fehlt dem System allerdings die Möglichkeit, Schlußfolgerungen topologischer Natur zu ziehen. Die Bestimmung von topologischen Beziehungen ist aber für den geowissenschaftlichen Benutzer von großer Bedeutung. Von Interesse sind die räumlich ausgedehnten Objekte Fläche und Volumen, auf denen die topologischen 3D-Beziehungen Anwendung finden sollen.

Vorraussetzung hierfür ist jedoch die Festlegung eines geeigneten Repräsentationsmodells topologischer Beziehungen, um dieses inhärent qualitative Konzept auf eine formale Basis stellen zu können. Die Beachtung des zugrundeliegenden 3-dimensionalen Raumes ist dabei ebenso erforderlich, wie eine spezielle Ausrichtung des Modelles auf die geowissenschaftliche Benutzergruppe. Im Zuge der Klassifikation von topologischen 3D-Beziehungen wird in der Arbeit ein Ansatz verfolgt, die interne Modellierung der zu betrachtenden Flächen und Volumina mittels unregelmäßiger Vermaschungen auszunutzen und die topologische Beziehung von zwei komplexen Objekten auf die topologischen Lagen ihrer Bestandteile zurückzuführen. Diese sollen dann geeignet zu einem Endresultat kombiniert werden.

Den Rahmen für die Konzepte dieser Diplomarbeit bildet der GIS-Baukasten GEOTOOLKIT. Dieser GIS-Kern stellt den zweiten Schritt ([BBC97]) in der Entwicklung eines ``objektorientierten 3D/4D-Geoinformationssystems`` dar, wie es das Ziel des Teilprojektes D4 im SFB 350 ist. Zunächst wurde jedoch mit GEOSTORE ein GIS-Prototyp fertiggestellt, welcher auf der Programmiersprache C und einem relationalen Datenbankmanagementsystem (DBMS) beruhte. Aufgrund des hohen Stellenwertes der Objektcharakteristik ging man jedoch schnell dazu über, eine komplette Reimplementierung von GEOSTORE vorzunehmen und sich dabei auf einen objektorientierten Entwurf zu stützen. Die Realisierung dieser neuen Version erfolgte mittels C2.3pt++ und setzt nunmehr auf dem objektorientierten DBMS OBJECTSTORE auf.

Die erste Zielgruppe von GEOSTORE lag innerhalb der Geologie. Aus dem Kreis der anderen Geowissenschaften kamen allerdings mit der Zeit immer mehr Anfragen nach GEOSTORE-ähnlichen Informationssystemen auf, da verschieden ausgerichtete Forscher auch unterschiedlich spezialisierte GIS favorisierten. Auf diese große Nachfrage wurde mit der Entwicklung eines GEOTOOLKIT reagiert, welches sich für die Entwicklung zukünftiger Geoinformationssysteme als Geo-Datenbankkern versteht, auf dem verschiedene Geo-Applikationen aufsetzen können. Das GEOTOOLKIT ist eine C2.3pt++ Klassenbibliothek zur Verwaltung von persistenten Objekten - diese Datenhaltung erfolgt ebenfalls über OBJECTSTORE. Eine anschließende Integration in das GEOSTORE-System war so die konsequente Weiterführung des objektorientierten Redesigns. Das GEOTOOLKIT fungiert demnach konzeptionell als Ebene zwischen GEOSTORE und OBJECTSTORE. Es stellt die grundlegenden räumlichen Datentypen incl. Operationen zur Verfügung und ermöglicht einen effizienten Zugriff darauf. Die für diese Arbeit wichtigsten Datentypen sind die der Fläche und des Volumens. Hierfür werden Funktionen zur Verschneidung oder Abstandsberechnung bereitgestellt. Außerdem ist es möglich, Teile der Objekte durch andere zu ersetzen oder das jeweilige 3D-Objekt im entsprechenden Format eines Visualisierungstools auszugeben.

Zur Zeit können jedoch topologische Fragestellungen der Art ``Berühren sich zwei Flächen in einem Punkt¿` oder ``Liegt ein Volumen vollständig in einem anderen¿` noch nicht direkt beantwortet werden, da sich die Funktionalität des GEOTOOLKIT größtenteils auf geometrische Funktionen erstreckt und jenseits quantitativer Aspekte auf nur ein topologisches Prädikat (intersects) beschränkt ist. Es fehlt also die Möglichkeit, über einen Schnittest hinausgehende qualitative Aussagen über die relative Lage zweier 3D-Objekte zueinander ableiten zu können. Dabei sind diese Punkte doch gerade für Geologen von großem Interesse. In ihrem Kontext stellen Volumina meist geologische Erdschichten und Flächen in der Regel deren Begrenzungen oder sogenannte Störungen dar. Die Beziehungen zwischen diesen geologischen Objekten spielen in der Analyse von zeitgeschichtlichen Entwicklungsvorgängen - bei denen schon kleine Veränderungen eine topologisch signifikante Auswirkung haben können - eine große Rolle und sind für eine exakte Beurteilung von geologischen Momentaufnahmen von Bedeutung. Außerdem basieren Integritätstests auf topologischen Invarianten, und würden daher Nutzen aus einer topologischen Komponente des GEOTOOLKIT ziehen. Die geologischen Daten des Untersuchungsgebietes der Niederrheinischen Bucht werden durch verschiedene Vorgänge gewonnen: Bohrproben, Digitalisierungsschritte und Interpolationen. Damit Inkonsistenzen in den Modelldatensätzen erkannt und beseitigt werden können, sind bislang feste Integritätstests in Verwendung (vgl. [Hil98]), die zum Teil auf einfachen topologischen Konzepten beruhen. Eine allgemeine Verfügbarkeit topologischer 3D-Beziehungen im GEOTOOLKIT würde dieses Arbeitsgebiet vereinfachen.

Konkret läßt sich also die Aufgabenstellung dieser Diplomarbeit folgendermaßen formulieren: Vor dem Hintergrund geowissenschaftlicher Anwendungen ist ein adäquates Repräsentationsmodell topologischer 3D-Beziehungen zu entwickeln, welches einerseits umfangreich genug ist, alle topologisch unterscheidbaren Fälle zu trennen, andererseits aber keine unnötigen Redundanzen enthält. Im praktischen Teil dieser Arbeit soll dann der GIS-Baukasten GEOTOOLKIT auf dieser Grundlage um eine topologische 3D-Komponente erweitert werden, wobei das Hauptaugenmerk auf den Entwurf der Funktionalität zur Bestimmung von topologischen Beziehungen zwischen Flächen und Volumina zu legen ist.

Zur genaueren Untersuchung topologischer Beziehungen erfolgt innerhalb dieser Diplomarbeit zunächst ein Vergleich der in der Literatur zu findenden Repräsentationsmodelle. Da Topologie ein rein qualitatives Konzept und frei jeglichen Maßes ist, war es anfangs schwer, ein geeignetes formales Datenmodell für topologische Beziehungen zu finden. Pionierarbeit hierzu lieferte EGENHOFER 1989 mit seiner 4-intersection-Methode ([Ege89]), welche die topologische Beziehung zwischen zwei Objekten auf die vier Durchschnittspaare von Rand und Innerem zurückführte. Dieser Ansatz wurde später von ihm selber noch erweitert (vgl. [Ege91]), um auch die relative Lage von Objekten in höherdimensionalen Räumen völlig charakterisieren zu können. Eine andere Erweiterung (dimension extended method: [CFvO93], [CF95]) bezieht noch die Dimensionen der Schnittmengen mit ein, wodurch ein weitaus höherer Grad der Unterscheidungsmöglichkeit topologischer Beziehungen gewährleistet werden kann. Ein komplementärer Ansatz wurde schließlich von CLEMENTINI/DI FELICE mit der calculus based method (vgl. [CF95] und [CFvO93]) angegeben, um von einer großen Fülle topologischer Beziehungen herunter zu einer überschaubaren Menge zu gelangen, ohne dabei Berechnungskraft zu verlieren. Sie geben speziell fünf topologische Beziehungen an und zeigen von diesen, daß alle anderen Beziehungen abgeleitet werden können.

Diese vier Repräsentationsmodelle zur Formalisierung topologischer Beziehungen sind in den jeweiligen Literaturreferezen lediglich für den 2-dimensionalen Raum konzipiert. Als erstes Resultat dieser Arbeit werden diese Methoden jedoch ausnahmslos im 3D entwickelt und somit die Betrachtung der relativen räumlichen Lagen von Volumina ermöglicht. Ein Vergleich der vorgestellten Repräsentationsmodelle motiviert schließlich die Wahl, die Menge der topologischen Beziehungen der calculus based method als Grundlage für das GEOTOOLKIT zu verwenden und diese noch um Konzepte anzureichern, welche es erlauben, die interaktiven Arbeitsvorgänge der geowissenschaftlichen Benutzer effizienter zu gestalten. Einen besonderen Stellenwert nimmt hierbei die Dimension von Berührungen zwischen 3D-Objekten ein, welche nunmehr mit Hilfe der topologischen Komponente direkt ablesbar ist, ohne sich auf das visuelle Urteilsvermögen stützen zu müssen, welches bei komplexeren 3D-Situationen oder Grenzfällen schnell überfordert werden kann.

Mit dem gegebenen Repräsentationsmodell topologischer Beziehungen ist somit der Ausgangspunkt für die Umsetzung der entsprechenden topologischen Prädikate und Klassifikationsfunktionen im GEOTOOLKIT gegeben. Bei der Konzeption dieser Komponente wird die interne Darstellung der 3D-Objekte Fläche und Volumen mittels sogenannter simplizialer Komplexe ausgenutzt, da diese aus den sehr einfachen Primitiven (Simplexen) Dreieck bzw. Tetraeder zusammengesetzt sind. Es wird diskutiert, inwiefern man sich diese Tatsache zunutze machen und die topologische Beziehung zweier simplizialer Komplexe aus den einzelnen topologischen Beziehungen ihrer Bestandteile herleiten kann, die sehr viel einfacher zu bestimmen sind. Diese neuartige Herangehensweise kommt vor allem bei dem Entwurf der Funktionen zur Bestimmung der topologischen Beziehungen zum tragen. Die Implementierung der Menge der topologische Prädikate hingegen, kann auf das jeweilige Problem ausgerichetet werden und aus diesem Grund viele räumliche Lagen vernachlässigen. Diese Testfunktionen können mit viel schärferen Abbruchbedingungen ausgestattet werden und haben daher im allgemeinen schnellere Antwortzeiten, als die Klassifikationsmethoden, bei denen keine topologische Lage außer acht gelassen werden kann.

Zum Vorgang der Kombination der Einzelergebnisse wird gezeigt, daß es keine Methode geben kann, durch eine einfache Komposition auf die endgültige Beziehung zwischen den Objekten schließen zu können. In einigen Fällen ist es vielmehr nötig, zusätzlich den Rand der Komplexe mit in die Betrachtung des aktuellen Simplexpaares einzubeziehen oder die topologischen Beziehungen zu den Nachbarsimplexen zu untersuchen. Damit dieser Ansatz jedoch auf eine formale Grundlage gestellt werden kann, werden alle möglichen Paare von topologischen Beziehungen zwischen benachbarten Dreiecken bzw. Tetraedern auf ihren Beitrag zu der Gesamtbeziehung zwischen den betrachteten Flächen bzw. Volumina untersucht, und somit eine Methode entwickelt, die lokal (also höchstens unter Betrachtung der betreffenden Nachbarprimitive) entscheiden kann, ob der neue Beitrag relevant für die topologische Gesamtbeziehung ist und somit einfließt, oder keine Auswirkungen darauf hat. Die Angabe von entsprechenden vollständigen Tabellen und deren Umsetzung in den Klassifikationsfunktionen komplettiert den Ansatz, die Bestimmung der topologischen Beziehung von komplexen Objekten auf ihre Bestandteile herunterzubrechen und stellt damit das Hauptresultat dieser Diplomarbeit dar.

Ein weiteres Konstrukt, das diese Arbeit hervorbringt, bewertet den Abstand von topologischen Beziehungen zueinander (vgl. [EAT92]). Dazu wird der Begriff benachbarter Beziehungen eingeführt und über das Konzept der Transitivität auf den Abstand erweitert. Dieser kann dann von Interesse sein, wenn Geowissenschaftler an der kleinsten Anzahl von minimal signifikanten Veränderungen von 3D-Objekten interessiert sind, die eine topologische Beziehung in eine andere überführen.

Außerdem wird im Rahmen der Erweiterung des GEOTOOLKIT um eine topologische Komponente die Datenstruktur zur Modellierung von Volumina um eine bedarfsorientierte Randverwaltung ergänzt, da das Konzept des Randes von räumlich ausgedehnten 3D-Objekten von großer Bedeutung für deren topologische Lage ist.

Für alle möglichen Paare von Flächen und Volumina werden sowohl topologische Prädikate als auch Klassifikationsfunktionen implementiert, welche aufgrund der Unterschiede ihrer verwendeten Argumente unterschiedliche Herangehensweisen benötigen und auch verschiedene Teilmengen der insgesamt möglichen topologischen Beziehungen zurückliefern, ingesamt jedoch auf einem gemeinsamen Repräsentationsmodell fußen, welches den Geowissenschaftler als Benutzer im Auge hat.

Die Arbeit gliedert sich folgendermaßen: Nachdem die wichtigsten Themen aus dem Gebiet der Geo-Informationssysteme angesprochen werden, wird in 2.2 die Modellierung simplizialer Komplexe als Darstellungsform von Flächen und Volumina im GEOTOOLKIT eingeführt. Eine Betrachtung des Konzeptes der Topologie schließt sich an und endet in der Definition des für diese Arbeit zentralen Begriffes topologischer Beziehungen. Für weitere Untersuchungen ist die Menge topologischer Beziehungen formal zu fassen. In Kapitel 3 werden verschiedene Ansätze beschrieben und miteinander verglichen. Unter dem Gesichtspunkt der Umsetzung der topologischen Beziehungen werden anschließend die wichtigsten 3D-Datenstrukturen und Zugriffsmethoden des GEOTOOLKIT beleuchtet. Ein kurzer Einblick in die Entwicklung des GEOTOOLKIT-Paketes sowie dessen aktuelle Architektur steht am Ende dieses Kapitels.

Die Konzeption der topologischen Komponente ist der zentrale Punkt des 5. Kapitels, in dem speziell auf die Methode der Zerlegung simplizialer Komplexe zur Bestimmung topologischer Beziehungen eingegangen und Probleme angesprochen werden. Außerdem werden hier die Konzepte der Nachbarschaft und des Abstands topologischer Beziehungen erarbeitet. Implementierungsdetails werden schließlich in Kapitel 6 nach einer umfassenden Beschreibung der neuen Funktionalitäten diskutiert. Hier sind auch die Lösungen zu den Problemfällen zu finden, welche innerhalb der Klassifikationsfunktionen auftreten.

Eine Zusammenfassung der wichtigsten Resultate bildet den Abschluß dieser Arbeit, wobei auch noch kurz auf mögliche Erweiterungen der entwickelten topologischen Komponente eingegangen wird.