https://blog.lufei.so/#/collisionDetection/GJK/1
https://blog.lufei.so/#/collisionDetection/GJK/2
现实世界里我们对于是否碰撞的判断可以说极其容易而且准确，比如下图。在二进制的世界里，一切就没这么直观了。
GJK(Gilbert-Johnson-Keerthi Distance Algorithm)
GJK就是此次要实现的碰撞检测算法。如果对碰撞算法有过了解的话，大概率听过另一个碰撞检测算法SAT(Separating Axis Theorem)。
GJK相较于SAT有什么优点吗？
- 快
- 简单
实际上就我目前了解的碰撞检测算法，应用对象都是凸多边形(Convex polygon)。如果不是凸多边形，问题也不大，可以事先分割。
游戏里对于不规则物体，我们通常都是借助工具生成顶点数据。此时生成的数据通常都是处理过的(凹多边形被分解)，如果你想了解更多关于凹多边形分解的知识，可以参考这两个库：poly-decomp.js，earcut。
Minkowski Difference
由于不知道Min到底是“明”还是“闵”，所以下面都用MD表示了。
MD是GJK算法的理论基础。那么到底什么是MD？
假设有两个凸多边形：
s1 =[{x:1, y:10},{x:3, y:10},{x:3, y:8},{x:1, y:8}]
s2 =[{x:2, y:9},{x:4, y:7},{x:2, y:7}]那么它们的位置看起应该像下图这样。
MD就是s1与s2所有点的差形成的集合。
MD(s1, s2):
s3 =[]for p1 in s1:for p2 in s2:
s3.push(p1 - p2)return s3MD(s1, s2)=>[{x:-1, y:1},{x:-3, y:3},{x:-1, y:3},{x:1, y:1},{x:-1, y:3},{x:1, y:3},{x:1, y:-1},{x:-1, y:1},{x:1, y:1},{x:-1, y:-1},{x:-3, y:1},{x:-1, y:1}]这些点的布局如下图所示：
关键的地方来了。首先要介绍一个新的概念叫Convex Hull。
Convex hull是包含点集的最小凸多边形。拿上面的例子来说：
铺垫了这么久，现在可以说结论了。
我们把s1 - s2点集形成的Convex hull命名为s3。如果s3包含点(0, 0)，那么s1和s2发生碰撞。
有没有觉得很简单？对，原理就是这么简单。
至于怎么算出点集的Convex hull，翻译自维基百科的Gift wrapping algorithm。
functionwrap(points){const hull =[]let current ={x:Infinity}for(const p of points){if(p.x < current.x) current = p
}let i =0, end
while(true){
hull[i]= current
end = points[0]for(let j =1; j < points.length; j++){if((end.x === current.x && end.y === current.y)||inline(points[j], hull[i], end)>0){
end = points[j]}}
i +=1
current = end
if(end.x === hull[0].x && end.y === hull[0].y)break}return hull
}Gift wrapping algorithm是获取Convex hull的一种算法，不是效率最高的但应该是最易懂的。
最后就是判断点是否在多边形内的算法了，可以看我之前的文章。
交互示例
思考
有小伙伴不禁要问：这样的嵌套循环真的比SAT快？确实，上面的实现并不是真正意义上的GJK算法。但是核心思想是一样的：
如果两个凸多边形的Minkowski Difference所形成的Convex hull包含点(0, 0)，那么这两个凸多边形相交。
怎么优化这个实现呢？
我们并不需要计算两个凸多边形所有点的Minkowski Difference。还是文章开始的例子：
我们只需要尽早的从已知的条件里判断出是否包含原点即可。
比如：如果获取到的第一个点刚好是原点，说明相交停止循环，否则继续获取下一个点，如果原点在两点的连线上，说明相交停止循环，否则继续获取下一个点。
真正的GJK算法用了一个很取巧的方式来减少循环次数，而且效果很理想。当然这也是下篇文章里的内容了。
感兴趣的小伙伴也可以从下面的参考资料里先尝试一波。
参考资料
- https://blog.hamaluik.ca/posts/building-a-collision-engine-part-1-2d-gjk-collision-detection/
- http://www.dyn4j.org/2010/04/gjk-gilbert-johnson-keerthi/
- https://cse442-17f.github.io/Gilbert-Johnson-Keerthi-Distance-Algorithm/
国际惯例先放图。
GJK是怎么快速判断出这两个图形是否碰撞的呢？
Support Function
Support Function用来计算凸体在给定方向上的最远点。什么意思呢？
代码片段
图示中的例子带入，可以得到(9, 6) = (0, 4) - (-9, -2)，正是图二三角形的一个顶点。
将方向取反再调用getSupport，我们可以得到(-1, -2) = (-6, 0) - (-5, 2)，也是图二三角形的一个顶点。
这样做的意义是什么呢？因为可以确保我们所取的两个点跨度足够大，有更大的概率包含原点，减少循环次数。
那么问题来了：
初始给定的方向是怎么来的？
随机。更推荐的是凸体中心的差：
direction = shapeA.center - shapeB.center。已经获取了两个点，那么第三个点如何确定呢？
通过
a(9, 6)，b(-1, -2)，可以计算出垂直于向量ab(-10, -8)且指向原点方向的向量，这个向量将会作为direction来获取第三个点。
这里要用到向量积来计算出
代码片段direction。
核心算法
获取到三个点后，我们需要判断原点的是否在这三个所形成的多边形内。如果在说明碰撞，不在则剔除一个点后继续寻找下一个点。
上面这种情况：w * AO > 0，说明原点在AB外部，则剔除点C并以w为direction继续寻找下一个点。
上面这种情况：w * AO < 0，说明原点在AB内部，则验证剩余的边（实际上不需要验证所有的边）。假如我开始获取到的两个点是B，C，则我们只需要验证AB，AC，因为原点一定在BC内部。
这里的关键点在于：如何计算出垂直于AB且指向远离点C的方向的向量w？
直接贴代码了，毕竟也解释不了为何是这样的运算顺序。
代码片段
交互示例
上面只是介绍了我觉得实现GJK算法中比较重要的点。整个流程可能并不够清晰，所以这里附上完整的步骤分解示例。
总结
GJK算法并不复杂，完整的代码不到200行。主要用到的数学知识是数量积和向量积。