Laufrichtung von Polygonen errechnen

[Whiz-zarD]

Hallo,

Ich schreib ein kleines Programm, was den Weiler-Atherton-Clipping-Algorithmus erläutert.
In diesem Programm kann der Benutzer selbst die Polygone erstellen, die bearbeitet werden sollen.
Dieser Algorithmus und die Triangulierung von Polygonen benötigen die Laufrichtung der Eckpunkte.
Ich hab bis jetzt nur ein Weg gefunden, wie man die Laufrichtung von konvexe Polygone errechnet, aber nicht für konkave Polygone. Und zwar, dass eine Gerade zwischen zwei Punkte berechnet wird und geschaut wird, wo der dritte Punkt liegt. Dies klappt aber, wie gesagt, nur für konvexe Polygone.

Nun ist meine Frage, ob da jemand eine Idee hat? Oder welche Praktiken kommen da zum Einsatz?

Ich hab da schon unter Google gesucht, aber bis jetzt nur Ideen gefunden, wie man sowas realisieren kann, die aber letzendlich zu keinem Ergebnis geführt haben.

mfg
Whiz-zarD

[nudelsalat]

Das beste was mir einfällt wär, den Normalvektor des Polygons zu berechnen und zu schaun ob der z-Wert negativ oder positiv ist. Eins von beiden bedeutet immer, dass es gegen den Uhrzeigersinn gerichtet ist und das andere, dass es im Uhrzeigersinn gerichtet ist. Mit Newells Method kann man sich scheinbar die Normale von concaven Polygonen berechnen: http://www.opengl.org/wiki/Calculating_a_Surface_Normal

[Whiz-zarD]

Schon mal Danke für den Link.
Vielleicht hätte ich noch erwähnen sollen, dass ich mich mit Zwei-Dimensionalen Raum bewege und nicht im Drei-Dimensionalen Raum und dementsprechend eigentlich keine Z-Koordinate besitze.
Wie würde es sich dann mit der Z-Achse verhalten? Würde diese Methode dennoch funktionieren, wenn ich z mit 1 definiere? ... mmh, müsste ich mal in den nächsten Tagen testen.

[nudelsalat]

Das macht nichts, du setzt z für jeden Eckpunkt einfach auf 0. ( bei Dreiecken könntest du den Eckpunkten sogar beliebige und auch unterschiedliche z-Werte geben, das Vorzeichen vom z-Wert der Normale wird gleich bleiben. Nur der Betrag ändert sich. Ich weiß aber nicht ob das auch für größere bzw. konkave Polygone gilt. )

[Papa Justify]

http://users.informatik.uni-halle.de/~schenzel/ss07/Uebung-D/vorlesung.pdf

http://www.amazon.de/Algorithmische-Geometrie-Grundlagen-Anwendungen-eXamen-Press/dp/3540209565/ref=sr_1_1?ie=UTF8&qid=1306578056&sr=8-1

Desweiteren: Definiere bitte "Laufrichtung"!

[Whiz-zarD]

Desweiteren: Definiere bitte "Laufrichtung"!

In welche Richtung die Punkte angeordnet sind. Im oder gegen den Uhrzeigersinn.

[Whiz-zarD]

Das macht nichts, du setzt z für jeden Eckpunkt einfach auf 0. ( bei Dreiecken könntest du den Eckpunkten sogar beliebige und auch unterschiedliche z-Werte geben, das Vorzeichen vom z-Wert der Normale wird gleich bleiben. Nur der Betrag ändert sich. Ich weiß aber nicht ob das auch für größere bzw. konkave Polygone gilt. )

Danke.
Dieser Algorithmus scheint tatsächlich zu funktionieren :)