Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Rechts oder Links drehende Form

  • 1
  • 2

Werbeanzeige

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

1

10.07.2014, 11:04

Rechts oder Links drehende Form

Ich habe eine variable Anzahl an Punkten innerhalb eines arrays. 2 Nachbarn innerhalb dieses arrays ergeben eine gerade, der erste und der letzte Punkt ebenso (d.h. die Form ist geschlossen).
Wie bekomme ich jetzt heraus, ob die Form links oder rechts herum geschlossen ist?
Habe ein paar Überlegungen angestellt aber irgendwie komme ich auf keinen grünen Zweig. Hat da jemand eine Idee? Gibt es dafür eine allgemein gültige Formel?

Zum besseren Verständnis, was ich eigentlich meine, habe ich mal eine kleine Skizze angehängt.
rot = form
schwarz = koordinatensystem

Wenn jetzt z.B. die 3 Punkte in dieser Reihenfolge im Array liegen:

0/4; 2/0; 4/4

ist es links herum geschlossen.
Wenn sie z.B. so liegen:
0/4; 4/4; 2/0
ist es rechts herum geschlossen.

Wäre über einen kleinen Schubs in die richtige Richtung sehr dankbar ;)

mfg

EDIT: Eine meiner Überlegungen war, die Winkel der einzelnen Linien zueinander zu addieren. Welche Richtung kleiner ist, ist dann natürlich der Innenwinkel. Gibt es noch eine einfachere Variante?
»anti-freak« hat folgendes Bild angehängt:
  • form.png

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

2

10.07.2014, 11:19

Es müssten bei Innenwinkel immer (n-2)*180 sein. Kommst Du aber auf n*360-(n-2)*180, dann ist das Polygon andersherum.
Du kannst auch das Kreuzprodukt zweier angrenzenden Seiten nehmen und schauen in welche Richtung die so gebildete Normale zeigt. Letzteres wäre deutlich schneller, geht aber nur bei konvexen Polys, denke ich.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

3

10.07.2014, 11:30

Rechne die z-Koordinate des Kreuzprodukts zweier Kantenvektoren aus und schau dir das Vorzeichen an. ;)
m4studios

BlueCobold

Community-Fossil

Beiträge: 10 738

Beruf: Teamleiter Mobile Applikationen & Senior Software Engineer

  • Private Nachricht senden

4

10.07.2014, 11:32

Geht das denn auch bei konkaven? Ja, ja, meine linke/rechte Hand-Tests sind auch nicht mehr das, was sie mal waren.
Edit: Doch, sollte passen.
Teamleiter von Rickety Racquet (ehemals das "Foren-Projekt") und von Marble Theory

Willkommen auf SPPRO, auch dir wird man zu Unity oder zur Unreal-Engine raten, ganz bestimmt.[/Sarkasmus]

dot

Supermoderator

Beiträge: 9 757

Wohnort: Graz

  • Private Nachricht senden

5

10.07.2014, 13:19

Mit konkaven Formen funktioniert das so einfach in der Tat nicht. Allerdings gibt es einen gewissermaßen verwandten Weg, um sehr einfach die Fläche eines (nicht überschlagenen) Polygons zu berechnen: Du bildest für jede Kante das von Startpunkt, Endpunkt und dem Ursprung aufgespannte Dreieck, berechnest dessen gerichtete Fläche (entspricht der z-Koordinate des Kreuzproduktes von Start- und Endpunkt) und summierst diese Flächen für alle Kanten auf. Auf diesem Weg bestimmst du den gerichteten Flächeninhalt des Polygons, welcher je nach Drehsinn der Figur positiv oder negativ ist.
m4studios

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

6

10.07.2014, 16:18

Danke für die Antworten, nur hilf mir mal schnell auf die Sprünge.
Kantenvektor:
Was genau ist damit gemeint? Ist das z.B. ein Vektor mit der minimalsten bzw. maximalsten x Koordinate?

Kreuzprodukt, ich versuche mich da gerade einzulesen, es macht mich aber stutzig, das hier immer von 3d ausgegangen wird, ich befinde mich allerdings im 2d Raum. Ist das trotzdem so gültig?

Meine Mathe Kenntnisse sind leider ein wenig eingerostet und leider auch nur bis zum Mittelstufen Niveau vorhanden. Könntest du das vll nochmal ein wenig ausführen?

mfg

iSmokiieZz

Treue Seele

Beiträge: 364

  • Private Nachricht senden

7

10.07.2014, 16:34

