Mathe: Drehrichtung von Polygonen

Übersicht

Sonstiges

Smalltalk

	Goodjee Betreff: Mathe: Drehrichtung von Polygonen	Do, März 24, 2011 14:29 Antworten mit Zitat
guten morgen allerseits. ich habe nen algorithmus geschrieben, der konkave polygone in dreiecke zerlegt. allerdings funktioniert das ganze nur wenn die eingegeben eckpunkte gegen den uhrzeigersinn sortiert sind. ich brauche also einen test, ob das polygon gegen oder im uhrzeigersinn sortiert ist um es gegebenenfalls umzudrehen. Bei konvexen Polygonen reicht es ja sich ein Dreieck anzugucken, aber für konkave polygone habe ich noch keinen ansatz gefunden. ich bin dankbar für lösungsvorschläge =) schönen tag noch
"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House http://deeebian.redio.de/ http://goodjee.redio.de/

Goodjee

Betreff: Mathe: Drehrichtung von Polygonen

Do, März 24, 2011 14:29
Antworten mit Zitat

guten morgen allerseits.
ich habe nen algorithmus geschrieben, der konkave polygone in dreiecke zerlegt. allerdings funktioniert das ganze nur wenn die eingegeben eckpunkte gegen den uhrzeigersinn sortiert sind.
ich brauche also einen test, ob das polygon gegen oder im uhrzeigersinn sortiert ist um es gegebenenfalls umzudrehen.

Bei konvexen Polygonen reicht es ja sich ein Dreieck anzugucken, aber für konkave polygone habe ich noch keinen ansatz gefunden.
ich bin dankbar für lösungsvorschläge =)

schönen tag noch

"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House
http://deeebian.redio.de/ http://goodjee.redio.de/

	darth	Do, März 24, 2011 16:34 Antworten mit Zitat
Hallo, ich gehe einfach mal davon aus, dass du vom 2D-Raum redest. In 3D wird das Problem unheimlich viel komplizierter.. Ich benutze dafür meist folgende Funktion: BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Function isCCW(p1.TVector2D, p2.TVector2D, p3.TVector2D) Return (p2\x-p1\x)(p3\y-p1\y)-(p2\y-p1\y)(p3\x-p1\x) End Function Die gibt an, ob drei Punkte einen Winkel im Gegenuhrzeigersinn bilden (>0) oder im UZS (<0). Jetzt musst du eigentlich nur für das ganze Polygon durchgehen und die Punkte testen.. Code: [AUSKLAPPEN] [EINKLAPPEN] For i = 0 To pointCount -1 ;Ang. Punkte sind 0, 1, 2, .., pC-1 gespeichert If isCCW(point[i], point[(i+1) mod pointCount], point[(i+2) mod pointCount]) < 0 notCCW = true EndIf Next So in etwa. Sollte dann ein notCCW rauskommen, müsstest du einfach die Punkte "umdrehen" (also max -> 0, max-1 -> 1 usw..). Hoffentlich war es sowas, das du gesucht hast. MfG, Darth
Diese Signatur ist leer.

darth

Do, März 24, 2011 16:34
Antworten mit Zitat

Hallo,

ich gehe einfach mal davon aus, dass du vom 2D-Raum redest. In 3D wird das Problem unheimlich viel komplizierter..

Ich benutze dafür meist folgende Funktion:

BlitzBasic: [AUSKLAPPEN]

Function isCCW(p1.TVector2D, p2.TVector2D, p3.TVector2D)
	Return (p2\x-p1\x)*(p3\y-p1\y)-(p2\y-p1\y)*(p3\x-p1\x)
End Function

Die gibt an, ob drei Punkte einen Winkel im Gegenuhrzeigersinn bilden (>0) oder im UZS (<0).
Jetzt musst du eigentlich nur für das ganze Polygon durchgehen und die Punkte testen..

Code: [AUSKLAPPEN]

For i = 0 To pointCount -1 ;Ang. Punkte sind 0, 1, 2, .., pC-1 gespeichert
If isCCW(point[i], point[(i+1) mod pointCount], point[(i+2) mod pointCount]) < 0
notCCW = true
EndIf
Next

