- ...2,5-dimensional
- Ein räumliches Objekt
O im 3-dimensionalen Raum wird als 2,5-dimensional bezeichnet,
wenn folgendes gilt: 8#8.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Volumenelementen
- Diese werden
- analog zu den Pixeln eines 2D-Rasters - Voxel genannt
(vgl. [Sie93]).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Topologie
- Der Begriff der
Topologie wird im nächsten Abschnitt noch eingehend behandelt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Berührung
- Welche
topologischen Beziehungen man unterscheidet, wird in Abschnitt
2.3.2 eingeführt und im anschließenden Kapitel
3 auf die solide Grundlage formaler Modelle
gestellt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Kugeln
- Über Größe und
Form (rund oder oval) der offenen Kreisscheibe/Kugel wird hierbei
nichts ausgesagt - lediglich der Bezugspunkt x soll enthalten sein.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...gültig
- Objekte mit Codimension > 0 sind in
höherdimensionalen Räumen eingebettet. Dieser Begriff wird in
Abschnitt 3.2 definiert.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Raum
- Im Zusammenhang des Raumes
sei für n stets 3 als das Maximum und 0 als Minimum anzusehen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...HREF="node18.html#sub4imdef">3.1.2
- Hier
werden die Begriffe eingeführt, die EGENHOFER in
[Ege89] wählte.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...abdecken
- Für Punkte im 0-dimensionalen Raum gibt
es trivialerweise nur die topologische Beziehung equal, da
alle Punkte im 0D gleich sind.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...möglich
- Die Dimension eines
Durchschnittes kann maximal so groß sein, wie die kleinste
Dimension ihrer Operanden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...ist
- Auf eine Bezeichnung
der einzelnen Beziehungen wird hier aufgrund der großen
Anzahl verzichtet; mögliche Ansätze werden in
3.3.2 angegeben.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...definiert
- Eine
Einführung in den 2-dimensionalen Fall der CBM wird in
[CFvO93] und [CF95] angegeben - der
3-dimensionale Raum wird dort allerdings nicht berücksichtigt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Randoperators
- Der Randoperator der CBM wird in
Definition 3.16 eingeführt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...können
- Einzelheiten hierzu
werden in Abschnitt 3.4.3 angegeben, wo die
CBM u.a. mit der DEM verglichen wird.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Grundbeziehungen
- Die Antisymmetrie der
in-Beziehung wird hier durch das doppelte Vorkommen
eines in im Baum erfaßt, so daß man 6 Beziehungen
erhält.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Volumina
- In [CFvO93]
wird dieser Satz lediglich für Objekte mit Dimensionen < 3
bewiesen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...DEM
- Vgl. hierzu
Abschnitt 3.3.1, wo alle Fälle der
Volumen/Volumen-Situation aufgelistet sind.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...sind
- Hier
wird der Satz wieder nur für zwei Volumina im 27#27
bewiesen - Objekte mit Dimensionen < 3 werden in
[CF95] betrachtet.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...bewiesen
- Da sich diese
Arbeit vor allem im 3D bewegt, betrachten wir auch hier wieder
nur den Volumen/Volumen-Fall. CLEMENTINI und
DI FELICE legen in [CF95] den 2D
zugrunde, so daß alle Fälle niederdimensionaler Objekte
dort nachgeschlagen werden können.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Basisterm
- Das sind die 5
topologischen Beziehungen und die 4 Randoperatoren, welche
aber nur ein n-dimensionales in ein (n-1)-dimensionales
Objekt überführen und demnach vernachlässigt werden können.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Raum
- Da cross in diesem Szenario
nicht existiert, wird hier stattdessen von einem Volumen und
einer Fläche ausgegangen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...persistenten
- Man spricht von persistenten
Daten, wenn die Informationen nach Beendigung der aktuellen
Bearbeitung weiterhin bestehen, während die Lebensdauer
transienter Daten auf die Sitzung beschränkt ist, in der
sie erzeugt wurden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Modellierung``
- Der
SFB 350 ist eine Fördereinrichtung der Deutschen
Forschungsgemeinschaft (DFG).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...C4
- Das
Teilprojekt C4 ,,Quantitative Modellierung der tektonischen
und sedimentären Entwicklung der Niederrheinischen Bucht`` des
SFB 350 steht in enger Zusammenarbeit zum Teilprojekt D4.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Volumina
- Im
Kontext der Geologie stellen Volumina Erdschichten dar, die
durch andere Schichten und seitliche Störungen (Flächen)
getrennt sind. Vgl. hierzu auch [Sie93].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...GEOSTORE-Implementierung
- Zu den Ausführungen
dieses Abschnittes vgl. [BBC97].
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...muß
- Ein anderes Beispiel ist die topologische Überprüfung
von Integritätsbedingungen auf digitalisierten Datensätzen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Tetraedernetzes
- Die
Definition von Dreiecks- und Tetraedernetzen erfolgt in Abschnitt
4.3.1 resp. 4.3.2, wozu das Konzept eines
simplizialen Komplexes weiter eingeschränkt werden muß.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...GEOTOOLKIT implementieren
- Der R-Baum (gtRTree) wird in
Abschnitt 4.4.2 vorgestellt, während an einer Version eines
Octrees (gtOcTree) gerade gearbeitet wird.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...GEOTOOLKIT
- Eine Spatial SQL-Schnittstelle zur Klasse
gtSpace ist momentan in der Entwicklung.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Breitensuche
- Eine Breitensuche oder BFS
durchläuft das Netz ausgehend von einem Startdreieck, indem zuerst
alle Nachbarn besucht werden, bevor nacheinander zu den Nachbarn
verzweigt und der Vorgang wiederholt wird.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...R-Baum
- Der R-Baum geht auf eine Arbeit von
GUTTMAN aus dem Jahre 1984 zurück ([Gut84]).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...minimieren
- Ein weiteres Kriterium für den Aufbau eines
R-Baumes stellt die Minimierung der enthaltenen Bounding-Boxen (Volumen
und Oberfläche) dar.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...vor
- Diese Probleme
mußten bisher über den Umweg der Einschätzung des Betrachters in
einem Visualisierungstool gelöst werden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...gtTriangleNet
- Auf die GEOTOOLKIT-Klassen
gtTetraNet und gtTriangleNet wurde schon in
Kapitel 4 unter 4.3.1 und
4.3.2 genauer eingegangen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Objekt
- Hierbei
spielt es keine Rolle, ob es sich um eine Fläche oder ein Volumen
handelt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...können
- Es
ist zu beachten, daß die Bedingung dieser Aussage damit erfüllt
ist, daß es zu den Datenstrukturen Fläche (gtTriangleNet)
und Volumen (gtTetraNet) im GEOTOOLKIT Methoden gibt, womit deren
Ränder bestimmt werden können.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...ni
- Das ni als inverser
topologischer Beziehung zum in entspricht also einer echten
contains-Beziehung.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Beziehungen
- Hierbei wurde die topologische Beziehung
disjunkter 3D-Objekte vernachlässigt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Nachbarschaftsgraph
- PAPADIAS ET AL geben
in [PAK98] einen solchen Nachbarschaftsgraph
topologischer Beziehungen für das 4-Intersection-Modell an.
Analog wird in [EAT92] der Graph auf der Grundlage des
9-Intersection-Modells von EGENHOFER und
AL-TAHA entwickelt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Kante
- Die in Abb. 226#226 mit einem 223#223 markierten
Kanten gelten jedoch nur für die Fälle, in denen die topologischen
Beziehungen zwischen einer Fläche und einem Volumen betrachtet
werden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...sind
- Die Implementierung
dieser Prädikate wird im folgenden 6. Kapitel
betrachtet.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...vorzunehmen
- In
Abb. 5.4 ist ein Beispiel der Reduktion auf die
Simplexe zu finden. Hier ist der Fall zweier Dreiecksnetze, welche in einer
Ebene liegen, dargestellt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...vorkommen
- Dies stimmt sogar - der Ansatz als solches
ist jedoch nicht brauchbar, wie noch gezeigt wird.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...konstruieren
- Benachbarte
Paare von touch_2D und covered_2D können beispielsweise
auf dem Rand eines Volumens auftreten oder aber im Inneren (auf dem
Rand eines Tetraeders). Im ersten Fall folgt ein overlap,
während dies in der zweiten Konfiguration nicht der Fall sein muß!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...können
- Bei
cross liegen die beiden benachbarten Dreiecke auf
entgegengesetzten Seiten der Ebene, die durch das andere Dreieck
definiert wird, und bei touch_1D auf der gleichen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...wären
- Auf diesen
speziellen Fall wird später noch genauer eingegangen (vgl. Abb. 6.6
auf Seite 88).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...ist
- Die default-Werte der
strict-Flags betragen jedoch 0.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...touch
- Das gleiche gilt natürlich
auch für die dimensionsbehafteten Varianten.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Teilelemente
- Ein Berührpunkt 235#235 wird also nicht erfaßt,
wenn es auch ein Berührsegment 236#236 oder ein Berührdreieck
237#237 gibt. Würde sowohl das Segment als auch das Dreieck
vorkommen, so wäre auch das Berührsegment zu vernachlässigen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...kodiert
- Eine genauere Beschreibung ist in Abschnitt
6.3 zu finden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...werden
- Dieses Vorgehen entspricht insofern der
Intuition, daß es sich mit den betrachteten Flächen um 2D-Objekte im
3-dimensionalen Raum handelt und Berührungen nur kleinere Dimensionen
als die beteiligten Objekte aufweisen dürfen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...benachbart
- Sie haben also den Abstand 1 -
vgl. Nachbarschaftsgraph (Abb. 5.3 auf Seite 61).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...intersects
- In diesem Fall zwischen
Dreiecksnetzelementen (Dreiecken) und Segmenten.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...realisiert
- Weitere Details dieses Sonderfalles
sind in Abschnitt 6.2.3 zu finden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...zurück
- Da der Algorithmus im wesentlichen selbsterklärend
ist, soll nicht näher auf ihn eingegangen werden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...vorgehalten
- Für jede mögliche
Klasse topologischer Beziehungen (touch, cover) wird ein Flag
bereitgestellt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...wurde
- Diese Situation wird von der Funktion
nextTwoTouch aus der Klasse gtTetraNet erkannt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Anpassungen
- Hierbei sind die Beziehungen ni
durch in und covers durch covered zu
ersetzen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...bewirken
- Ein ni der Primitive legt
so beispielsweise das ni der Netze nahe: das entsprechende
Flag wird gesetzt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Lagen
- Hierzu gehören also covered_0D,
covered_1D und ni.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Ebene
- Hier wird
oBdA diejenige Ebenen verwendet, die durch den Endpunkt 235#235 des
Segmentes gegeben ist.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Ebene
- Die Punkte 263#263/264#264
gehören hierbei zu dem einen und 265#265/266#266 zu dem anderen
Dreieckspaar.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...betrachten
- Die Anzahl der im Zuge der aktuellen Berechnung
zusätzlich zu untersuchenden Simplexe ist auf die Kardinalität der
Nachbarmenge beschränkt.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Netzen
- Dies ist dann der Fall, wenn die Größen der
enthaltenen Simplexe beider Objekte nicht sehr differieren.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Fällen
- Die Ausnahmen bilden hier nur die topologischen
Beziehungen overlap im Volumen/Volumen- und
Fläche/Fläche-Fall bzw. cross für die Situation einer
Fläche und eines Volumens, da in diesen Fällen die Berechnungen
vorzeitig abgebrochen werden können.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Berührdimensionen
- Es
werden alle möglichen Dimensionen erkannt und gleichzeitig
kodiert zurückgeleifert.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...Listen
- Hierfür kann die Funktionalität os_list
von OBJECTSTORE verwendet werden.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...ist
- Ist die Liste
xyList leer, so beträgt der Wert zu xyTouch 0.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...entspricht
- Eine 7 bedeutet also, daß sowohl ein
Berühr-Punkt, -Segment und -Dreieck zwischen den beiden
Tetraedernetzen aufgetreten ist.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
- ...ist
- Eine
Neuimplementierung wird gerade von JöRG SIEBECK im
Rahmen der Arbeit [Sie99] vorgenommen.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.