- Algoritme GJK adalah metode untuk memeriksa apakah dua bentuk saling bertumpang tindih
- Untuk memeriksa apakah bentuk A dan bentuk B bertumpang tindih, cukup periksa apakah ada titik dari kedua bentuk yang saling tumpang tindih
Selisih Minkowski
- Membuat himpunan baru dengan mengurangkan semua titik dari dua bentuk.
- Jika himpunan baru ini mencakup titik asal, itu berarti kedua bentuk bertumpang tindih.
- Ini disebut selisih Minkowski.
Ide dasar algoritme
- Memeriksa apakah selisih Minkowski dari A dan B mencakup titik asal.
- Jika selisih tersebut mencakup titik asal, kedua bentuk bertumpang tindih.
Langkah-langkah algoritme
- Inisialisasi: Tetapkan vektor arah sembarang
d, lalu cari titik pertama p.
- Mencari titik: Hitung hasil kali titik dari
d dan p; jika positif lanjutkan, jika negatif hentikan.
- Menambahkan titik baru: Dari
p, cari titik baru ke arah titik asal.
- Penyederhanaan: Tambahkan titik baru berdasarkan dua titik pertama untuk melakukan simplifikasi.
- Memeriksa apakah mencakup titik asal: Periksa apakah bentuk yang telah disederhanakan mencakup titik asal.
- Ulangi: Ulangi sampai bentuk mencakup titik asal atau sampai ditemukan bukti bahwa titik asal tidak tercakup.
Opini GN⁺
- Hal yang menarik: Algoritme GJK adalah contoh yang baik tentang bagaimana masalah kompleks dapat diselesaikan dengan transformasi matematis yang sederhana.
- Mengapa ini membantu: Sangat berguna dalam grafika real-time seperti deteksi tabrakan.
- Sudut pandang kritis: Implementasi algoritme bisa rumit dan membutuhkan pemahaman yang tepat.
- Teknologi terkait: Algoritme deteksi tabrakan lainnya mencakup SAT (Separating Axis Theorem) dan sebagainya.
- Hal yang perlu dipertimbangkan: Saat menggunakan algoritme GJK, kompleksitas bentuk dan biaya komputasi perlu dipertimbangkan.
1 komentar
Komentar Hacker News
Algoritma GJK: Pada 1990-an saya bersusah payah selama setahun untuk memahami algoritma GJK. Algoritma ini berguna untuk deteksi tabrakan dan mencari titik terdekat. Konsep dasarnya mudah dipahami. Mulainya dari dua benda padat cembung, memilih titik acak, lalu mencoba memperbaiki jarak di antara kedua titik itu. Pilih titik terdekat dan ulangi. Saat titik terdekat tidak lagi berupa simpul, konsep "simplex" menjadi diperlukan. Intinya adalah menganalisis berbagai kasus. Di mesin fisika, masalah muncul ketika objek menetap dalam kontak sisi-ke-sisi. Secara teori ini solusi yang elegan, tetapi dalam praktiknya merupakan masalah analisis numerik yang sulit. Meski begitu, ini kemungkinan masih pendekatan tercepat. Dalam kasus umum O(log N), dan bila dekat dengan posisi sebelumnya O(1). Almarhum Profesor Stephen Cameron dari Oxford melakukan banyak riset untuk mengimplementasikan GJK dengan benar. Pada akhir 1990-an, GJK digunakan dalam sistem ragdoll 3D komersial "Falling Bodies".
Menulis penjelasan GJK: Karena tidak bisa menemukan penjelasan intuitif tentang algoritma deteksi tabrakan GJK, saya menulisnya sendiri. Saya meminta masukan jika ada cara untuk membuatnya lebih jelas dan lebih efisien. Karena ini penjelasan matematika dari seorang siswa SMA, sebaiknya dibaca dengan tingkat skeptisisme yang wajar.
Video algoritma GJK: Membagikan tautan ke presentasi video tentang algoritma yang sama. Tautan video
Pujian untuk artikel: Artikel yang luar biasa. Sangat jelas dan menarik.
Perbandingan dengan optimisasi cembung: Cara lain untuk memeriksa perpotongan antara dua himpunan cembung adalah menyelesaikan masalah optimisasi cembung yang meminimalkan norma selisih antara dua titik. Jika nilai optimumnya 0, berarti himpunan tersebut berpotongan. Saya ingin melihat perbandingan antara algoritma GJK dan pendekatan optimisasi cembung. Saya tidak yakin mana yang lebih baik.
Pujian artikel dan kesalahpahaman: Artikelnya luar biasa. Namun, gambar pertama menunjukkan perpotongan bentuk tak cembung, sementara baru belakangan dijelaskan bahwa algoritma ini hanya bekerja pada bentuk cembung.
Baru pertama kali mendengar algoritma GJK: Ini pertama kalinya saya mendengar tentang algoritma GJK.
Posting blog terkait: Saya pernah menulis posting blog yang terkait dengan geometri Minkowski. Tautan blog
Situs web pribadi: Karena tiba-tiba mendapat perhatian, saya menyebutkan bahwa situs web pribadi saya penuh dengan lelucon. Jika ingin menghubungi saya, beri tahu lewat balasan.
Menggunakan fungsi Minkowski: Saya sudah menggunakan fungsi Minkowski di openSCAD, dan senang akhirnya tahu apa sebenarnya itu.
Pujian untuk algoritma: Algoritma yang hebat.