Upload
adalwolf-karmann
View
107
Download
2
Embed Size (px)
Citation preview
Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer
Geoinformation II6. Sem.Vorlesung 5
18. Mai 2000
Konstruktion des Voronoi-Diagramms II
22
Divide and Conquer: Merge
33
Konstruktion des Voronoi-Diagramms
„Divide and Conquer“• Input: Gegeben ist eine Menge P von mindestens 2 Punkten
• Split: Zerlege P in zwei etwa gleich große Teilmengen P1 und P2
• Rekursiv: Berechne Voronoi-Diagramme von VD(P1) und VD(P2)
• Merge: Verknüpfe VD(P1) und VD(P2)
44
„Merge“
• Die Voronoi-Diagramme VD(P1) und VD(P2) sind bereits berechnet.
• Die konvexen Hüllen CH(P1) und CH(P2) seien ebenfalls an dieser Stelle bekannt.
1. Bestimme die oberen und unteren Extrempunkte und die beiden oberen und unteren Tangenten von CH(P1) CH(P2)
2. Konstruiere CH(P1 P2)
3. Bilde die Mittelsenkrechten zu den beiden neu eingeführten Kanten
4. Konstruiere den trennenden Kantenzug als Verbindung der beiden Mittelsenkrechten
5. Entferne die überstehenden Kanten
6. Bilde die neu entstandenen Voronoi-Regionen (Maschen)
55
max y
min ymin y
max y
Extrempunkte von CH(P1) CH(P2)
66
Tangente von CH(P1) CH(P2)
77
Nochmals zur konvexen Hülle CH
Was wissen wir über die „konvexe Hülle“ CH(P) einer Punktmenge P?
Die Extrempunkte sind die Knoten auf der Grenze von CH.
• Zu je zwei Punkten P1 und P2 ist die verbindende Kante ganz in CH enthalten.
• Der obere und der untere Extrempunkt zerlegen die Grenze von CH in zwei vertikal monotone Kantenzüge.
• Die Verbindungskante k zweier Punkte P1 und P2 aus P definiert eine Randkante von CH genau dann, wenn alle übrigen Punkte von P auf der gleichen Seite von k liegen.
• P2 ist genau dann Nachfolger von P1 auf dem Rand von CH, wenn der zugehörige polare Winkel von P2 minimal ist.
88
Tangente
99
Nachfolger - Bestimmung
Winkel minimal
P1
P2
1010
Nachfolger
Winkel minimal
P2
P1
1111
Bestimmung der (oberen) Tangenten der konvexen Hüllen
• Bestimme die oberen und unteren Extrempunkte von CH(P1), CH(P2) und CH(P1) CH(P2)
• Betrachte die oberen Extrempunkte P1 und Q1 und die Nachfolger P2 und Q2 im Uhrzeigersinn, und sei P1 höher als Q1
• Bestimme das Minimum der mit P1P2, P1Q1 und P1Q2 assoziierten Winkel
• Fälle:– P1 Q1 ist minimal: Tangente gefunden, fertig
– P1 P2 minimal: ersetze P1 durch P2 und P2 durch P3 (wandere auf der linken konvexen Hülle im Uhrzeigersinn)
– P1 Q2 minimal: ersetze Q1 durch Q2 und Q2 durch Q3 (wandere auf der rechten konvexen Hülle im Uhrzeigersinn)
• Der Fall der unteren Tangente ist symmetrisch
1212
Extrempunkte
1313
2 vertikal monotone Kantenzüge
1414
Tangente
1515
Bestimmung des Nachfolgers
Winkel nicht minimal
1616
Bestimmung des Nachfolgers
Winkel minimal
1717
Bestimmung des Nachfolgers
1818
Bestimmung des Nachfolgers
1919
Konvexe Hülle
2020
Bestimmung des Nachfolgers
2121
Konvexe Hülle
2222
Konstruiere den trennenden Kantenzug als Verbindung der beiden Mittelsenkrechten
2323
Vereinigung
Mittelsenkrechte bilden
2424
Vereinigung
2525
Vereinigung
Aktive Voronoi-Diagramme
Schnittpunkte mit Seg-menten suchen
2626
Vereinigung
Aktive Voronoi-Diagramme
Schnittpunkte mit Seg-menten suchen
Neues aktives VD
2727
Vereinigung
Aktive Voronoi-Diagramme
Schnittpunkte mit Seg-menten suchen
Neues aktives VD
Mittelsenkrechte zuwischenden aktiven VD
2828
Vereinigung
Schnittpunkte suchen
2929
Vereinigung
Schnittpunkte suchen
Neues aktives VD suchen
3030
Vereinigung
Schnittpunkte suchen
Neues aktives VD suchen
3131
Vereinigung
Schnittpunkte suchen
Neues aktives VD suchen
Mittelsenkrechte deraktiven VD
3232
Vereinigung
Schnittpunkte suchen
3333
Vereinigung
Schnittpunkte suchen
Neues aktives VD suchen
3434
Vereinigung
Schnittpunkte suchen
Neues aktives VD suchen
Mittelsenkrechte deraktiven VD
3535
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
3636
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
Mittelsenkrechte deraktiven VD
3737
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
3838
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
Mittelsenkrechte deraktiven VD
3939
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
4040
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
Mittelsenkrechte deraktiven VD
4141
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
4242
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
Mittelsenkrechte deraktiven VD
4343
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
4444
Vereinigung
Nächsten relevanten Schnittpunkte suchen
Neues aktives VD suchen
Verknüpfung mit der Mittel-senkrechten vom Anfang
4545
Konstruiere den trennenden Kantenzug als Verbindung der beiden Mittelsenkrechten
• gegeben: die beiden oberen und unteren Mittelsenkrechten g und g*
• die zugehörigen oberen Voronoi-Regionen seien P und Q
• Solange die untere Mittelsenkrechte noch nicht erreicht ist– Bestimme für die aktuelle Mittelsenkrechte
• die Austrittspunkte p und q aus den aktuellen Voronoi-Regionen, • die zugehörigen Kanten• die zugehörigen Nachbarn P‘ und Q‘
– wenn p höher ist als q• ersetze P durch P‘ und schneide g an der Stelle p ab
– wenn q höher als p • ersetze Q durch Q‘ und schneide g an der Stelle q ab
– bestimme die aktuelle Mittelsenkrechte g des neuen Paares P, Q
4646
Länge des Kantenzuges im Worst Case
O(n)
4747
Größenordnung des Kanten-Umrings im worst case
O(n)
4848
O(n) * O(n) = O(n2) ?
Voronoi-Regionen sind konvex
Kantenzug ist monoton
war jetzt alles umsonst?
4949
O(n) * O(n) = O(n2) ?
Voronoi-Regionen sind konvex
Kantenzug ist monoton
Keine Kante öfter als zwei mal anfassen!
5050
„Investitionen müssen sich amortisieren“
• Ziel: keine Kante mehr als zwei mal „anfassen“• Es gibt insgesamt höchstens 3* n – 6 Kanten O(n)• Konvexität der Voronoi-Regionen höchstens
zwei Schnittpunkte mit der aktiven Halbgeraden• Es genügt, die linken (grünen) Kantenumringe im
Uhrzeigersinn und die rechten (roten) Kantenumringe gegen den Uhrzeigersinn zu durchlaufen und den zuletzt gefundenen und verworfenen Schnittpunkt als Haltepunkt zu merken!