Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation Vorlesung 9 SS 2001 Voronoi-Diagramme: Bestimmung der Tangente bei der

Institut für Kartographie und GeoinformationProf. Dr. Lutz Plümer

GeoinformationVorlesung 9

SS 2001

Voronoi-Diagramme: Bestimmung derTangente bei der Konstruktion des

trennenden Kantenzuges

Lutz Plümer - Diskrete Mathematik II - SS 2000 - Vorlesung 9 - 29.06.00 Lutz Plümer - Diskrete Mathematik - 2. Semester - SS 2001 - Vorlesung 9


2 2

Übersicht I

• Bestimmung der Tangente• Extrempunkte von CH(P1) CH(P2)• Tangente von CH(P1) CH(P2)• Nochmals zur konvexen Hülle CH• Tangente• Nachfolger - Bestimmung• Nachfolger• Bestimmung der (oberen) Tangenten der konvexen

Hüllen



3 3

Übersicht II

• Extrempunkte• 2 vertikal monotone Kantenzüge• Tangente• Bestimmung des Nachfolgers• Konvexe Hülle• Bestimmung des Nachfolgers• Konvexe Hülle



4 4

Bestimmung der Tangente

• im Detail



5 5

max y

min ymin y

max y

Extrempunkte von CH(P1) bzw. CH(P2)



6 6

Tangente von CH(P1) CH(P2)



7 7

Tangente von CH(P1) CH(P2)



8 8

Extrempunkte: Funktioniert das immer ?



9 9

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.



10 10

Tangente



11 11










12 12

Extrempunkte



13 13

2 vertikal monotone Kantenzüge



14 14

Tangente



15 15










16 16

Nachfolger - Bestimmung

Winkel minimal

P1

P2

P3

P4



17 17

Nachfolger

Winkel minimal

P2

P1

P3

P4



18 18

Bestimmung der (oberen) Tangenten der konvexen Hüllen

1. Betrachte die oberen Extrempunkte P1 und Q1 und die Nachfolger P2 und Q2 im Uhrzeigersinn, und sei P1 höher als Q1

2. Bestimme das Minimum der mit P1P2, P1Q1 und P1Q2 assoziierten Winkel

3. 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)

4. weiter mit 2.

Der Fall der unteren Tangente ist symmetrisch



19 19

Bestimmung des Nachfolgers

Winkel nicht minimal

P1

P2

Q1

Q2



20 20


Winkel minimal

P1

P2

Q1

Q2



21 21


P1

P2

Q1

Q2

P3



22 22




23 23




24 24




25 25

Konvexe Hülle

Documents

Institut für Kartographie und Geoinformation Prof. Dr. Lutz Plümer Geoinformation Vorlesung 9 SS 2001 Voronoi-Diagramme: Bestimmung der Tangente bei der