GJK algoritması: basit bir işi tuhaf ve güzel bir şekilde çözmenin yolu

 (computerwebsite.net)
2 puan yazan GN⁺ 2024-06-13 | 1 yorum | WhatsApp'ta paylaş
  • GJK algoritması, iki şeklin üst üste binip binmediğini kontrol etmenin bir yoludur
  • Şekil A ile şekil B'nin çakışıp çakışmadığını kontrol etmek için, iki şeklin noktalarından en az birinin çakışıp çakışmadığını kontrol etmek yeterlidir

Minkowski farkı

  • İki şeklin tüm noktaları birbirinden çıkarılarak yeni bir küme oluşturulur.
  • Bu yeni küme orijini içeriyorsa, bu iki şeklin çakıştığı anlamına gelir.
  • Buna Minkowski farkı denir.

Algoritmanın temel fikri

  • A ile B'nin Minkowski farkının orijini içerip içermediği kontrol edilir.
  • Fark kümesi orijini içeriyorsa şekiller çakışır.

Algoritma adımları

  1. Başlatma: Rastgele bir yön vektörü d belirlenir ve ilk nokta p bulunur.
  2. Nokta bulma: d ile p arasındaki iç çarpım hesaplanır; sonuç pozitifse devam edilir, negatifse sonlandırılır.
  3. Yeni nokta ekleme: p'den orijin yönüne doğru yeni bir nokta bulunur.
  4. Sadeleştirme: İlk iki nokta temel alınarak yeni nokta eklenir ve sadeleştirme yapılır.
  5. Orijini içerip içermediğini kontrol etme: Sadeleştirilmiş şeklin orijini içerip içermediği kontrol edilir.
  6. Tekrarlama: Orijin içerilene kadar veya içerilmediğine dair bir kanıt bulunana kadar işlem tekrarlanır.

GN⁺ görüşü

  • İlginç nokta: GJK algoritması, karmaşık bir problemi basit bir matematiksel dönüşümle çözmenin iyi bir örneğidir.
  • Neden faydalı: Çarpışma algılama gibi gerçek zamanlı grafiklerde çok yararlı şekilde kullanılır.
  • Eleştirel bakış: Algoritmanın uygulanması karmaşık olabilir ve doğru anlaşılması gerekir.
  • İlgili teknolojiler: Diğer çarpışma algılama algoritmaları arasında SAT(Separating Axis Theorem) gibi yöntemler vardır.
  • Dikkate alınacaklar: GJK algoritması kullanılırken şekillerin karmaşıklığı ve hesaplama maliyeti göz önünde bulundurulmalıdır.

İlgili okumalar

1 yorum

 
GN⁺ 2024-06-13
Hacker News yorumları

  • GJK algoritması: 1990'larda GJK algoritmasını anlamaya çalışırken bir yıl boyunca epey uğraştım. Çarpışma tespiti ve en yakın noktayı bulmada faydalı. Temel fikir anlaşılması kolay. İki dışbükey cisimle başlanır, rastgele noktalar seçilir ve bu noktalar arasındaki mesafe iyileştirilmeye çalışılır. En yakın noktalar seçilip işlem tekrarlanır. En yakın nokta artık bir köşe olmadığında simplex kavramı gerekir. Bu, çeşitli durumları analiz etmek anlamına gelir. Fizik motorlarında nesneler yüzey-yüzey temasına oturduğunda sorun çıkar. Teoride zarif bir çözüm ama pratikte zor bir sayısal analiz problemidir. Yine de muhtemelen en hızlı yaklaşımdır. Genel durumda O(log N), önceki konuma yakınsa O(1)'dir. Oxford'dan merhum Prof. Stephen Cameron, GJK'nin düzgün uygulanması üzerine çok araştırma yaptı. 1990'ların sonlarında ticari 3D ragdoll sistemi "Falling Bodies" içinde GJK kullandım.

  • GJK açıklamasını yazma: GJK çarpışma tespit algoritmasına dair sezgisel bir açıklama bulamadığım için kendim yazdım. Daha açık ve verimli hale getirmenin bir yolu varsa söylemelerini istedim. Bu, bir lise öğrencisinin matematik açıklaması olduğu için uygun miktarda şüpheyle yaklaşılmalı.

  • GJK algoritması videosu: Aynı algoritma hakkında bir video sunum bağlantısı paylaşılıyor. Video bağlantısı

  • Yazıya övgü: Harika bir yazı. Çok açık ve ilgi çekici.

  • Dışbükey optimizasyon karşılaştırması: İki dışbükey küme arasındaki kesişimi kontrol etmenin başka bir yolu, iki nokta arasındaki farkın normunu en aza indiren bir dışbükey optimizasyon problemini çözmektir. En iyi değer 0 ise kümelerin bir kesişim noktası vardır. GJK algoritması ile dışbükey optimizasyon yaklaşımının karşılaştırmasını görmek isterdim. Hangisinin daha iyi olduğundan emin değilim.

  • Yazıya övgü ve yanlış anlama: Harika bir yazı. Ancak ilk görsel dışbükey olmayan şekillerin kesişimini gösteriyor; algoritmanın yalnızca dışbükey şekillerde çalıştığı ise daha sonra anlaşılıyor.

  • GJK algoritmasıyla ilk tanışma: GJK algoritmasını ilk kez duyuyorum.

  • İlgili blog yazısı: Minkowski geometrisiyle ilgili bir blog yazısı yazdım. Blog bağlantısı

  • Kişisel web sitesi: Beklenmedik şekilde ilgi gördüğü için kişisel web sitesinin şakayla dolu olduğunu belirtiyor. İletişime geçmek isteyenlerin yanıt olarak haber vermesini istiyor.

  • Minkowski fonksiyonunun kullanımı: openSCAD'de Minkowski fonksiyonunu kullanıyordum; bunun aslında ne olduğunu öğrenmek hoşuma gitti.

  • Algoritmaya övgü: Müthiş bir algoritma.