圆形和多边形情况下的GJK算法

Question

我想知道是否可以修改 GJK，以便我可以用它来检测圆和 n 点多边形之间的碰撞。
我之前实现了多边形和多边形，并尝试修改支持函数（以获取圆的最远点），但显然，这会导致无限循环。
这可以吗？除了支持功能之外，我还需要更改其他内容吗？ （因为我没看到）

这是我用来获得圆中最远点的方法

maxPointCircle = new Vector2(circle.center).add(new Vector2(direction).mul(circle.radius));

Answer 1

GJK算法实际上告诉你两个多边形之间的最小距离（当距离为0时，就是碰撞）。 因此，对于多边形和圆，您可以使用 GJK 找到该多边形与圆中心点之间的最小距离，然后将该距离与圆的半径进行比较。如果距离小于或等于半径，则为碰撞。

算法如下：

collision(polygon1, circle):
  polygon2 = dummy polygon of only one point, which is the center of the circle
  distance = GJK(polygon1, polygon2)
  if distance <= circle.radius:
    return true
  else:
    return false

Answer 2

您的无限循环可能是因为您基本上总是可以（至少达到机器精度）在圆上找到另一个点，该点位于原点之间并且比之前的点稍微靠近原点。要么在您检查的迭代次数中添加固定限制（例如 100），要么在迭代之间距离结果没有显着变化时添加终止条件（例如 1e-4 等的相对变化）。

特别对于圆（或与圆卷积的任何凸多边形），lavin 的答案基本上是最佳方法。对于更一般的圆凸形状（椭圆形、具有不同半径的圆的凸包、圆扇形等），您将不得不求助于我的建议。