Orientierung eines 3Ecks

*Rewind*

Nein, zumindest nicht im Standard, aber vielleicht kannst du mir erklären, wie ein Dreieck eine Orientierung haben kann. Mit dem Dreieck ist in dem Fall wie mit einem Kreis: er hat keine Orientierung, es sei denn du definierst Referenz- bzw. Bezugspunkte. Das hat dann aber wiederum nichts mit dem Uhrzeigersinn zu tun, denn damit gibst du die Drehrichtung an. Dreht sich dein Dreieck? Zweite Frage: mit Segmenten meinst du die Dreiecksseiten?

Grüße,
Rew.

82kolu

icarus2 schrieb:

*Edit
Meinst du mit Orientierung in welcher Reihenfolge die Segmente gegeben sind?

Genau das mein ich.

icarus2

Ich weiss zwar nicht wofuer du es brauchst und wie man das am effizientesten feststellen kann, aber hier mal ein Ansatz:

Du nimmst das erste Segment und stellst dir das Segment mit einer Richtung vor (Anfangspunkt zu Endpunkt). Du schaust nun also in die Richtung des Segments und denkst dir, es sei eine Gerade. Wenn du das naechste Segment links von der Gerade ist, so drehst du dich im Gegenuhrzeiger sind. Andernfalls im Uhrzeigersinn.
Und dann halt nochmals fuer das naechste Segment.

Damit das klappt muessen die Segmente entsprechend gespeichert sein. Das oben muesstest du nochmals klar durchdenken. Sollte nur eine Idee sein, wie man das vielleicht machen koennnte. Keine Ahnung, ob es einfacher geht.

krümelkacker

Ich nehme mal 2D Punkte und 2D Vektoren an.

Die "Orientierung" kannst Du über die Determinante der 2x2 Matrix berechnen, die sich durch zwei Punktdifferenzen ergibt:

| punkt2x-punkt1x   punkt3x-punkt2x |    | a  b |
|                                   | =: |      |
| punkt2y-punkt1y   punkt3y-punkt2y |    | c  d |

Die Determinante davon ist a*d-b*c. Das Vorzeichen sagt Dir, ob die Punkte 1,2,3 nun im oder gegen den Uhrzeigersinn laufen. Wenn ich mich jetzt nicht vertan habe und wir ein normales Achsensystem aus der Mathematik verwenden (Y-Achse zeigt nach oben), dann sollte eine positive Determinante heißen, dass die Punkte 1,2,3 gegen den Uhrzeiger laufen.

Diese Determinante ist auch äquivalent zum Skalarprodukt zweier Kantenvektoren, wobei der eine aber um 90° gedreht wurde. Damit kann man sich IMHO mit etwas Überlegen leicht erklären, dass das auch wirklich so funktioniert.

*Rewind*

Meinst du a*d-b*c?

82kolu

icarus2 schrieb:

Ich weiss zwar nicht wofuer du es brauchst und wie man das am effizientesten feststellen kann, aber hier mal ein Ansatz:

Du nimmst das erste Segment und stellst dir das Segment mit einer Richtung vor (Anfangspunkt zu Endpunkt). Du schaust nun also in die Richtung des Segments und denkst dir, es sei eine Gerade. Wenn du das naechste Segment links von der Gerade ist, so drehst du dich im Gegenuhrzeiger sind. Andernfalls im Uhrzeigersinn.
Und dann halt nochmals fuer das naechste Segment.

Damit das klappt muessen die Segmente entsprechend gespeichert sein. Das oben muesstest du nochmals klar durchdenken. Sollte nur eine Idee sein, wie man das vielleicht machen koennnte. Keine Ahnung, ob es einfacher geht.

Ich mein damit das es zu aufwändig ist keine Missverständnisse... ^^

82kolu

krümelkacker schrieb:

Ich nehme mal 2D Punkte und 2D Vektoren an.

Die "Orientierung" kannst Du über die Determinante der 2x2 Matrix berechnen, die sich durch zwei Punktdifferenzen ergibt:
| punkt2x-punkt1x   punkt3x-punkt2x |    | a  b |
|                                   | =: |      |
| punkt2y-punkt1y   punkt3y-punkt2y |    | c  d |
Die Determinante davon ist a*d-b*c. Das Vorzeichen sagt Dir, ob die Punkte 1,2,3 nun im oder gegen den Uhrzeigersinn laufen. Wenn ich mich jetzt nicht vertan habe und wir ein normales Achsensystem aus der Mathematik verwenden (Y-Achse zeigt nach oben), dann sollte eine positive Determinante heißen, dass die Punkte 1,2,3 gegen den Uhrzeiger laufen.

