gjk 算法 c++

GJK算法（Gilbert-Johnson-Keerthi算法）是一种用于求解凸体相交的算法，其用途广泛应用在物理引擎、碰撞检测和计算机图形学等领域。

GJK算法的基本思想是通过迭代逼近的方式，在高维空间中找到两个凸体是否相交的最近点对，从而确定它们是否相交。具体来说，GJK算法分为三个主要步骤：

1. 初始化：选择两个初始点，一个位于第一个凸体上，一个位于第二个凸体上。这两个点可以是凸体的顶点、边界上的任意一点。

2. 迭代逼近：根据Minkowski差集（两个凸体的差集）形成的新凸体，找到离原点最近的点。该最近点必然位于Minkowski差集的边界上，可以通过求解凸包或者线段相交等方法来寻找。

3. 更新凸体：如果最近点距离原点足够小，说明两个凸体相交；否则，将最近点加入到Minkowski差集，进行下一轮迭代逼近。

由于GJK算法通过在高维空间中进行求解，虽然只需要两个凸体的形状信息，但能够得到相交的最近点对，进而支持接触深度、碰撞法向量等额外的信息。此外，GJK算法具有高效、可扩展性好等优点，因此被广泛应用于各种实时计算几何问题中。

总之，GJK算法是一种高效的求解凸体相交的算法，通过迭代逼近的方式找到相交的最近点对，其具有应用广泛的优势，可用于物理引擎、碰撞检测和计算机图形学等领域。