Mengurutkan berbagai titik dalam urutan searah jarum jam

Apakah ada algoritma semacam itu untuk mengurutkan array poin 2D dalam urutan searah jarum jam?
Saya secara khusus berurusan dengan segitiga siku-siku dalam kasus saya jadi hanya 3 poin.

Namun saya tertarik untuk mengetahui apakah ada algoritma seperti itu, jika tidak apa cara sederhana untuk mengembalikan 3 poin dari segitiga saya dalam urutan searah jarum jam?

Sunting: Saya mencoba menghitung titik searah jarum jam relatif terhadap pusat massa poligon, yang cembung.

Pembaruan: Ini adalah implementasi yang saya akhirnya gunakan berdasarkan jawaban yang dipilih, itu bukan kinerja kritis dan hanya terjadi sesekali sehingga berhasil.

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

}

Pertanyaan Anda tidak cukup tepat. Array poin hanya «searah jarum jam» atau «berlawanan arah jarum jam» relatif terhadap titik referensi. Jika tidak, setiap array dari tiga titik selalu dapat berupa CW atau CCW. Lihat gambar berikut: di sebelah kiri, titik-titiknya diatur searah jarum jam; di sebelah kanan, titik-titik yang persis sama dipesan berlawanan arah jarum jam.

Dalam kasus Anda, saya percaya menggunakan barycenter poin sebagai titik referensi masuk akal.

Metode yang baik untuk jumlah poin yang tidak diketahui bisa berupa yang berikut:

• biarlah P[0], P[1], ... P[n-1]daftar poin untuk disortir
• biarkan M menjadi barycenter dari semua poin
• menghitung a[0], a[1], ... a[n-1]sedemikian rupa sehinggaa[i] = atan2(P[i].y - M.y, P[i].x - M.x);
• mengurutkan poin relatif terhadap anilainya, menggunakan qsortmisalnya.

Namun, Anda dapat yakin bahwa algoritma penyortiran yang baik akan berkinerja buruk dengan tiga nilai input dibandingkan dengan metode ad-hoc. Penggunaan atan2masih valid, tapi jangan gunakan qsort.

Saya percaya bahwa yang sebenarnya Anda tanyakan di sini adalah urutan belitan segitiga, yang sebenarnya cukup mudah untuk diuji.

Karena hanya ada tiga titik dalam segitiga Anda, segitiga Anda sudah dalam urutan searah jarum jam atau berlawanan arah jarum jam, dan yang perlu Anda lakukan adalah memeriksa mana dari dua itu, dan membalikkan urutan indeks jika belitan bukan yang kamu inginkan.

Inilah ide umum, dengan asumsi bahwa tiga simpul segitiga adalah a , b , dan c , dan bahwa Anda memiliki operasi pengurangan vektor sederhana:

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

Perhatikan bahwa tergantung pada arah mana Anda mengarahkan sumbu + y Anda (naik atau turun), case "searah jarum jam" dan "berlawanan arah jarum jam" dapat dibalik dari cara saya memberi label pada komentar dalam kode contoh ini.

Bisakah Anda memberi info lebih lanjut? Anda menginginkan urutan poin CCW, tetapi titik mana yang harus menjadi pusat pemesanan?

Jika Anda hanya memiliki segitiga (3 poin) dalam bidang, Anda dapat menghitung determinan dari matriks, di mana garis adalah koordinat titik (koordinat ke-3 adalah 1). Jika determinan> 0, poin berada dalam urutan CCW. Jika tidak, Anda dapat swith misalnya dua poin terakhir dan Anda akan mendapatkan pesanan CCW.

Jika Anda memiliki poin A, B, C, maka matriks Anda terlihat seperti:

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

Determinan adalah: xA * yB + xB * yC + xC * yA - yB * xC - yC * xA - yA * xB. Kemudian Anda dapat membandingkannya dengan nol. Jika> 0, kembalikan poin A, B, C, jika tidak, kembalikan A, C, B.

Jika Anda memiliki set poin dan tahu, mereka membuat cembung poligon (semua adalah bagian dari cembung lambung), dan ingin mendapatkan pesanan mereka, Anda dapat menggunakan Graham Scan atau Jarvis's March (ini adalah algoritma untuk menemukan cembung cembung dari banyak titik, tetapi itu juga harus bekerja di sini :))