现实世界里我们对于是否碰撞的判断可以说极其容易而且准确，比如下图。在二进制的世界里，一切就没这么直观了。

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},