Diese Determinante ist auch äquivalent zum Skalarprodukt zweier Kantenvektoren, wobei der eine aber um 90° gedreht wurde. Damit kann man sich IMHO mit etwas Überlegen leicht erklären, dass das auch wirklich so funktioniert.

ah cool wenn des geht des wär super. wo hast du die formel gefunden? oder kanntest du die?

krümelkacker

icarus2 schrieb:

[...] Du schaust nun also in die Richtung des Segments und denkst dir, es sei eine Gerade. Wenn du das naechste Segment links von der Gerade ist, so drehst du dich im Gegenuhrzeiger sind. Andernfalls im Uhrzeigersinn. [...]

Auf welcher Seite der dritte Punkt ist, würde man über ein Skalarprodukt berechnen.

| v'
             | 
        v    |
    2 *<-----+-----* 1
             |
             |
             V

         *
         3

wobei v' eine um 90° gedrehte Version von v ist. Ist nun dot(v',punkt3-punkt2)>0 liegt der 3. Punkt links von der Kante v wenn man von 1 nach 2 schaut. "dot" soll hier das Skalarprodukt sein.

90°-Rotation + Skalarprodukt ist aber genau das, was man mit der Determinante a*d-b*c berechnet, wie ich das vorher erklärt habe.

82kolu schrieb:

ah cool wenn des geht des wär super. wo hast du die formel gefunden? oder kanntest du die?

Ich wusste das.

82kolu

krümelkacker schrieb:

Ich wusste das.

Cool danke!

Werner Salomon

Also der Standard liefert schon ein wenig Unterstützung.
Wenn man sich ein wenig mit dem mathematischen Hintergrund auskennt, so kann man die komplexen Zahlen dafür verwenden. Seien a, b und c die Eckpunkte und ax, ay, bx, by, cx und cy die Koordinaten dieser Punkte, so kann man schreiben

complex< double > a(ax,ay);
    complex< double > b(bx,by);
    complex< double > c(cx,cy);
    if( imag(conj(b-a)*(c-a)) > 0.0 )
    {
        // Drehsinn math. positiv bzw. Gegenuhrzeigersinn

das ganze erfordert natürlich ein #include <complex>.
Wenn Du nur wenige Dreiecke hast, so kannst Du es so machen. Wenn es mehrere 10000 sind, ist die Lösung von krümelkacker performanter.

Gruß
Werner

82kolu

Werner Salomon schrieb:

Also der Standard liefert schon ein wenig Unterstützung.
Wenn man sich ein wenig mit dem mathematischen Hintergrund auskennt, so kann man die komplexen Zahlen dafür verwenden. Seien a, b und c die Eckpunkte und ax, ay, bx, by, cx und cy die Koordinaten dieser Punkte, so kann man schreiben
complex< double > a(ax,ay);
    complex< double > b(bx,by);
    complex< double > c(cx,cy);
    if( imag(conj(b-a)*(c-a)) > 0.0 )
    {
        // Drehsinn math. positiv bzw. Gegenuhrzeigersinn
das ganze erfordert natürlich ein #include <complex>.
Wenn Du nur wenige Dreiecke hast, so kannst Du es so machen. Wenn es mehrere 10000 sind, ist die Lösung von krümelkacker performanter.

Gruß
Werner

Kannst du das nochmal ausführlicher erklären?

Werner Salomon

Oje - das habe ich jetzt wieder davon
Ich weiß jetzt nicht wo ich da anfangen soll. Kannst Du zwei komplexe Zahlen mit einander multiplizieren?

82kolu

Werner Salomon schrieb:

Oje - das habe ich jetzt wieder davon
Ich weiß jetzt nicht wo ich da anfangen soll. Kannst Du zwei komplexe Zahlen mit einander multiplizieren?

Oh sorry hab deine gegenfrage nicht gesehen... habs jetzt schon auf die andere art implementiert... aber danke