c++ - 任意大小的凸多边形之间的碰撞检测算法

Question

我正在研究小行星克隆。一切都是二维的，用 C++ 编写。

对于小行星，我正在生成随机的 N 边多边形。我保证它们是凸的。然后我旋转它们，给它们一个旋转速度，让它们在太空中飞翔。一切正常，而且非常漂亮。

对于碰撞，我使用的是我自己想到的算法。这可能是个坏主意，如果到了紧要关头，我可能会放弃整个事情并在互联网上找到教程。

我已经编写并实现了所有内容，并且碰撞检测工作正常......大部分时间。当屏幕上有明显的碰撞时它会随机失败，并且有时在没有任何东西接触时指示碰撞。要么我在某个地方搞砸了我的实现，要么我的算法很糟糕。由于我实现的规模/范围(超过几个源文件)，我不想为此打扰你，只是希望有人检查我的算法实际上是否合理。到那时，我可以继续寻找大漏洞。

算法:

对于每颗小行星，我都有一个函数可以输出绘制小行星时每个顶点的位置。对于每对相邻的顶点，我为它们所在的线生成公式，y=mx+b 格式。然后我从我的飞船顶点之一开始，测试该点以查看它是否在小行星内部。我首先插入点的 X 坐标，然后将输出与实际 Y 值进行比较。这告诉我该点是在线上方还是在线下方。然后我对小行星的中心做同样的事情，以确定线的哪一半被认为是小行星的“内部”。然后我对每对顶点重复。如果我找到一条线，我的点不在小行星中心的同一侧，我知道没有碰撞，并退出对该点的检测。由于我的船上有 3 个点，因此我必须测试下一个点。如果所有 3 个点都提前退出，那么船上的任何点都没有碰撞，我们就完成了。如果任何一点都被小行星组成的线所包围，那么它就在小行星内部，并且碰撞标志被设置。

我发现这个算法的两个问题是:

1. 它不适用于凹多边形，并且
2. 它在斜率未定义的边缘情况下存在问题。

我已经确保所有的多边形都是凸面的，并且已经编写了代码来处理未定义的斜率问题(如果我们除以 0，doubles 应该返回 NAN，所以它很漂亮很容易对此进行测试)。

那么，这应该行得通吗？

Answer 1

此问题的标准解决方案是使用分离轴定理 (SAT)。给定两个凸多边形 A 和 B，算法基本上是这样的:

for each normal N of the edges of A and B
    intervalA = [min, max] of projecting A on N
    intervalB = [min, max] of projecting B on N
    if intervalA doesn't overlap intervalB
        return did not collide
return collided