So in etwa. Sollte dann ein notCCW rauskommen, müsstest du einfach die Punkte "umdrehen" (also max -> 0, max-1 -> 1 usw..). Hoffentlich war es sowas, das du gesucht hast.

MfG,
Darth

Diese Signatur ist leer.

	Goodjee	Do, März 24, 2011 19:05 Antworten mit Zitat
aber das geht doch jetzt nur in konvexen polygonen, in konkaven müsste es doch dreiecke mit beiden drehrichtungen geben?
"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House http://deeebian.redio.de/ http://goodjee.redio.de/

Goodjee

Do, März 24, 2011 19:05
Antworten mit Zitat

aber das geht doch jetzt nur in konvexen polygonen, in konkaven müsste es doch dreiecke mit beiden drehrichtungen geben?

"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House
http://deeebian.redio.de/ http://goodjee.redio.de/

	mpmxyz	Do, März 24, 2011 19:34 Antworten mit Zitat
Edit2 Ich habe zumindest einen eher langsamen Algorithmus gefunden: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Type TVector Field x:Double,y:Double Function Create:TVector(x:Double,y:Double) Local newV:TVector=New TVector newV.x=x newV.y=y Return newV EndFunction EndType Local points:TVector[]=[ TVector.Create(0,0),.. TVector.Create(1,0),.. TVector.Create(1,1),.. TVector.Create(0,1)] '---Anfang des Algorithmus--- Local angle:Double For Local i:Int=0 Until points.length Local p1:TVector = points[i] Local p2:TVector = points[(i+1) Mod points.length] Local p3:TVector = points[(i+2) Mod points.length] Local crossValue:Double = (p2.x-p1.x)(p3.y-p2.y) - (p2.y-p1.y)(p3.x-p2.x) '(p2-p1)x(p3-p2) [z] Local dotValue:Double = (p2.x-p1.x)(p3.x-p2.x) + (p2.y-p1.y)(p3.y-p2.y) Local squareLengthFactor:Double = ((p2.x-p1.x)(p2.x-p1.x)+(p2.y-p1.y)(p2.y-p1.y)) * ((p3.x-p2.x)(p3.x-p2.x)+(p3.y-p2.y)(p3.y-p2.y)) Local tmpAngle:Double = ASin(crossValue/Sqr(squareLengthFactor)) 'Länge -> Sin(winkel) DebugLog tmpAngle If dotValue<0.0 'Winkel>90° -> Sin(x)=Sin(180-x) tmpAngle = (Sgn(tmpAngle)*180.0-tmpAngle) EndIf angle:+tmpAngle Next If angle>0 'gegen den Uhrzeigersinn im 'normalen' Koordinatensystem Else 'im Uhrzeigersinn im 'normalen' Koordinatensystem EndIf '---Ende des Algorithmus--- Print angle '+-360 bei einfachen Umrundungen mfG mpmxyz

mpmxyz

Do, März 24, 2011 19:34
Antworten mit Zitat

*Edit2*
Ich habe zumindest einen eher langsamen Algorithmus gefunden:
BlitzMax: [AUSKLAPPEN]

SuperStrict
Type TVector
	Field x:Double,y:Double
	Function Create:TVector(x:Double,y:Double)
		Local newV:TVector=New TVector
		newV.x=x
		newV.y=y
		Return newV
	EndFunction
EndType


Local points:TVector[]=[	TVector.Create(0,0),..
					TVector.Create(1,0),..
					TVector.Create(1,1),..
					TVector.Create(0,1)]
