View
108
Download
5
Category
Preview:
Citation preview
1
Landkarten
• Landkarten sind Tesselationen mit folgenden Eigenschaften:a) jede Masche ist der
geschlossenen Kreisscheibe topologisch äquivalent
b) die Aggregation aller inneren Maschen ist der geschlossenen Kreisscheibe topologisch äquivalent
• Beachte: zu jeder Landkarte gehört eine unbeschränkte Masche „Außen“ - die einzige Masche, die nicht der geschlossenen Kreis-scheibe äquivalent ist
2
Datenstrukturen für Landkarten
Landkarten
Nachbarschaften
A: 2.0 0.0 5.0 1.0 7.0 3.0 5.0 4.0 1.0 1.0
B: 5.0 4.0 7.0 3.0 7.0 6.0 5.0 6.0
C: 5.0 4.05.0 6.0 5.0 7.00.0 3.0 1.0 1.0
Spaghetti
(5.0 4.0)
(5.0 1.0)
(2.0 0.0)
(7.0 3.0)
(1.0 1.0)
(7.0 6.0)
(5.0 6.0)
(5.0 7.0)
(0.0 3.0)
A
BC
4
UML-Diagramm für die Spaghetti-Struktur
M asche
Koordinate
2n
1..1
{geordnet}
5
Masche
Punkt
n
1..1
{geordnet}
UML-Diagramm für Spaghetti-Struktur mit Punkten
6
Typischer Fehlerfall für Spaghetti: Änderung der Koordinaten eines gemeinsamen Punktes
vorher
nachher
7
P2
P1
P3
P6
P7
P8
P9
A
BC
Flächen:
A: P1 P2 P3 P4 P5
B: P4 P3 P6 P7
C: P4 P7 P8 P9 P5
P5
P4 Punkte:P1 2.0 0.0P2 5.0 1.0P3 7.0 3.0P4 5.0 4.0P5 1.0 1.0P6 7.0 6.0.............................
Punktobjekte ohne Redundanz
8
Masche
Punkt
n
1..n
{geordnet}
Beachte: Redundanzfreiheitkann durch dies UML-Diagrammnicht erzwungen werden.
UML-Diagramm für Spaghetti-Struktur mit Punkt-Objekten
9
UML-Diagramm für die Knoten- und Kantenstruktur
3..*
Masche
2
begrenzt
Kante
2
2..*
begrenzt
Knoten
Punkt
1
1Geometrie
neu
Topologie explizit
Redundanzfreiheit wirderzwungen
10
P1
E6
E11
P2
P3
P6P7
P8
P9
A
BC
P5
P4
E1
E2
E3E4
E5
E7
E8
E9
E10
Außen
Knoten:P1 2.0 0.0P2 5.0 1.0..............................................
Kante
Anfangs-knoten
End-knoten
linkeMasche
rechteMasche
E1 P1 P2 A Außen
E2 P2 P3 A Außen
E3 P3 P4 A B
E4 P4 P5 A C
E5 P5 P1 A Außen
E6 P3 P6 B Außen
..............................................
Kanten:
Knoten-Maschen-Struktur
11
Vor- und Nachteile der Knoten- und Kanten-Struktur
• Vorteile:– Geometrie ist
redundanzfrei
– Topologie ist explizit
– bei Änderungen können Fehler leichter vermieden werden
• Nachteil– der Kantenumring ist nicht
direkt gegeben, sondern muß berechnet werden
• Lösung: Kanten mit Flügeln
12
Kanten mit Flügeln
13
Geflügelte Kanten
P1
P8
P2
P3
P6P7
P9
A
BC
P5
P4
E1
E2
E3E4
E5
E6
E7
E8
E9
E10
E11
Außen
E1 P1 P2 A Außen E5 E2
E2 P2 P3 A Außen E1 E6
E3 P3 P4 A B E2 E8
E4 P4 P5 A C E3 E11
E5 P5 P1 A Außen E4 E1
E6 P3 P6 B Außen E3 E7
.....................................................
Kanten:
Wie bei Knoten-Kanten-
Struktur
Vorgängerim Umring derlinken Masche
Nachfolgerim Umring der
rechten Masche
14
Die Euler-Formel
• Für jede Landkarte mit – f Maschen (face)– e Kanten (edge)– v Knoten (vertex) gilt:
f - e + v = 2
• Euler-Charakteristik:– Landkarte: 2– Landkarte mit n Kontinenten: n + 1– Landkarte mit n Inseln und m Kontinenten: n + m + 1
• beachte: Außen zählt als eigene Masche!
Euler-Charakteristik
15
Topologische Fehler (I)
Fehlender Knoten Zwei Referenzpunkte (Namen)
Undershoot
Overshoot
Fehlender Referenz-punkt (Name)
16
Topologische Fehler (II)
• Überlappung zweier Maschen ohne Überschneidung von Kanten
17
Integritätsbedingungen für Landkarten (I)
1. Schnittfreiheit der Kanten
2. Jede Kante hat zwei Maschen auf verschiedenen Seiten
3. Jede Masche wird von einem einfachen Zyklus begrenzt
4. Kein Mittelpunkt einer Kante liegt in einer Masche
falsch richtig
18
Integritätsbedingungen für Landkarten (II)
1. Schnittfreiheit der Kanten
2. Jede Kante hat zwei Maschen auf verschiedenen Seiten
3. Jede Masche wird von einem einfachen Zyklus begrenzt
4. Es gibt genau eine unbeschränkte Masche
falsch richtig
19
Zusammenfassung „Geometrisch-Topologische Datenstrukturen“
• Spaghetti mit Koordinaten: redundante Geometrie• Spaghetti mit Punkten: redundante Geometrie• Spaghetti mit Punkten als Objekten: redundanzfreie
Geometrie• Knoten-Kanten-Struktur: redundanzfreie Geometrie, explizite
Topologie, Maschenumring muß berechnet werden• geflügelte Kanten: redundanzfreie Geometrie, explizite
Topologie, Maschenumring leicht zu berechnen
20
Aus Landkarten abgeleitete Strukturen
• quadratische Maschen gleicher Größe:Raster, Grid– kompakte Speicherung– homogene Informationsdichte
• Maschen sind Dreiecke– Triangulation
– gut zur Modellierung des Geländes
• Verallgemeinerung– Simplizes
– Simpliziale Komplexe
21
Simplizes
• Ein 0-Simplex ist ein Punkt
• Ein 1-Simplex ist eine gerade Kante
• Ein 2-Simplex ist ein Dreieck (Inneres + 3 Kanten + 3 Knoten)
• Ein 3-Simplex ist ein Tetraeder
Beachte: Das Schwierige an den
Simplexen ...
... ist der Plural
23
Teilsimplizes
• Ein Knoten ist Teilsimplex einer Kante
• Eine Kante ist Teilsimplex eines Dreiecks
• Ein Dreieck ist Teilsimplex eines Tetraeders
• Der Teilsimplex T eines Simplex S ist ein Simplex, dessen Knoten alle in S vorkommen.
• Der Rand eines Simplex ist die Menge aller Teilsimplizes.
Randeines Dreiecks
24
Simpliziale Komplexe
• Ein Simplizialer Komplex C ist eine Menge von Simplizes mit folgenden Eigenschaften:– jeder Teilsimplex in C ist
ebenfalls in C
– der Durchschnitt zweier Simplizes in C ist entweder leer oder in C
falsch:
25
Simpliziale Komplexe
• Ein Simplizialer Komplex C ist eine Menge von Simplizes mit folgenden Eigenschaften:– jeder Teilsimplex in C ist
ebenfalls in C
– der Durchschnitt zweier Simplizes in C ist entweder leer oder in C
Korrektur:
26
Simpliziale Komplexe
• Ein Simplizialer Komplex C ist eine Menge von Simplizes mit folgenden Eigenschaften:– jeder Teilsimplex in C ist
ebenfalls in C
– der Durchschnitt zweier Simplizes in C ist entweder leer oder in C
Korrektur:
27
Anwendungen
• Geländemodell• Computergraphik• Eisberge• ...
28
Resümee
• Landkarten– 2D– beliebige Polygone
• Simpliziale Komplexe– Dreiecke– auch 3D
• Gemeinsamkeiten– Konstruktion des Raumes
durch Aggregation atomarer Primitive
– „algebraische“ oder „kombinatorische“ Topologie
• zurück zur „Punktmengentopologie“
Recommended