Sortieren von Punkten gegen den Uhrzeigersinn

[bords0]

Das täuscht. Zum einen habe ich fünf unterschiedliche Methoden gefunden, zum anderen bewegen sich deren Geschwindigkeitsunterschiede im Bereich von Mikrosekunden.

Eine Messung mit auskommentierter Berechnung (Zeile 70) scheint mir wenig aussagekräftig

[HWK]

Stimmt!
Meine Tests hatte ich zwar ohne Kommentare durchgeführt, habe sie dann aber eingefügt, um die Ausgabe nicht unnötig aufzublähen.
Hier sind jetzt die Ergebnisse mit ausgeführtem f(points):

Code: Alles auswählen

0.000812
0.000771
0.000798
0.001868
0.000790

Dabei schneidet die für spinneratz subjektiv am schnellsten erscheinende Lösung leider am schlechtesten ab, wobei wohl selbst die 1 ms nicht ins Gewicht fällt.
MfG
HWK

[Kleinmeister]

Man braucht hierfür keine Winkelfunktionen, es geht auch einfacher.

Punkt A hat die Koordinaten (x_a, y_a), Punkt B (x_B, y_B) und Punkt C (x_C, y_C).
Dann kann man von A ausgehend die Vektoren AB = B-A und AC = C-A berechnen.
Diese haben die Koordinaten x_AB = x_B - x_A, y_AB = y_B - y_A, x_AC = x_C - x_A und y_AC = y_C - y_A.

Nun bildet man das Vektorprodukt von AB und AC. Da das Dreieck in einer Ebene liegt, hat das Vektorprodukt nur eine z-Komponente.
Diese berechnet sich zu
V_z = x_AB * y_AC - y_AB * x_AC oder ausgeschrieben:

V_z = (x_B - x_A)*(y_C - y_A) - (y_B - y_A)*(x_C - x_A).
"Im Uhrzeigersinn" und "gegen Uhrzeigersinn" kann man nun am Vorzeichen von V_z unterscheiden:

Positives Vorzeichen, V_z > 0: Die Punkte (A, B, C) werden im UZS durchlaufen.
Negatives Vorzeichen, V_z < 0: Die Punkte (A, B, C) werden gegen den Uhrzeigersinn durchlaufen.
V_z = 0: Die Punkte liegen auf einer Linie (oder sind sogar identisch): Richtung nicht eindeutig.

Die Methode kommt mit zwei Multiplikationen und 5 Subtraktionen aus und dürfte im Vergleich am schnellsten sein. Es gibt nur eine Fallunterscheidung ganz am Ende.

Die Rückmeldung kommt etwas spät, habe die Frage heute erst gelesen.
Vielleicht hilft es aber trotzdem noch irgendwo.