任意大小凸多边形碰撞检测算法

Question

我正在研究小行星克隆.一切都是2D,用C++编写.

对于小行星,我正在生成随机的N边多边形.我保证他们是Convex.然后我旋转它们,让它们旋转速度,让它们飞过太空.这一切都有效,非常漂亮.

对于碰撞,我使用的是我自己想到的算法.这可能是一个坏主意,如果推动,我可能会废弃整个事情,并在互联网上找到一个教程.

我已经编写并实现了所有内容,并且碰撞检测工作正常....大部分时间.当屏幕上明显发生碰撞时,它会随机失败,有时会在没有任何触摸时指示碰撞.我要么在某处扯下我的实现,要么我的算法很糟糕.由于我的实现的大小/范围(通过几个源文件),我不想打扰你,只是想让某人检查我的算法实际上是合理的.那时我可以继续寻找一个大虫子.

算法:

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

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

1. 它不适用于凹多边形,并且
2. 在Slope未定义的Edge情况下存在问题.

我已经确保所有多边形都是凸面的,并且已经编写了代码来处理未定义的斜率问题(NAN如果我们除以0,则应该双重返回,因此很容易测试它).

那么,这应该有用吗？

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

Answer 2

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

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

P = S +  t * D

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

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

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

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

当 P 点靠近 S 时，就会出现斜率问题。

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

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