Sortowanie tablicy punktów w kolejności zgodnej z ruchem wskazówek zegara

Czy istnieje taki algorytm do sortowania tablicy punktów 2D w kolejności zgodnej z ruchem wskazówek zegara?
W moim przypadku mam do czynienia z trójkątem prostokątnym, więc tylko 3 punkty.

Chciałbym jednak wiedzieć, czy taki algorytm istnieje, a jeśli nie, to w jaki sposób można zwrócić 3 punkty mojego trójkąta w kolejności zgodnej z ruchem wskazówek zegara?

Edycja: Próbuję obliczyć punkty zgodnie z ruchem wskazówek zegara w stosunku do środka ciężkości wielokąta, który jest wypukły.

Aktualizacja: jest to implementacja, z której korzystałem w oparciu o wybraną odpowiedź, nie jest krytyczna pod względem wydajności i zdarza się tylko raz na jakiś czas, więc działa.

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;
    }

}

Twoje pytanie nie jest wystarczająco precyzyjne. Układ punktów jest tylko „zgodny z ruchem wskazówek zegara” lub „przeciwnie do ruchu wskazówek zegara” w stosunku do punktu odniesienia. W przeciwnym razie dowolna tablica trzech punktów może zawsze mieć wartość CW lub CCW. Zobacz następujący obrazek: po lewej punkty są uporządkowane zgodnie z ruchem wskazówek zegara; po prawej dokładnie te same punkty są uporządkowane przeciwnie do ruchu wskazówek zegara.

W twoim przypadku uważam, że użycie barycentrum punktów jako punktu odniesienia jest rozsądne.

Dobrą metodą dla nieznanej liczby punktów może być następująca:

• niech P[0], P[1], ... P[n-1]będzie lista punktów do posortowania
• niech M będzie centrum wszystkich punktów
• obliczyć a[0], a[1], ... a[n-1]tak, żea[i] = atan2(P[i].y - M.y, P[i].x - M.x);
• posortuj punkty względem ich awartości, używając qsortna przykład.

Jednak możesz być pewien, że dobry algorytm sortowania będzie działał słabo przy trzech wartościach wejściowych w porównaniu do metody ad-hoc. Używanie atan2jest nadal prawidłowe, ale po prostu nie używaj qsort.

Uważam, że tak naprawdę pytasz o kolejność nawijania trójkąta, która w rzeczywistości jest dość prosta do przetestowania.

Ponieważ w twoim trójkącie są tylko trzy punkty, twój trójkąt jest już w kolejności zgodnej z ruchem wskazówek zegara lub przeciwnie do ruchu wskazówek zegara, więc wszystko, co musisz zrobić, to sprawdzić, który z nich jest, i odwrócić kolejność indeksów, jeśli uzwojenie nie jest tym, którego chcesz.

Oto ogólna idea, zakładając, że trzy wierzchołki trójkąta to a , b i c , i że masz prostą operację odejmowania wektora:

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.
}

Zauważ, że w zależności od tego, w jaki sposób zorientowałeś oś + y (w górę lub w dół), przypadki „zgodnie z ruchem wskazówek zegara” i „przeciwnie do ruchu wskazówek zegara” mogą być odwrócone od tego, jak opisałem je w komentarzach w tym przykładowym kodzie.

Czy możesz podać więcej informacji? Chcesz kolejność punktów w CCW, ale jaki punkt powinien być w centrum zamawiania?

Jeśli masz tylko trójkąt (3 punkty) w płaszczyźnie, możesz obliczyć wyznacznik z macierzy, gdzie linie są współrzędnymi punktów (3. współrzędna to 1). Jeśli wyznacznikiem jest> 0, punkty są w kolejności CCW. Jeśli nie, możesz zaliczyć na przykład ostatnie dwa punkty, a otrzymasz zamówienie CCW.

Jeśli masz punkty A, B, C, to twoja macierz wygląda następująco:

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

Determinantem jest: xA * yB + xB * yC + xC * yA - yB * xC - yC * xA - yA * xB. Następnie możesz porównać to z zerem. Jeśli jest> 0, zwróć punkty A, B, C, jeśli nie, zwróć A, C, B.

Jeśli masz zestaw punktów i wiesz, że tworzą wypukły wielokąt (wszystkie są częścią wypukłego kadłuba) i chcą uzyskać ich kolejność, możesz użyć Graham Scan lub Jarvis's March (są to algorytmy do znalezienia wypukłego kadłuba z wielu punktów, ale tu też powinno działać :))