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 :lol:


// 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:

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:

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.

[Medium]

Mal so am Rande: Wie wirkt sich eine Orientierungsvertauschung überhaupt in Fourierdeskriptoren aus? Nicht, dass wir hier viel zu viel machen, und nachher ists da einfach durch Vorzeihen/Phasenverschiebung/Spiegelung erkennbar :). Lage und Drehung sind ja egal dabei, nur an die Wirkung der Orientierung kann ich mich nicht mehr erinnern.

@Jpeg2000: Das erklärt einiges, thx :)

[Nikolas]

Da bin ich mir ehrlich gesagt nicht sicher, da ich keine Werte habe, um meinen Algorithmus für die Deskriptoren zu testen.
Im Anhang noch mal ein einfacheres Bild. Grün die Koeffizienten, Rot die Deskriptoren. Die dicken Linien markieren die Laufrichtung, der Gaussalgorithmus funktioniert jedenfalls schon mal bei diesen beiden.


Danke für eure Hilfe (besonders an das Medium)

Im Anhang gibt's ein neues Beispiel, rot die Deskriptoren, die doch sehr schön aussehen.
Der Code ist in Java, falls jemand Lust hat, ein paar der Funktionen nach Delphi zu portieren, werde ich den Code hier veröffentlichen.

[Medium]

Ich meinte eher, dass du mal versuchen könntest Koeffizienten/Deskriptoren für ein und die selbe Kontur, ein Mal im und ein Mal gegen den Uhrzeigersinn. Wenn man die Deskriptoren dann vergleicht, ist der Unterschied evtl. sehr laufzeiteffizient zu ermitteln, so dass du damit ganz einfach gleiche Konturen erkennen kannst, die sich in ihrer Orientierung unterscheiden. Im Grunde ist es ja eine Spiegelung.

Und nicht lage fragen, ob der Code interessant wäre! Das ist seit längerem mal wieder ein echt interessantes Thema in der DP (:love: Geometrie/LA), und ich würde mich gerne mal daran versuchen das zu portieren.

[Nikolas]

Das kann ich mal machen.
Nur leider habe ich noch Fehler drin. Beim final.JPG sind manche Konturen schon sehr schön. (z.B. die ganz rechts und ganz oben), die unterste und rechts oben sind aber noch gegeneinander verdreht.

Auch weiss ich nicht genau, wie ich die Deskriptoren vergleichen soll. Mein erster Ansatz ist einfach die Differenz für jeden Deskriptor zu nehmen und dann über die Beträge zu summieren. Da liegen bei dem gegebenen Bild aber alle Differenzen zwischen 0.3 und 2 (c_5,...,c_5 benutzt), wodurch eine Klassifikation recht schwierig wird. Auch wenn ich mehr (100) Koeffizienten benutze, werden die Werte nicht besser.

Wenn ich einen sauberen Klassifikator habe, werde ich den Code mal hochladen. Die Portierung dürfte nicht allzu schwierig sein, ich benutze jedoch eine Klasse für Komplexe Zahlen, da müsstest du mal schauen, wo du sowas schönes für Delphi findest.

[Medium]

Eine Lib für komplexe Zahlen hab ich schon länger fertig rumliegen, die sollte sich ja anpassen lassen.

Was die Bestimmung von Ähnlichkeit angeht, so könnte evtl. Folie 16 dieser Powerpoint Präsentation hilfreich sein.