Durchlaufrichtung eines Polygons erkennen

[Nikolas]

Hallo

Ich habe ein neues PolygonProblem:

Nach ein paar Schritten habe ich eine Liste an Eckpunkten meines Polygons wobei der letzte Punkt mit dem ersten Übereinstimmt.
Da ich später noch Fourierdeskriptoren dieser Polygon berechnen will, muss ich wissen, in welcher Richtung das Polygon durchlaufen wird.
Bei einem Kreis wäre das ja noch recht einfach, da ich aber beliebig geformte Polygone (keine Löcher aber konkav) betrachten will stoße ich auf ein Problem.
Wenn ich z.B. ein Polygon habe, das wie eine Swastika aussieht, gibt es häufig Teilstrecken, die gegen die eigentlich Richtung durchlaufen werden.
Da ich ein möglichst robustes System bauen will, würde ich auch gerne solche Fälle abdecken.

Hat da jemand eine Idee/Algorithmus?

Nikolas

// das ist FolgeThread, damit der hier nicht zu viele unterschiedliche Probleme beinhaltet.

[Medium]

Hello again

So aus dem Bauch heraus:
Ermittle die Winkel zwischen jeweils 2 Geraden, die durch zwei benachbarte Punkte, und einem definierten Fixpunkt laufen. Addiere dies für alle Nachbarpaare, und du solltest am Ende auf +/- 2*Pi kommen. Das Vorzeichen müsste ein Indikator für die Orientierung sein. (Mit ArcTan2 berechnen, um Vorzeichenbehaftete Winkel zu erhalten.)

Ein anderer Weg könnte es sein, wenn du eine Normale zu dem Polygon berechnest, allerdings weiss ich gerade nicht, ob und wie schnell sich das für Polygone mit mehr als 3 Eckpunkten machen lässt (Koplanar sind sie ja immerhin auf jeden Fall). Das Vorzeichen der Normale ist dann wieder ein Indikator.

[Corpsman]

@medium

was er im 1. schritt macht ist die Summe aller winkel im Vieleck das müste dann (n-2)*180 in Winkelgraden geben. Ich denke nicht das er da auf irgend einen Drehsinn kommt.

für eher Brauchbar halte ich die Variante mit dem Mittelpunkt und der aussenseit.

Also du suchst dir einen Definierten Punkt innerhalb des Polygons. bildest dann immer normalen 2er vertices. Verglichen mit den Richtungen vom Mittelpunkt müste sich da evtl eine aussage treffen lassen ...

[Apollonius]

Du könntest auch an jedem Punkt den Winkel zwischen den Strecken bestimmen (immer von der vorhergehenden zur nächsten), das ergibt dann im n-Eck entweder (n+2)*Pi (falls es gegen Uhrzeigersinn durchlaufen wird) oder (n-2)*Pi (falls es im den Uhrzeigersinn durchlaufen wird).

Edit: Ich lese gerade zufällig von der Gaußschen Trapezformel - damit kommst du ohne Winkelberechnungen aus, du musst nur das Vorzeichen der Fläche betrachten.

[Nikolas]

Ich hatte gerade ein kleine Idee:

(in Java habe ich gerade eine Polygon klasse gefunden, die einen contains-Befehl kennt)

Jetzt habe ich zwei nebeneinander liegende Pixel mit dem gleichen x-Wert gesucht und mit einen weiteren Punkt definiert, der über dem ersten Punkt liegt:

Code:

   a
___xy__        /// a liegt über x

Genau dann, wenn a im Polygon liegt, wird es positiv umlaufen. Damit kann ich mich um Winkel und Geradenrechnung rumdrücken...

Danke für eure Vorschläge, noch läuft meine Idee nicht, mal schauen


// Die Trapezformal sieht stark aus. Wenn es mit meiner Idee nicht funktioniert, werde ich die wohl umsetzen.

[Corpsman]

Vergiss nicht deine Ergebnisse zu posten, die könnten durchaus interessant sein. So zwecks OpenGL und FaceCulling ...

[Nikolas]

Ein erstes Ergebnis ist das Bild im Anhang.
Die Objekte sind aus Pappe. Die grünen Konturen sind eine Approximation über ein paar (wenige) Fourierkoeffizienten, die roten
sind die passenden Fourierdeskriptoren.
Wenn alles funktioniert, sollen die roten Konturen für gleiche Objekte (die sich nur über Drehung und Position unterscheiden, gleich ausgerichtet sein.

[Medium]

Zitat von Corpsman:

@medium

Nunja, deswegen hatte ich dazu geschrieben, dass ArcTan2 ganz hilfreich ist, da dann nicht einfach alle Winkel, sondern alle orientierten Winkel addiert werden. Macht man das in der Reihenfolge der Punktliste, und nimmt den Sprung letzter/erster Index mit, dürfte mMn nichts anderes als +/- 2Pi herauskommen dürfen. Der Referenzpunkt muss dabei imho nichtmal Mittel-/Schwerpunkt sein, sondern beliebig aber konstant.

Zitat von Corpsman:

Also du suchst dir einen Definierten Punkt innerhalb des Polygons. bildest dann immer normalen 2er vertices. Verglichen mit den Richtungen vom Mittelpunkt müste sich da evtl eine aussage treffen lassen ...

Glaube ich nicht, weil du durchaus das Pech haben kannst ein "rückläufiges" Vertexpaar zu erwischen. Man kann das zwar herausfinden, weil die Geraden in diesem Fall die Kontur ungeradzahlig oft schneiden müssen, aber effizient ist das nicht mehr

Die "A über X" Variante klingt spaßig. Was macht man aber, wenn es keine 2 Punkte mit gleichem X-Wert gibt? Hier wäre es denke ich interessanter herauszufinden welches Prinzip dahinter steckt - evtl. lässt sich das ja allgemeiner implementieren!

Edit: Das Bild tuts bei mir nicht

[CK_CK]

Das Bild ist eine jpg-2000 Datei...

Umbenennen in .jp2 und mit Firefox tut's

[Nikolas]

Meine Idee ist natürlich Unsinn. Man nehme einen Kreis. Wenn ich das Verfahren oben starte, habe ich ein anderes Ergebnis, als wenn ich es unten ansetze.

Also doch der Gaußansatz.