'---Anfang des Algorithmus---
Local angle:Double
For Local i:Int=0 Until points.length
	Local p1:TVector = points[i]
	Local p2:TVector = points[(i+1) Mod points.length]
	Local p3:TVector = points[(i+2) Mod points.length]
	Local crossValue:Double = (p2.x-p1.x)*(p3.y-p2.y) - (p2.y-p1.y)*(p3.x-p2.x) '(p2-p1)x(p3-p2) [z]
	Local dotValue:Double = (p2.x-p1.x)*(p3.x-p2.x) + (p2.y-p1.y)*(p3.y-p2.y)
	Local squareLengthFactor:Double = ((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y)) * ((p3.x-p2.x)*(p3.x-p2.x)+(p3.y-p2.y)*(p3.y-p2.y))
	Local tmpAngle:Double = ASin(crossValue/Sqr(squareLengthFactor)) 'Länge -> Sin(winkel)
	DebugLog tmpAngle
	If dotValue<0.0 'Winkel>90° -> Sin(x)=Sin(180-x)
		tmpAngle = (Sgn(tmpAngle)*180.0-tmpAngle)
	EndIf
	angle:+tmpAngle
Next
If angle>0
	'gegen den Uhrzeigersinn im 'normalen' Koordinatensystem
Else
	'im Uhrzeigersinn im 'normalen' Koordinatensystem
EndIf
'---Ende des Algorithmus---

Print angle '+-360 bei einfachen Umrundungen

mfG
mpmxyz

Zuletzt bearbeitet von mpmxyz am Do, März 24, 2011 20:19, insgesamt einmal bearbeitet

	Lunatix	Do, März 24, 2011 19:40 Antworten mit Zitat
