GJK एल्गोरिद्म: साधारण कामों को अजीब और खूबसूरती से हल करने का तरीका

 (computerwebsite.net)
2 पॉइंट द्वारा GN⁺ 2024-06-13 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • GJK एल्गोरिद्म यह जांचने का एक तरीका है कि क्या दो आकृतियाँ एक-दूसरे पर ओवरलैप करती हैं
  • यह जांचने के लिए कि आकृति A और आकृति B ओवरलैप करती हैं या नहीं, यह देखना होता है कि क्या दोनों आकृतियों के बिंदुओं में से कोई एक भी एक-दूसरे से मेल खाता है

Minkowski अंतर समुच्चय

  • दो आकृतियों के सभी बिंदुओं को घटाकर एक नया समुच्चय बनाया जाता है।
  • अगर इस नए समुच्चय में मूलबिंदु शामिल हो, तो इसका मतलब है कि दोनों आकृतियाँ ओवरलैप करती हैं।
  • इसे Minkowski अंतर समुच्चय कहा जाता है।

एल्गोरिद्म का मूल विचार

  • यह जांचना कि A और B का Minkowski अंतर समुच्चय मूलबिंदु को शामिल करता है या नहीं।
  • अगर अंतर समुच्चय में मूलबिंदु शामिल है, तो दोनों आकृतियाँ ओवरलैप करती हैं।

एल्गोरिद्म के चरण

  1. आरंभ: एक मनमाना दिशा वेक्टर d सेट किया जाता है और पहला बिंदु p खोजा जाता है।
  2. बिंदु खोजना: d और p का डॉट प्रोडक्ट निकाला जाता है; अगर यह धनात्मक हो तो प्रक्रिया जारी रहती है, और ऋणात्मक हो तो समाप्त हो जाती है।
  3. नया बिंदु जोड़ना: p से मूलबिंदु की दिशा में एक नया बिंदु खोजा जाता है।
  4. सरलीकरण: पहले दो बिंदुओं के आधार पर नया बिंदु जोड़कर simplex को अपडेट किया जाता है।
  5. मूलबिंदु शामिल है या नहीं, इसकी जांच: यह देखा जाता है कि सरलीकृत आकृति में मूलबिंदु शामिल है या नहीं।
  6. दोहराव: जब तक मूलबिंदु शामिल न हो जाए, या यह प्रमाण न मिल जाए कि वह शामिल नहीं है, तब तक प्रक्रिया दोहराई जाती है।

GN⁺ की राय

  • दिलचस्प बात: GJK एल्गोरिद्म इस बात का एक अच्छा उदाहरण है कि जटिल समस्या को सरल गणितीय रूपांतरण से कैसे हल किया जा सकता है।
  • यह उपयोगी क्यों है: real-time graphics में collision detection जैसे कामों में इसका बहुत उपयोग होता है।
  • आलोचनात्मक दृष्टिकोण: एल्गोरिद्म का implementation जटिल हो सकता है, और इसे सही तरह से समझना जरूरी है।
  • संबंधित तकनीक: अन्य collision detection एल्गोरिद्म में SAT(Separating Axis Theorem) आदि शामिल हैं।
  • ध्यान देने योग्य बात: GJK एल्गोरिद्म का उपयोग करते समय आकृतियों की जटिलता और computation cost को ध्यान में रखना चाहिए।

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-06-13
Hacker News टिप्पणियाँ

  • GJK एल्गोरिथ्म: 1990s में GJK एल्गोरिथ्म को समझने की कोशिश में एक साल तक जूझना पड़ा। यह collision detection और सबसे नज़दीकी बिंदु खोजने में उपयोगी है। मूल विचार समझना आसान है। दो convex solids से शुरू करके एक random point चुना जाता है, फिर हर बिंदु-युग्म के बीच की दूरी को बेहतर करने की कोशिश की जाती है। सबसे नज़दीकी बिंदु चुना जाता है और प्रक्रिया दोहराई जाती है। जब सबसे नज़दीकी बिंदु अब vertex नहीं रहता, तब "simplex" की अवधारणा की ज़रूरत पड़ती है। इसमें कई मामलों का विश्लेषण करना होता है। physics engine में तब समस्या आती है जब objects face-to-face contact पर स्थिर हो जाते हैं। सैद्धांतिक रूप से यह एक elegant समाधान है, लेकिन व्यवहार में यह कठिन numerical analysis की समस्या है। फिर भी, संभवतः यह सबसे तेज़ तरीका है। सामान्य स्थिति में O(log N), और पिछली स्थिति के क़रीब होने पर O(1) है। Oxford के दिवंगत प्रोफेसर Stephen Cameron ने GJK को सही तरह से implement करने पर बहुत शोध किया था। 1990s के उत्तरार्ध में commercial 3D ragdoll system "Falling Bodies" में GJK का उपयोग किया गया था.

  • GJK विवरण लिखना: GJK collision detection एल्गोरिथ्म की एक सहज व्याख्या नहीं मिल रही थी, इसलिए इसे खुद लिखा। इसे और स्पष्ट या अधिक कुशल बनाने का कोई तरीका हो तो बताने का अनुरोध किया। यह एक हाई-स्कूल छात्र की गणित-संबंधी व्याख्या है, इसलिए इसे उचित मात्रा में संदेह के साथ लेना चाहिए.

  • GJK एल्गोरिथ्म वीडियो: उसी एल्गोरिथ्म पर एक वीडियो प्रस्तुति का लिंक साझा किया। वीडियो लिंक

  • लेख की प्रशंसा: शानदार लेख है। बहुत स्पष्ट और रोचक.

  • convex optimization तुलना: दो convex sets के बीच intersection जाँचने का एक और तरीका यह है कि दो बिंदुओं के अंतर के norm को न्यूनतम करने वाली convex optimization समस्या हल की जाए। यदि optimal value 0 हो, तो sets में intersection है। GJK एल्गोरिथ्म और convex optimization पद्धति की तुलना देखना चाहूँगा। कौन बेहतर है, इस पर निश्चित नहीं हूँ.

  • लेख की प्रशंसा और गलतफ़हमी: शानदार लेख है। लेकिन पहली image non-convex shape के intersection को दिखाती है, जबकि बाद में पता चलता है कि एल्गोरिथ्म केवल convex shapes पर ही काम करता है.

  • GJK एल्गोरिथ्म पहली बार सुना: GJK एल्गोरिथ्म के बारे में पहली बार सुना.

  • संबंधित ब्लॉग पोस्ट: Minkowski geometry से संबंधित एक ब्लॉग पोस्ट लिखा था। ब्लॉग लिंक

  • व्यक्तिगत वेबसाइट: अप्रत्याशित रूप से ध्यान मिलने पर यह कहा कि उनकी निजी वेबसाइट मज़ाकों से भरी हुई है। संपर्क करना हो तो reply में बताने को कहा.

  • Minkowski फ़ंक्शन का उपयोग: openSCAD में Minkowski function का उपयोग करता रहा हूँ, और यह जानकर खुशी हुई कि वह वास्तव में क्या है.

  • एल्गोरिथ्म की प्रशंसा: कमाल का एल्गोरिथ्म है.