Institut für Kartographie und Geoinformation
Prof. Dr. Lutz Plümer
Geoinformation II
6. Sem.
Vorlesung 3
27. April 2000
Polygon Overlay
Verwaltung der aktiven Elemente
F
B
S2
S3
C
D
A
S4
S1
E
B
C
E
D
AVL-Baum: L-Rotation
+2
k1
+1
k2
T1
T2
T3
x
Eine Variante des AVL-Baums
• mit einer doppelt verketteten Liste der Blätter
• für die Menge der aktiven Elemente
für die Haltepunkte ...
• ...mit den Operationen
– Einfügen eines gefundenen Schnittpunktes
– Finden und Entfernen des nächsten (also minimalen)
Elements ...
•
•
•
•
... genügt ein „normaler“ AVL-Baum
obwohl man mit Kanonen auf Spatzen schießt
besser: ein Heap
bei Interesse: Vorlesung 2 (heute),
Diskrete Mathematik
Overlay von Polygonen (Landkarten)
• bisher: Overlay von Netzen
• genügt: Bestimmung der Schnittpunkte
• bei Polygonen
– Konstruktion der neuen Polygone
Polygon Overlay
• Problem: Konstruktion der neuen Flächen
A
C
B
Polygon-Overlay
• der Schnitt zweier Kanten führt zu vier neun Kanten
• Problem: Aggregation der neuen Polygone aus den
alten und den neuen Kanten
• Vererbung der Attribute der alten Maschen auf die
neuen Maschen
– Vegetation
– Niederschlag
• wichtigsten Teilproblem: Aggregation der Kante
– Konstruktion einer neuen Verzeigerung zwischen den
Kanten
Datenstruktur für Landkarten
• zur Erinnerung
– Spaghetti
– Knoten-Kanten-Strukturen
– geflügelte Kante
• Variante: doppelt-geflügelte Doppelkanten
• twin(e)
• beachte den Umlaufsinn der Kanten
• Masche liegt immer links
zur Erinnerung:
Datenstrukturen
für Landkarten
Flächen:
Spaghetti
A:
2.0
5.0
7.0
5.0
1.0
0.0
1.0
3.0
4.0
1.0
B:
5.0
7.0
7.0
5.0
4.0
3.0
6.0
6.0
C:
5.0
5.0
5.0
0.0
1.0
4.0
6.0
7.0
3.0
1.0
(5.0 7.0)
(5.0 6.0)
(7.0 6.0)
C
B
(5.0 4.0)
(0.0 3.0)
A
(1.0 1.0)
(2.0 0.0)
(7.0 3.0)
(5.0 1.0)
x
y
Spaghetti
• Vorteile:
– bequem für
Flächenberechnung
– gut für Graphikprogramme
• Zeichnen von
Polygonen
• Nachteile:
–
–
–
–
Topologie nur implizit
fehleranfällig
wenig änderungsfreundlich
Beispiel: Korrektur von
Punktkoordinaten
2.0, 5.0
P1
P2
P3
P1
P5
P4
3.0, 6.0
7.0, 2.0
Kante
Knoten-Maschen-Struktur
Anfangsknoten
P8
Außen
Kanten:
E9
E10
P6
E8
C
P9
E7
P7
B
P4
A
P5
E5
E1
P1
P3
E3
E4
E11
E6
E2
P2
Endknoten
linke
Masche
rechte
Masche
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
..............................................
Knoten:
P1
2.0
0.0
P2
5.0
1.0
..............................................
Knoten-MaschenStruktur
Kante
Anfangsknoten
P8
Außen
E9
E10
P9
E7
P7
P6
E8
C
Kanten:
B
P4
A
P5
E5
E1
P1
P3
E3
E4
E11
E6
E2
P2
Endknoten
linke
Masche
rechte
Masche
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
..............................................
Knoten:
P1
2.0
0.0
P2
5.0
1.0
..............................................
Kanten mit Flügeln
Nachfolger
im Umring der
rechten Masche
Geflügelte Kanten
P8
Außen
E9
E10
E8
C
P9
E7 P6
P7
P4
Kanten:
B
E6
E3
E4
P3
A
E11
P5
E5
E1
P1
E2
P2
Vorgänger
im Umring der
linken Masche
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
.....................................................
Nachfolger
im Umring der
rechten Masche
Geflügelte Kanten
P8
Außen
E9
E10
E8
C
P9
E7 P6
P7
P4
Kanten:
B
E6
E3
E4
P3
A
E11
P5
E5
E1
P1
E2
P2
Vorgänger
im Umring der
linken Masche
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
.....................................................
Nachfolger
im Umring der
rechten Masche
Geflügelte Kanten
P8
Außen
E9
E10
E8
C
P9
E7 P6
P7
P4
Kanten:
B
E6
E3
E4
P3
A
E11
P5
E5
E1
P1
E2
P2
Vorgänger
im Umring der
linken Masche
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
.....................................................
Nachfolger
im Umring der
rechten Masche
Geflügelte Kanten
P8
Außen
E9
E10
E8
C
P9
E7 P6
P7
P4
Kanten:
B
E6
E3
E4
P3
A
E11
P5
E5
E1
P1
E2
P2
Vorgänger
im Umring der
linken Masche
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
.....................................................
Nachfolger
im Umring der
rechten Masche
Geflügelte Kanten
P8
Außen
E9
E10
E8
C
P9
E7 P6
P7
P4
Kanten:
B
E6
E3
E4
P3
A
E11
P5
E5
E1
P1
E2
P2
Vorgänger
im Umring der
linken Masche
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
.....................................................
Datenstruktur für Landkarten
• zur Erinnerung
– Spaghetti
– Knoten-Kanten-Strukturen
– geflügelte Kante
• Variante: doppelt-geflügelte Doppelkanten
• twin(e)
• beachte den Umlaufsinn der Kanten
• Masche liegt immer links
Von Kanten zu Halbkanten
Polygon Overlay
• Problem: Konstruktion der neue Flächen
• wir beschränken uns hier auf einen schwierigen Sonderfall
• alle anderen Fälle leiten sich als Vereinfachungen daraus ab
A
C
B
Maschenumring eines Knotens („Umbrella“)
I
IV
II
III
Problem
• Konstruktion der neuen Maschen
• Update der alten Maschen
• hier: Update der Verzeigerung der Kanten
– explizite Konstruktion der Maschen ist dann einfach
Der neue Regenschirm
I
II
VI
III
V
IV
Beachte
•
•
•
•
Entstehung zweier neuer Maschen
Umring gegeben durch die zu v inzidenten Kanten
sowie die Aufteilung von e in e‘ und e‘‘
Problem: Konstruktion und Update der VorgängerNachfolger-Relationen zwischen Kanten
– Konstruktion zunächst implizit
– explizite Konstruktion und Attributierung siehe später
Geometrische Situation
e
v
Darstellung der Halbkanten
e
v
Nachfolger und Vorgänger von e
e
v
Wo müssen wir etwas tun?
• am Knoten v
– neue Maschen konstruieren
– wie finden wir diese?
– Umlauf definiert
• Ordnung
• Nachbarschaft
• benachbarte Kanten gehören zur gleichen Masche
• an den beiden Endknoten von e
Aufteilung von e in e` und e``
e
v
Aufteilung von e in e` und e``
e``
v
Aufteilung von e in e` und e``
e``
v
e`
Korrektur am Knoten v
e``
v
e`
Korrektur am Knoten v
Erste Halbkante gegen
den Uhrzeigersinn von
e``mit v als Zielpunkt
e``
Erste Halbkante im
Uhrzeigersinn von e`
mit v als Ursprung
Erste Halbkante im
Uhrzeigersinn von e``
mit v als Ursprung
v
Erste Halbkante gegen
den Uhrzeigersinn von
e` mit v als Zielpunkt
e`
Maschenkonstruktion
• im Prinzip einfach
• alle Kanten durchlaufen
• Markierung aller besuchten Kanten liefert
Abbruchkriterium
• Vererbung der Attribute aus den alten Kanten
– einsammeln
Spezialfall
• äußere, unbeschränkte Masche
• Löcher
• als Übung:
• Vorgehen am Schnittpunkt zweier Kanten
• explizite Aufzählung der neuen Maschen und ihrer
Attribute
• Behandlung der unbeschränkten äußeren Masche
• Behandlung von Löchern

e - Institut für Geodäsie und Geoinformation der Universität Bonn