6

我正在研究小行星克隆。一切都是 2D 的，并且是用 C++ 编写的。

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

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

我已经编写并实现了所有内容，并且碰撞检测工作正常......大部分时间。当屏幕上有明显的碰撞时它会随机失败，有时当没有任何东西接触时会显示碰撞。要么我在某个地方搞砸了我的实现，要么我的算法很糟糕。由于我的实现的大小/范围（在几个源文件中），我不想打扰你，只是想让有人检查我的算法实际上是否合理。到那时，我可以进行一次大型的错误搜索。

算法：

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

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

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

我已经确保所有多边形都是凸的，并且已经编写了代码来处理未定义的斜率问题（NAN如果我们除以，则双精度应该返回0，所以很容易测试）。

那么，这应该工作吗？

4

2 回答 2

7

这个问题的标准解决方案是使用分离轴定理（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
于 2013-01-31T16:33:27.063 回答
2

我做了类似于计算多边形交点的事情，即查找顶点是否位于给定多边形内。

您的算法是合理的，并且确实不适用于凹多边形。您选择的线表示在接近无穷大的斜率处也存在问题。我选择使用几个向量，一个用于线方向，一个用于线上的参考点。从这些，我可以很容易地推导出线的参数化方程，并以各种方式使用它来找到与其他形状的交点。

P = S +  t * D

给定上述关系，线的任何点 P 都可以通过其在线上的坐标 t 来表征，其中 S 是参考点，D 是方向向量。

由于方向方向，这种表示可以让您轻松定义平面的哪些部分是正部分和负部分（即在线上方和下方）。现在，平面的任何区域都可以定义为多条线的负子平面或正子平面的交点。因此，您的“多边形内的点”算法可以稍微更改以使用该表示，并增加所有方向指向顺时针方向的约束，并测试该点是否位于所有线的负子平面中（所以你不需要多边形的中心了）。

我使用的线计算点的边的公式如下：

(xs - xp) * yd - (ys - yp) * xd

当点 P 接近 S 时，这里会出现斜率问题。

可以使用边缘顶点计算该表示，但为了获得正确的子平面，您必须以连续顺序保持多边形中的顶点。

对于凹多边形，问题有点复杂：简单地说，您必须测试该点是否位于两个连续的凸边之间。这可以通过检查投影到边缘上的点的坐标来实现，并确保它位于0和之间length(edge)（假设方向是标准化的）。请注意，归结为检查点是否属于多边形内的三角形。

于 2013-01-31T18:39:28.793 回答