GJK(Gilbert–Johnson–Keerthi) algorithm

.جی جی کی یکی از معروفترین الگوریتم هایی هست که برای تشخیص برخورد اشکال هندسی محدب به کار میره(دو بعدی و سه بعدی) ، و این بهترین آموزشی بود که ازش پیدا کرد :
http://s5.picofile.com/file/8114232500/The_Gilbert.pdf.html

این تصویر هم به فهم مساله کمک میکنه (برای دیدن تصویر اصلی روی عکس کلیک کنید):

نظریه محور مجزا ساز -SAT-Separating Axis Theorem

این متد برای تشخیص برخورد اشکال محدب convex بکار میره، اما برای اشکال مقعر concave هم میشه به کار برد(تقسیم اشکال) کل الگوریتم اینو میگه که : " وقتی دو شکل  با هم برخوردی ندارن ، حد اقل یک محور وجود داره که سایه ی شکل روی اونها با هم تداخل ندارن".

در کل اینجوری میتونیم بگیم  که "دو جسم با هم برخورد دارن مگر اینکه خلافش ثابت بشه".
یا اینکه دو جسم با هم برخورد دارن اگر و فقط اگر که بر روی همه محور ها همپوشانی داشته باشند.

 

برای هر شکل یک سری محور وجود داره که باید اشکال رو روی تک تک اون محور ها تصویر کنیم اگه تصویر دو شکل روی محوری با هم تداخل نداشت یعنی برخوردی وجود نداره وباید از پردازش بیرون بیاد برناممون.