Anordnung der Punkte im Uhrzeigersinn

Gibt es einen solchen Algorithmus, um ein Array von 2D-Punkten im Uhrzeigersinn zu sortieren?
Ich habe es in meinem Fall speziell mit rechtwinkligen Dreiecken zu tun, also nur mit 3 Punkten.

Ich möchte jedoch wissen, ob es einen solchen Algorithmus gibt. Wenn nicht, was ist eine einfache Möglichkeit, die 3 Punkte meines Dreiecks im Uhrzeigersinn zurückzugeben?

Bearbeiten: Ich versuche, die Punkte im Uhrzeigersinn relativ zum Schwerpunkt des Polygons zu berechnen, der konvex ist.

Update: Dies ist die Implementierung, die ich basierend auf der gewählten Antwort verwendet habe. Sie ist nicht leistungskritisch und kommt nur gelegentlich vor, sodass es funktioniert.

ArrayList<PVector> pointList = new ArrayList<PVector>();
pointList.add(A);
pointList.add(B);
pointList.add(C);
Collections.sort( pointList, new TriangleVectorComparator(origin) );

return pointList;

// Comparator
package triangleeditor;

import java.util.Comparator;

import processing.core.PVector;

public class TriangleVectorComparator implements Comparator<PVector>  {
    private PVector M; 
    public TriangleVectorComparator(PVector origin) {
        M = origin;
    }

    public int compare(PVector o1, PVector o2) {
        double angle1 = Math.atan2(o1.y - M.y, o1.x - M.x);
        double angle2 = Math.atan2(o2.y - M.y, o2.x - M.x);

        //For counter-clockwise, just reverse the signs of the return values
        if(angle1 < angle2) return 1;
        else if (angle2 < angle1) return -1;
        return 0;
    }

}

Ihre Frage ist nicht präzise genug. Eine Punktanordnung ist nur «im Uhrzeigersinn» oder «gegen den Uhrzeigersinn» relativ zu einem Referenzpunkt. Andernfalls kann jedes Array von drei Punkten immer im Uhrzeigersinn oder im Gegenuhrzeigersinn sein. Siehe folgendes Bild: Links sind die Punkte im Uhrzeigersinn angeordnet; rechts sind genau die gleichen Punkte gegen den Uhrzeigersinn angeordnet.

In Ihrem Fall halte ich es für sinnvoll, den Schwerpunkt der Punkte als Bezugspunkt zu verwenden.

Eine gute Methode für eine unbekannte Anzahl von Punkten könnte die folgende sein:

• sei P[0], P[1], ... P[n-1]die Liste der zu sortierenden Punkte
• sei M der Schwerpunkt aller Punkte
• so berechnen a[0], a[1], ... a[n-1], dassa[i] = atan2(P[i].y - M.y, P[i].x - M.x);
• sortiere Punkte relativ zu ihrem aWert, qsortzum Beispiel mit.

Sie können jedoch sicher sein, dass ein guter Sortieralgorithmus mit drei Eingabewerten im Vergleich zu einer Ad-hoc-Methode schlecht abschneidet. Using atan2ist weiterhin gültig, wird aber nur nicht verwendet qsort.

Ich glaube, was Sie hier tatsächlich fragen, ist die Wicklungsreihenfolge des Dreiecks, die eigentlich ziemlich einfach zu testen ist.

Da Ihr Dreieck nur drei Punkte enthält, befindet sich Ihr Dreieck bereits entweder im oder gegen den Uhrzeigersinn. Sie müssen also nur überprüfen, um welche der beiden Punkte es sich handelt, und die Reihenfolge der Indizes bei der Wicklung umkehren ist nicht der, den du willst.

Hier ist die allgemeine Idee unter der Annahme, dass die drei Eckpunkte eines Dreiecks a , b und sind c sind und dass Sie eine einfache Vektorsubtraktionsoperation haben:

Vector2 AToB = b - a;
Vector2 BToC = c - b;
float crossz = AToB.x * BToC.y - AToB.y * BToC.x;
if ( crossz > 0.0f )
{
  // clockwise
}
else
{
  // counter-clockwise.  Need to reverse the order of our vertices.
}

Beachten Sie, dass die Fälle "im Uhrzeigersinn" und "gegen den Uhrzeigersinn" je nachdem, in welcher Richtung Sie Ihre + y-Achse ausgerichtet haben (nach oben oder unten), möglicherweise umgekehrt sind, als in den Kommentaren in diesem Beispielcode angegeben.

Können Sie weitere Informationen geben? Sie möchten die CCW-Reihenfolge der Punkte, aber welcher Punkt sollte im Mittelpunkt der Reihenfolge stehen?

Wenn Sie nur ein Dreieck (3 Punkte) in der Ebene haben, können Sie die Determinante aus der Matrix berechnen, wobei Linien Koordinaten von Punkten sind (3. Koordinate ist 1). Wenn die Determinante> 0 ist, sind die Punkte in CCW-Reihenfolge. Wenn nicht, können Sie zum Beispiel die letzten zwei Punkte wechseln und erhalten die CCW-Reihenfolge.

Wenn Sie die Punkte A, B, C haben, sieht Ihre Matrix folgendermaßen aus:

|xA, yA, 1|
|xB, yB, 1|
|xC, yC, 1|

Determinante ist: xA * yB + xB * yC + xC * yA - yB * xC - yC * xA - yA * xB. Dann können Sie es mit Null vergleichen. Wenn es> 0 ist, geben Sie die Punkte A, B, C zurück. Wenn nicht, geben Sie A, C, B zurück.

Wenn Sie eine Reihe von Punkten haben und wissen, dass sie konvexe Polygone bilden (alle sind Teil der konvexen Hülle) und ihre Reihenfolge erhalten möchten, können Sie Graham Scan oder Jarvis's March verwenden (dies sind Algorithmen, um die konvexe Hülle aus vielen Punkten zu finden, aber es sollte auch hier funktionieren :))