Natürlich bist du im 2D Raum, aber du denkst dir einfach einen 3D Raum, weil du nur dort das Kreuzprodukt anwenden kannst.

Mit Kantenvektor ist einfach ein Vektor gemeint, der eine Kante / eine Seite deines Dreiecks darstellt.

Beim Kreuzprodukt zweier Kantenvektor bekommst du dann einen resultierenden Vektor, der orthogonal zu der Ausgangsvektoren ist.
§\vec{a} \times \vec{b} = \vec{n}§ mit §\vec{n} \perp \vec{a}§ und §\vec{n} \perp \vec{b}§

Jetzt zeigt der resultierende Normalenvektor dazu noch immer in eine solche Richtung, dass er mit den anderen Vektoren ein Rechtssystem bildet, was heißen soll, dass er je nach Anordnung der Ausgangsvektoren in zwei unterschiedliche Richtungen zeigen kann.

Da du jetzt nur 2D-Ausgangsvektoren hast, musst du aus denen noch 3D-Vektoren machen, indem du einfach eine 0 für die Z-Koordinate einsetzt.

Demnach wird der Normalenvektor dann entsprechend in die Richtung der z-Koordinate verlaufen, oder entgegen. (siehe Vorzeichen)

Voilà

Und jetzt holst du dir noch ein Mathebuch und studierst Vektorrechnung! ;)
EnvisionGame(); EnableGame(); AchieveGame(); - Visionen kann man viele haben. Sie umzusetzen und auf das Ergebnis stolz zu sein ist die eigentliche Kunst.

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

8

10.07.2014, 21:22

Ok, vielen Dank. Das hat mir doch sehr weiter geholfen ;)
Hab mich auch einmal ein wenig in die Vektor und Matrix Grundlagen eingelesen, kann ja nicht schaden.

mfg

anti-freak

Alter Hase

  • »anti-freak« ist der Autor dieses Themas

Beiträge: 635

  • Private Nachricht senden

9

10.07.2014, 23:21

Zitat von »dot«

Mit konkaven Formen funktioniert das so einfach in der Tat nicht. Allerdings gibt es einen gewissermaßen verwandten Weg, um sehr einfach die Fläche eines (nicht überschlagenen) Polygons zu berechnen: Du bildest für jede Kante das von Startpunkt, Endpunkt und dem Ursprung aufgespannte Dreieck, berechnest dessen gerichtete Fläche (entspricht der z-Koordinate des Kreuzproduktes von Start- und Endpunkt) und summierst diese Flächen für alle Kanten auf. Auf diesem Weg bestimmst du den gerichteten Flächeninhalt des Polygons, welcher je nach Drehsinn der Figur positiv oder negativ ist.

Tut mir leid für den Doppelpost, aber hier werfen sich mir doch noch ein paar Fragen auf.
Wenn ich nur das Kreuzprodukt der Eckpunkte jeder Kante berechnen soll, warum redest du dann von Dreiecken?
Und von welchem Ursprung redest du, den 0/0?
Wenn ja, wie soll das denn die Fläche des Polygons darstellen?

Steef

Alter Hase

Beiträge: 492

  • Private Nachricht senden

10

11.07.2014, 00:46

Zitat von »anti-freak«

Wenn ich nur das Kreuzprodukt der Eckpunkte jeder Kante berechnen soll, warum redest du dann von Dreiecken?

Du verwechselst hier was. iSmokiieZz redet von Kantenvektoren und liefert dir eine Methode mit diesen, die allerdings nur für bestimmte Polygone funktioniert. Dot spricht von den aufgespannten Dreiecken zwischen dem Ursprung und zwei Punkten einer Kante.

Zitat von »anti-freak«

Und von welchem Ursprung redest du, den 0/0?

Ja, mit Ursprung ist immer 0/0/.../0 gemeint.

Zitat von »anti-freak«

Wenn ja, wie soll das denn die Fläche des Polygons darstellen?

Der Betrag des Kreuzprodukt liefert die Größe des Parallelogramms (nicht Dreieck, aber der konstante Faktor ist irrelevant) das durch die 2 Punkte und den Ursprung eindeutig bestimmt ist. Da du in 2D arbeitest, sind x und y 0.

Dot, hast du nen mathematischen Beweis für deine Methode? Der würde mich mal interessieren.
"Theory is when you know something, but it doesn’t work. Practice is when something works, but you don’t know why. Programmers combine theory and practice: Nothing works and they don’t know why." - Anon

Werbeanzeige

  • 1
  • 2

Ähnliche Themen