Triangulierung von einfachen Polygonen - zaik.uni-koeln.de · i konvex ist und bei der das Dreieck 4P i 1P iP i+1 keinen von den ub rigen Eckpunkten enth alt (Entsprechendes de nieren

1.1 Die Problemstellung2.1 Ein naiver Algorithmus

3.1 Zerlegung in monotone Teilpolygone3.2 Triangulierung monotoner Polygone

Triangulierung von einfachen Polygonen

- Seminarvortrag von Tobias Kyrion -

Inhalt:

1.1 Die Problemstellung

2.1 Ein naiver Algorithmus

3.1 Zerlegung in monotone Teilpolygone

3.2 Triangulierung monotoner Polygone

Quellenangabe



1.1 Die Problemstellung

Definition

Polygon:endlich viele paarweise verschiedene EckpunkteP1, ...,Pn ∈ R2, n ∈ N

Seiten:Verbindungsstrecken PiPi+1, i = 1, ...,n− 1 und PnP1

einfach:Die Seiten schneiden sich paarweise nicht.

Sinnvoll: eine Orientierung der Seiten

Im Folgenden seien diese immer im Uhrzeigersinn angeordnet.



Beispiel 1.1: kein einfaches Polygon

1

2

3

45

67

89

10

11

12

1314

15

16

1718

Beispiel 1.2: einfaches orientiertes Polygon



Definition

Diagonale:Verbindungsstrecke von zwei EckpunktenPk,Pl, k, l ∈ {1, ...,n}, k 6= l, die selbst keine Seite ist, keineandere Seite schneidet und vollstandig im Inneren des Polygonsverlauft

Letzteres bedeutet:Durch Einfugen der Diagonale wird das Polygon in zwei kleineredisjunkte Teilpolygone zerlegt.

Die Diagonale ist dann jeweils eine Seite dieser Teilpolygone,welche beide auch einfach sind.



Fur einfache Polygone existiert mindestens eine Diagonale.

Dreiecke sind offenbar Polygone mit kleinstmoglicherEckenanzahl, die einfach sind und in die man keine Diagonale mehreinsetzen kann.

Induktiv beweist man somit, dass fur jedes einfache Polygon eineZerlegung in Dreiecke konstruierbar ist.



Solch eine Zerlegung nennt man Triangulation.

Problemstellung:Bestimme Triangulation nur durch Hinzunahme von Diagonalen.

Beachte:Neue Diagonalen durfen die bereits eingefugten nicht schneiden,denn es sollen keine inneren (Schnitt-)Punkte generiert werden.

Außerdem:Eine Triangulation eines einfachen Polygons mit n ∈ N Eckpunktenbesteht immer aus n− 2 Dreiecken.



2.1 Ein naiver Algorithmus

Wie erzeugt man nun algorithmisch eine Triangulation?

Eine mogliche Realisierung bietet der sogenannteear-clipping-Algorithmus.



Definition

Ecke:zwei (bzgl. der Orientierung) aufeinanderfolgende Seiten, alsoPi−1PiPi+1, i = 2, ..,n− 1 und PnP1P2, Pn−1PnP1

Innenwinkel :Die Seiten einer Ecke Pi−1PiPi+1 umschließen am mittleren PunktPi jeweils zwei Winkel (i = 2, ..,n− 1). In Durchlaufrichtungrechts von den Seiten Pi−1Pi und PiPi+1 liegt der Innenwinkel.

konvex :Ein konvexer Eckpunkt Pi hat einen Innenwinkel kleiner als 180◦.



Definition

Ohr :Ecke Pi−1PiPi+1, deren mittlerer Punkt Pi konvex ist und bei derdas Dreieck 4Pi−1PiPi+1 keinen von den ubrigen Eckpunktenenthalt

(Entsprechendes definieren wir auch fur die beiden Ecken PnP1P2

und Pn−1PnP1.)α

Pi−1

Pi

Pi+1

Beispiel 2.1: einfaches Polygon mit Ohr Pi−1PiPi+1 und α < 180◦



Prinzip des ear-clipping-Algorithmus:

Bei einem Ohr Pi−1PiPi+1 ist die Strecke Pi−1Pi+1 eine Diagonale.

Durchlaufe solange die Eckpunkte, bis einer dieser als mittlererPunkt eines Ohres identifiziert wird.

Fuge die zum gefundenen Ohr gehorende Diagonale ein - das Ohrwird dadurch vom Polygon abgetrennt.

Das verbleibende Restpolygon besitzt nun einen Eckpunkt wenigerals das Gesamtpolygon.

Fuhre die vorigen Schritte iterativ fur die jeweiligen Restpolygoneaus, bis das letzte von denen nur noch drei Ecken besitzt.



0

P1

P2

P3

P4

P5

P6

P7

1

P1

P2

P3

P4

P5

P6

2

P1 P2

P3

P4

P5

3

P1

P2

P3

P4

4

P1

P2

P3

5

Beispiel 2.2: ein Durchlauf des ear-clipping-Algorithmus



Zur Korrektheit:

Alle einfachen Polygone besitzen mindestens ein Ohr.

Nach Abtrennen eines Ohres ist das verbleibende Teilpolygoneinfach - dieses besitzt somit auch ein Ohr.

Bei jedem Abtrennen eines Ohres wird die Eckenanzahl n um 1verkleinert, d.h. der Algorithmus terminiert nach ngesamt − 3Iterationen.



Zur Laufzeit:

Prufen, ob Punkt x in Dreieck 4abc liegt:

O(1)

Prufen, ob aktuelle Ecke Pi−1PiPi+1 ein Ohr ist (liegt einer vonden n− 3 anderen Eckpunkten in 4Pi−1PiPi+1?):

O(n− 3)

Die Laufzeitsumme aller Iterationen - also die Gesamtlaufzeit -betragt hochstens:

O(∑n

k=4(k− 3)) = O(n2)

Der ear-clipping-Algorithmus besitzt folglich quadratischeLaufzeit.



3.1 Zerlegung in monotone Teilpolygone

Frage:

Gibt es schnellere Algorithmen zur Triangulation?

Strategie, um die Laufzeit zu verbessern:

1. Zerlege das einfache Polygon in monotone Polygone, welchein diesem Abschnitt behandelt werden.

2. Trianguliere diese in Linearzeit, was im nachsten Abschnittgezeigt wird.



Definition

monoton:Sei g ⊂ R2 eine Gerade.

Ein einfaches Polygon ist monoton bzgl. g, wenn die Schnittmengealler Geraden, die orthogonal zu g verlaufen, mit der vom Polygonbegrenzten Flache entweder die leere Menge, ein Punkt, oder eineStrecke ist.

Man nennt g dann auch die Monotonieachse.

g

Beispiel 3.1: monotones Polygon mit Monotonieachse g



Definition

x-monoton bzw. y-monoton:Ein monotones Polygon ist x-monoton bzw. y-monoton, falls diex-Achse bzw. die y-Achse des kartesischen Koordinatensystems imR2 seine Monotonieachse ist.

Der nachfolgende Algorithmus zerlegt ein einfaches Polygon inx-monotone Teilpolygone.



Er funktioniert nach dem scan-line-Prinzip:

Lasse eine imaginare zur y-Achse parallele Gerade - die scan-line -von links nach rechts uber das gesamte Polygon wandern.

Verarbeite stets nur Punkte, die bereits links von der scan-lineliegen.

Speichere diese Punkte in einer priority-queue. Punkte mitgroßerer x-Koordinate haben dabei hohere Prioritat.

Suchen, Einfugen oder Loschen von Punkten in der priority-queueist in O(log(n)) Zeit moglich.



Wir stellen fest:

Das Polygon besitzt:

einen Eckpunkt Pl, der von allen Eckpunkten am weitestenlinks liegt

einen Eckpunkt Pr, der von allen Eckpunkten am weitestenrechts liegt

eine obere Kette (d.h. ein Streckenzug bestehend ausSeiten), die bei Pl beginnt und bei Pr endet

eine untere Kette, die ebenfalls bei Pl beginnt und bei Pr

endet



(Zur Vereinfachung nehmen wir an, dass es keine zwei Eckpunktemit gleichen y-Koordinaten gibt.)

Alle Eckpunkte der oberen Kette, außer naturlich Pl und Pr, liegenoberhalb der unteren Kette.



Wir wandern nun gleichzeitig entlang der oberen und unterenKette von links nach rechts.

Es kann dabei passieren, dass sich dabei die Durchlaufrichtungvon rechts nach links oder links nach rechts andert.

Definition

turn-vertex :Eckpunkt, an dem sich die Durchlaufrichtung andert (d.h. seinVorganger und sein Nachfolger haben beide großere bzw. kleinerex-Koordinaten als der turn-vertex)



Um den Algorithmus zu bewerkstelligen, unterteilen wir dieEckpunkte in 5 Typen - die ersten 4 davon sind turn-vertices:

Definition

start-vertex :Innenwinkel kleiner als 180◦, Nachbarn beide rechts

end-vertex :Innenwinkel kleiner als 180◦, Nachbarn beide links

split-vertex :Innenwinkel großer als 180◦, Nachbarn beide rechts

merge-vertex :Innenwinkel großer als 180◦, Nachbarn beide links

regular vertex :alle ubrigen Eckpunkte



start

end

split

merge

regular

Beispiel 3.2: die 5 Eckpunkttypen



Grundidee des Algorithmus:

Ein einfaches Polygon ist x-monoton, falls es weder split- nochmerge-vertices besitzt.

Eliminiere also jeden split- oder merge-vertex durch Einfugen einergeeigneten Diagonale.

Dadurch zerfallt das Polygon in zwei Teilpolygone. In beidenTeilpolygonen ist der ursprungliche split- oder merge-vertex keinsplit- oder merge-vertex mehr.



Einfugen von Diagonalen bei split-vertices:

Die scan-line erreiche nun einen split-vertex vi. Wir versuchen anvi eine Diagonale so einzufugen, dass ihr anderer Endpunkt einEckpunkt links von vi ist.

Die scan-line schneidet das Polygon an zwei Seiten ek, ej

unmittelbar oberhalb bzw. unterhalb von vi.



Definition

helper(ej):derjenige Eckpunkt in der priority-queue (d.h. links von derscan-line) mit maximaler x-Koordinate, dessen Lot auf die Seite ej

vollstandig im Inneren des Polygons liegt

Schließlich muss man nur noch die Diagonale zwischen vi undhelper(ej) einsetzen, um vi zu eliminieren.



vi

ej

ekhelper(ej)

Beispiel 3.3: neue Diagonale bei einem split-vertex



Einfugen von Diagonalen bei merge-vertices:

Der Endpunkt der Diagonale, die wir an einem merge-vertex vi

einsetzen, muss rechts von vi liegen. Wir wahlen ihn so, dass seinex-Koordinate minimal ist.

Problem:Wenn die scan-line vi erreicht, sind die Eckpunkte rechts von vi

noch unbekannt.



Das Problem ist jedoch leichter, als es dem ersten Anschein nachist:

Die scan-line schneidet das Polygon wiederum an zwei Seitenek, ej unmittelbar oberhalb bzw. unterhalb von vi und vi istzudem der aktuelle helper(ej).

Die scan-line schreitet weiter nach rechts. Sobald ein neuerhelper(ej) gefunden wird, ist dieser der gesuchte rechte Endpunktfur die neue Diagonale.



Falls kein neuer helper(ej) gefunden wird, so verbinde vi mit demrechten Endpunkt von helper(ej).

Jedesmal, wenn der helper einer Seite aktualisiert wird, uberprufenwir, ob der alte helper ein merge-vertex war. Falls ja, wird dieVerbindungsdiagonale eingesetzt.



Beispiel 3.4: vollstandige Zerlegung in x-monotone Teilpolygone



Zur Korrektheit:

Das Eliminieren von split- und merge-vertices durch Hinzufugenvon Diagonalen liefert nur x-monotone Teilpolygone.

Die helper-Eigenschaft wird benutzt, damit sich die Diagonalennicht schneiden.



Zur Laufzeit:

Priority-queue-Operationen:

O(log(n))

notige Anzahl an priority-queue-Operationen:

O(n)

Damit ergibt sich die Gesamtlaufzeit:

O(n ∗ log(n))



3.2 Triangulierung monotoner Polygone

Wir betrachten nun ein x-monotones Polygon.

Es seien Pl und Pr wiederum die beiden Eckpunkte, die amweitesten links bzw. rechts liegen.

Es besitzt auch eine obere und untere Kette, die beide bei Pl

beginnen und bei Pr enden.



Wir stellen fest:

Da das Polygon keine split- oder merge-vertices besitzt, sind dieKetten geordnet:

Eckpunkte auf den Ketten haben stets kleinere x-Koordinaten alsihre Nachfolger in den Ketten, wenn man von links nach rechtswandert.



Definition

monotoner Berg :x-monotones Polygon, dessen obere oder untere Kette nur aus denEckpunkten Pl und Pr besteht

Definition

monotoner Streifen:x-monotones Polygon, dessen Eckpunkte abwechselnd zur oberenoder unteren Kette gehoren, wenn man sie nach der Große ihrerx-Koordinaten ordnet



Beispiel 3.5: monotone Berge

Beispiel 3.6: monotoner Streifen, trianguliert



Monotone Berge kann man auf diese Weise triangulieren:

Bestimme zunachst alle konvexen Eckpunkte in der langeren Ketteund speichere sie in einem Stapel L.

Jeder dieser konvexen Eckpunkte ist schon automatisch einmittlerer Punkt eines Ohres.

Entferne den obersten Eckpunkt Pi aus dem Stapel und fuge diezu seinem Ohr gehorende Diagonale ein.

Aktualisiere entsprechend die Innenwinkel des linken und rechtenNachbarpunktes von Pi.



Falls einer oder beide Nachbarpunkte nun konvex sind und sienicht mit Pl oder Pr ubereinstimmen, lege sie auf dem Stapel ab.

Wiederhole diese Prozedur so lange, bis der Stapel leer ist.



0

P1

P2

P3

P4

1

P1

P2

P3

2

P1

P23

P1



4

P1

5

P1

6

Beispiel 3.7: Triangulierung eines monotonen Berges



Zur Korrektheit:

Die Verbindungsstrecke vom linken und rechten Nachbarn eineskonvexen Eckpunkts in der langeren Kette eines monotonen Bergesist eine Diagonale.

Jeder monotone Berg besitzt in der langeren Kette mindestenseinen konvexen Eckpunkt.

Jedes Restpolygon ist auch ein monotoner Berg und besitzt somitauch mindestens einen konvexen Eckpunkt in seiner langeren Kette.

In jeder Iteration wird demnach genau ein Ohr abgeschnitten.



Zur Laufzeit:

Hochstens n− 2 Eckpunkte befinden sich im Stapel.

Initialisierung, d.h. prufen jedes Eckpunktes auf Konvexitat undbelegen des Stapels:

O(n)

Entfernen eines Punktes und Einfugen der Diagonale:

O(1)

Gesamtlaufzeit (d.h. Initialisierung plus Zeit, bis der Stapel leerist):

O(n)

Der Algorithmus besitzt also lineare Laufzeit.



Die Triangulierung eines monotonen Streifens ist trivial:

Verbinde aufsteigend nach der x-Koordinate abwechselnd dieEckpunkte aus der oberen und unteren Kette mit Diagonalen.

Dieser Algorithmus ist offensichtlich korrekt und hat lineareLaufzeit.



Nun zu beliebigen monotonen Polygonen:

Jedes monotone Polygon lasst sich in monotone Berge und Streifenzerlegen.

Diese sind in Linearzeit triangulierbar. Man kann mit Hilfe dieserZerlegung beliebige monotone Polygone in linearer Laufzeittriangulieren!



Beispiel 3.8: Zerlegung eines monotonen Polygons in Berge und Streifen



Initialisiere einen Stapel mit dem Eckpunkt Pl.

Verwende ferner die beiden Zahlvariablen UpCntr und DownCntrvom Typ Integer, die mit dem Wert 0 initialisiert werden.

Wandere gleichzeitig auf der oberen und unteren Kette von linksnach rechts.

Im Folgenden lege jeweils denjenigen nachsten Eckpunkt aus deroberen oder unteren Kette auf den Stapel, welcher die kleinerex-Koordinate hat.



Ist dieser aus der oberen Kette, so erhohe UpCntr um 1 und setzeDownCntr gleich Null, andernfalls erhohe DownCntr um 1 undsetze UpCntr gleich Null

Bevor UpCntr oder DownCntr gleich Null gesetzt werden, konnenfolgende drei Falle auftauchen:

1. UpCntr bzw. DownCntr = 0 (Initialisierung)

2. UpCntr bzw. DownCntr = 1

3. UpCntr bzw. DownCntr > 1



1. Fall:Nichts zu tun.

2. Fall:Die Verbindungsstrecke vom aktuellen Punkt und dem oberstenPunkt auf dem Stapel ist eine Diagonale, die zu einemmonotonen Streifen gehort. Fuge diese ein und ersetze denobersten Punkt auf dem Stapel mit dem aktuellen.

3. Fall:Der aktuelle Punkt ist der rechte Endpunkt Pr eines monotonenBerges, der aus den Punkten im Stapel besteht. Triangulierediesen und leere anschließend den Stapel, bevor dort der aktuellePunkt abgelegt wird.



Zur Korrektheit:

Es ist klar, dass die monotonen Streifen direkt trianguliert werden.

Der Algorithmus fur die monotonen Berge ist korrekt, somit ist dieTriangulierung jedes Teilberges ein korrekter Schritt.



Zur Laufzeit:

Da die monotonen Streifen direkt trianguliert werden, ist dieTriangulation aller Streifen insgesamt beschrankt durch:

O(n)

Das Polygon besitze j ∈ N Teilberge. Die Teilberge besitzenn1, ...,nj ∈ N Eckpunkte. Es gilt auf jeden Fall:

∑jk=1 nk < 2n

Laufzeit zur Triangulierung aller Berge:∑jk=1 O(nk) = O(n)

Gesamtlaufzeit:

O(n)

Linear!



Quellenangabe

M. de Berg, O. Cheong, M. van Krefeld, M. Overmars:Computational Geometry, Algorithms and Applications, p. 45 - 60

http://valis.cs.uiuc.edu/~sariel/teach/2004/b/webpage/lec/24_triang_II.pdf

Documents

Triangulierung von einfachen Polygonen - zaik.uni-koeln.de · i konvex ist und bei der das Dreieck 4P i 1P iP i+1 keinen von den ub rigen Eckpunkten enth alt (Entsprechendes de nieren