AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Programmieren allgemein Durchlaufrichtung eines Polygons erkennen

Durchlaufrichtung eines Polygons erkennen

Ein Thema von Nikolas · begonnen am 19. Jun 2008 · letzter Beitrag vom 20. Jun 2008
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#1

Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 18:07
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.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.596 Beiträge
 
Delphi 2007 Enterprise
 
#2

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 18:45
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.
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von Corpsman
Corpsman

Registriert seit: 8. Nov 2005
Ort: nähe Stuttgart
981 Beiträge
 
Delphi XE2 Professional
 
#3

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 18:50
@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 ...
Uwe
My Sitewww.Corpsman.de

My marble madness clone Balanced ( ca. 70,0 mb ) aktuell ver 2.01
  Mit Zitat antworten Zitat
Apollonius

Registriert seit: 16. Apr 2007
2.325 Beiträge
 
Turbo Delphi für Win32
 
#4

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 18:54
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.
Wer erweist der Welt einen Dienst und findet ein gutes Synonym für "Pointer"?
"An interface pointer is a pointer to a pointer. This pointer points to an array of pointers, each of which points to an interface function."
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#5

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 19:05
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.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Benutzerbild von Corpsman
Corpsman

Registriert seit: 8. Nov 2005
Ort: nähe Stuttgart
981 Beiträge
 
Delphi XE2 Professional
 
#6

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 19:13
Vergiss nicht deine Ergebnisse zu posten, die könnten durchaus interessant sein. So zwecks OpenGL und FaceCulling ...
Uwe
My Sitewww.Corpsman.de

My marble madness clone Balanced ( ca. 70,0 mb ) aktuell ver 2.01
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#7

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 19:17
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.
Angehängte Grafiken
Dateityp: jpg bild_1_190.jpg (64,5 KB, 40x aufgerufen)
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Medium

Registriert seit: 23. Jan 2008
3.596 Beiträge
 
Delphi 2007 Enterprise
 
#8

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 19:24
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
"When one person suffers from a delusion, it is called insanity. When a million people suffer from a delusion, it is called religion." (Richard Dawkins)
  Mit Zitat antworten Zitat
Benutzerbild von CK_CK
CK_CK

Registriert seit: 30. Aug 2005
Ort: Dortmund, Germany
388 Beiträge
 
Delphi 2006 Enterprise
 
#9

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 19:32
Das Bild ist eine jpg-2000 Datei...

Umbenennen in .jp2 und mit Firefox tut's
Chris
» «
Mehr von mir (Programme, etc.): http://www.kroegerama.de
  Mit Zitat antworten Zitat
Benutzerbild von Nikolas
Nikolas

Registriert seit: 28. Jul 2003
1.528 Beiträge
 
Delphi 2005 Personal
 
#10

Re: Durchlaufrichtung eines Polygons erkennen

  Alt 19. Jun 2008, 19:33
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.
Erwarte das Beste und bereite dich auf das Schlimmste vor.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 05:54 Uhr.
Powered by vBulletin® Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2020 by Daniel R. Wolf