Das geht eigentlich, ob 2D oder 3D, ganz einfach über die Normale. Wenn du eine 2D Anwendung hast, lässt du die Z-Achse einfach immer auf 0.0 =) Ein Beispiel: Code: [AUSKLAPPEN] [EINKLAPPEN] v0.x = 5; v1.x = 8; v2.x = 14; v0.y = 5; v1.y = 10; v2.y = 6; v0.z = 5; v1.z = 0; v2.z = 0; Gespeichert sind die Punkte als Triangles: v0, v1, v2... oder auch v2,v1,v0... oder v1,v0,v2... etc. Nun errechnet man die "Edges" (Kanten): Code: [AUSKLAPPEN] [EINKLAPPEN] Edge0 = v1 - v2 = -6,4,0 Edge1 = v1 - v0 = 3,5,0 Und aus den Edges errechnet sich über das Kreuzprodukt die Normale: Code: [AUSKLAPPEN] [EINKLAPPEN] Normal = Edge0 . Edge1 = 0,0,-42 Hier sieht man, das die Normale Negativ ist. Dreht man die Reihenfolge um (v2,v1,v0) kommt als Endergebnis "0,0,42" heraus - die Normale ist Positiv. Nun kannst du bestimmen, welche Polygone zu drehen sind und welche nicht! Vektor Addition/Subtraktion/Multiplikation/Dividierung: Code: [AUSKLAPPEN] [EINKLAPPEN] e1.x = v1.x +-/* v2.x e1.y = v1.y +-/* v2.y e1.z = v1.z +-/* v2.z Das Kreuzprodukt errechnet sich wie folgt: Code: [AUSKLAPPEN] [EINKLAPPEN] e1.y * e2.z - e1.z * e2.y e1.z * e2.x - e1.x * e2.z e1.x * e2.y - e1.y * e2.x
[size=9]Pro\|gram\|mier\|er: Ein Organismus, der Koffein in Software umwandelt. Geben Sie eine beliebige 11-stellige Primzahl ein, um fortzusetzen...

Lunatix

Do, März 24, 2011 19:40
Antworten mit Zitat

Das geht eigentlich, ob 2D oder 3D, ganz einfach über die Normale.

Wenn du eine 2D Anwendung hast, lässt du die Z-Achse einfach immer auf 0.0 =)
Ein Beispiel:

Code: [AUSKLAPPEN]

v0.x = 5; v1.x = 8; v2.x = 14;
v0.y = 5; v1.y = 10; v2.y = 6;
v0.z = 5; v1.z = 0; v2.z = 0;

Gespeichert sind die Punkte als Triangles: v0, v1, v2... oder auch v2,v1,v0... oder v1,v0,v2... etc.

Nun errechnet man die "Edges" (Kanten):

Code: [AUSKLAPPEN]

Edge0 = v1 - v2 = -6,4,0
Edge1 = v1 - v0 = 3,5,0

Und aus den Edges errechnet sich über das Kreuzprodukt die Normale:
Code: [AUSKLAPPEN]

Normal = Edge0 . Edge1 = 0,0,-42

Hier sieht man, das die Normale Negativ ist. Dreht man die Reihenfolge um (v2,v1,v0) kommt als Endergebnis "0,0,42" heraus - die Normale ist Positiv. Nun kannst du bestimmen, welche Polygone zu drehen sind und welche nicht!

Vektor Addition/Subtraktion/Multiplikation/Dividierung:
Code: [AUSKLAPPEN]

e1.x = v1.x +-/* v2.x
e1.y = v1.y +-/* v2.y
e1.z = v1.z +-/* v2.z

Das Kreuzprodukt errechnet sich wie folgt:
Code: [AUSKLAPPEN]

e1.y * e2.z - e1.z * e2.y
e1.z * e2.x - e1.x * e2.z
e1.x * e2.y - e1.y * e2.x

[size=9]Pro|gram|mier|er: Ein Organismus, der Koffein in Software umwandelt.
Geben Sie eine beliebige 11-stellige Primzahl ein, um fortzusetzen...

	Goodjee	Do, März 24, 2011 20:02 Antworten mit Zitat
auch deine antwort hilft leider nicht weiter, denn du hast wieder nur ein dreieck oder ein konvexes polygon. in einem konkaven polygon findest du leider sowohl negative als auch positive kreuzprodukte. beispiel: das dreieck aus 3 aufeinander folgenden eckpunkten mit der gelben kante hat ne andere drehrichtung als das mit der grünen. Edit: ich bin mir noch nicht ganz sicher ob folgendes funktioniert, aber erste tests scheinen vielversprechend: Code: [AUSKLAPPEN] [EINKLAPPEN] bool polygonClockwise(vector<Vector>& polygon) { float total=0; for(int i=0;i<polygon.size();i++) { Vector a=polygon[(i+1)%polygon.size()]-polygon[i]; Vector b=polygon[(i+2)%polygon.size()]-polygon[(i+1)%polygon.size()]; a=!a; //normalvektor total+=(a*b); //skalarprodukt } printf("TOTAL: %f\n",total); return (total>0); }
"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House http://deeebian.redio.de/ http://goodjee.redio.de/

Goodjee

Do, März 24, 2011 20:02
Antworten mit Zitat

auch deine antwort hilft leider nicht weiter, denn du hast wieder nur ein dreieck oder ein konvexes polygon.
in einem konkaven polygon findest du leider sowohl negative als auch positive kreuzprodukte.

beispiel:
user posted image

das dreieck aus 3 aufeinander folgenden eckpunkten mit der gelben kante hat ne andere drehrichtung als das mit der grünen.

Edit: ich bin mir noch nicht ganz sicher ob folgendes funktioniert, aber erste tests scheinen vielversprechend:
Code: [AUSKLAPPEN]

bool polygonClockwise(vector<Vector>& polygon)
{
float total=0;
for(int i=0;i<polygon.size();i++)
{
   Vector a=polygon[(i+1)%polygon.size()]-polygon[i];
   Vector b=polygon[(i+2)%polygon.size()]-polygon[(i+1)%polygon.size()];
   a=!a; //normalvektor
   total+=(a*b); //skalarprodukt
}
printf("TOTAL: %f\n",total);
return (total>0);
}

"Ideen sind keine Coladosen, man kann sie nicht recyclen"-Dr. House
http://deeebian.redio.de/ http://goodjee.redio.de/

Übersicht

Sonstiges

Smalltalk

Nach Oben

BlitzBasic Portal

Mathe: Drehrichtung von Polygonen

Goodjee

Betreff: Mathe: Drehrichtung von Polygonen

darth

Goodjee

mpmxyz

Lunatix

Goodjee