直观理解GJK算法

GJK 算法步骤选取初始方向初始方向可以是两个多边形的中心点构成的矢量也可以是两个多边形各自选取一个顶点构成的矢量还可以是给定的任意矢量根据初始方向用 Support 函数得到第一个 support 点并放到单纯形simplex中将初始方向取反作为下一次迭代方向循环开始a) 根据迭代方向和 Support 函数计算出一个新的 support 点b) 若新的 support 点与迭代方向的点乘结果小于 0说明在这个迭代方向上已经无法找到一个能够跨越原点的 support 点了。也就是说无法组成一个能够包含原点的单纯形。即两个多边形不相交函数退出c) 若新的 support 点能够跨越原点则将其加到 simplex 中d) NearestSimplex 函数用来更新单纯形和迭代方向并判断 simplex 是否包含原点。这时 simplex 有两个点或三个点若为两个点则这两个点构成一条直线以该直线的垂线朝向原点的方向作为下一次迭代方向若为三个点则需要判断这三个点组成的三角形是否包含原点。若不包含则保留离原点最近的边上的两个点同样以这两个点的直线的垂线朝向原点的方向作为下一次迭代方向回到循环的开始步骤 a。为什么:闵可夫斯基和定义和性质定义两个点p1​(x1​,y1​)和p2​(x2​,y2​)的闵可夫斯基加法是向量加法即p1​p2​(x1​x2​,y1​y2​)。 对于二维平面上两个图形A和B定义A和B的闵可夫斯基和为 ABC{ab∣a∈A,b∈B} 特殊地对于两个凸多边形A,B他们 的闵可夫斯基和有特殊的性质 交换律ABBA 结合律(AB)CA(BC) 凸集封闭性若 A,B 均为凸集则 AB 也是凸集。 平移不变对任意向量 t有 (At)BABt。 凸包关系conv(AB)conv(A)conv(B)。 AB的顶点数等于这两个凸多边形每条有向边向量角的种类数。 AB的周长总等于这两个凸多边形的周长之和。两个凸多边形A和B闵可夫斯基差A-B理解为: 取凸多边形B, 先让B的每个顶点各坐标轴取反(按原点对称), 然后A沿着B的每个边扫过得到的区域。因此此时闵可夫斯基差同样为凸多边形。可知闵可夫斯基差等价于闵可夫斯基和等价于求闵可夫斯基和包含原点问题。此时问题转换为高效判断间接计算得到的凸多边形是否包含原点。GJK算法中采取了类似二分排除法的方式逐步迭代排除不包含原点的范围收缩得到包含原点的单纯形范围。由于每步迭代都会排除一部分顶点因此可以保证有限步收敛性质。如何判定最远点有没有越过原点:若 s 在 d 方向上的投影小于 0即 d⋅s0说明 A−B 中没有点能到达原点两凸集不相交算法终止。最远点s点坐标作为向量和方向向量d点乘, 值小于0说明s在d方向的投影没有在投射方向上达到原点在d方向上的投影位置。