
_START_ARTICLE_
خوارزمية كشف التصادم
_START_PARAGRAPH_
تعد خوارزمية المسافة Gilbert-Johnson-Keerthi طريقة لتحديد الحد الأدنى للمسافة بين مجموعتين محدبتين . على عكس العديد من خوارزميات المسافة الأخرى ، فإنه لا يتطلب تخزين بيانات الهندسة في أي تنسيق محدد ، ولكن بدلاً من ذلك يعتمد فقط على وظيفة دعم لإنشاء تكرارات بسيطة أقرب إلى الإجابة الصحيحة باستخدام مجموع Minkowski (CSO) لشكلين محدبين. _NEWLINE_تستخدم خوارزميات "GJK المحسّنة" معلومات الحافة لتسريع الخوارزمية باتباع الحواف عند البحث عن البساط التالي. هذا يحسن الأداء إلى حد كبير لل polytopes مع أعداد كبيرة من الرؤوس. _NEWLINE_غالبًا ما تستخدم خوارزميات GJK بشكل متزايد في أنظمة المحاكاة وألعاب الفيديو. في هذا الوضع ، يتم استخدام simplex النهائي من حل سابق كتخمين أولي في التكرار التالي ، أو "إطار". إذا كانت المواضع في الإطار الجديد قريبة من تلك الموجودة في الإطار القديم ، فسوف تتقارب الخوارزمية في تكرار واحد أو اثنين. ينتج عن ذلك أنظمة الكشف عن التصادم التي تعمل في وقت شبه ثابت. _NEWLINE_ثبات الخوارزمية والسرعة ومساحة التخزين الصغيرة تجعله شائعًا لاكتشاف التصادم في الوقت الفعلي ، وخاصة في محركات الفيزياء لألعاب الفيديو .
_START_SECTION_
شبة الكود
_START_PARAGRAPH_
function GJK_intersection(shape p, shape q, vector initial_axis):_NEWLINE_       vector  A = Support(p, initial_axis) - Support(q, -initial_axis)_NEWLINE_       simplex s = {A}_NEWLINE_       vector  D = -A_NEWLINE_       loop:_NEWLINE_           A = Support(p, D) - Support(q, -D)_NEWLINE_           if dot(A, D) < 0:_NEWLINE_              reject_NEWLINE_           s = s ∪ A_NEWLINE_           s, D, contains_origin = NearestSimplex(s)_NEWLINE_           if contains_origin:_NEWLINE_              accept