任意大小凸多边形之间的碰撞检测算法 [英] Algorithms for Collision Detection between Arbitrarily sized Convex Polygons
问题描述
我正在研究一个小行星克隆.一切都是二维的，用 C++ 编写.
I am working on an asteroids clone. Everything is 2D, and written in C++.
对于小行星，我正在生成随机的 N 边多边形.我保证它们是凸的.然后我旋转它们，给它们一个旋转速度，让它们飞过太空.一切正常，而且非常漂亮.
For the asteroids, I am generating random N-sided polygons. I have guaranteed that they are Convex. I then rotate them, give them a rotspeed, and have them fly through space. It all works, and is very pretty.
对于碰撞，我使用的是我自己想到的算法.这可能是个坏主意，如果迫不得已，我可能会废弃整个内容并在互联网上找到教程.
For collision, I'm using an Algorithm I thought of myself. This is probably a bad idea, and if push comes to shove, I'll probably scrap the whole thing and find a tutorial on the internet.
我已经编写并实现了所有内容，并且碰撞检测工作正常......大部分时间.当屏幕上明显发生碰撞时，它会随机失败，有时在没有任何接触时指示碰撞.要么我在某处搞砸了我的实现，要么我的算法很糟糕.由于我的实现(在多个源文件上)的大小/范围，我不想打扰你，只是想让有人检查我的算法实际上是合理的.到时候我就可以进行一次大的 bug 搜索了.
I've written and implemented everything, and the collision detection works alright.... most of the time. It will randomly fail when there's obviously a collision on screen, and sometimes indicate collision when nothing is touching. Either I have flubbed my implementation somewhere, or my algorithm is horrible. Due to the size/scope of my implementation (over several source files) I didn't want to bother you with that, and just wanted someone to check that my algorithm is, in fact, sound. At that point I can go on a big bug hunt.
对于每个小行星，我有一个函数可以输出绘制小行星时每个顶点的位置.对于每对相邻的顶点，我为它们所在的线生成公式，y=mx+b 格式.然后我从我的一个飞船顶点开始，测试那个点，看看它是否在小行星内部.我首先插入点的 X 坐标，并将输出与实际 Y 值进行比较.这告诉我该点是在线上还是线下.然后我对小行星的中心做同样的事情，以确定这条线的哪一半被认为是小行星内部".然后我对每对顶点重复.如果我找到一条线，我的点与小行星的中心不在同一侧，我知道没有碰撞，并退出该点的检测.由于我的船上有 3 个点，因此我必须测试下一个点.如果所有 3 个点都提前退出，那么船上的任何点都不会发生碰撞，我们就完成了.如果任何一点被小行星组成的线四面包围，那么它就在小行星内部，并且设置了碰撞标志.
For each Asteroid, I have a function that outputs where each vertex should be when drawing the asteroid. For each pair of adjacent Vertices, I generate the Formula for the line that they sit on, y=mx+b format. I then start with one of my ships vertices, testing that point to see whether it is inside the asteroid. I start by plugging in the X coordinate of the point, and comparing the output to the Actual Y value. This tells me if the point is above or below the line. I then do the same with the Center of the Asteroid, to determine which half of the line is considered "Inside" the asteroid. I then repeat for each pair of Vertices. IF I ever find a line for which my point is not on the same side as the center of the asteroid, I know there is no collision, and exit detection for that point. Since there are 3 points on my ship, I then have to test for the next point. If all 3 points exit early, then There are no collisions for any of the points on the ship, and we're done. If any point is bound on all sides by the lines made up by the asteroid, then it is inside the asteroid, and the collision flag is set.
我发现这个算法的两个问题是:
The two Issues I've discovered with this algorithm is that:
- 它不适用于凹多边形，并且
- 它在斜率未定义的边缘情况下存在问题.
我已经确保所有的多边形都是凸的，并且已经编写了代码来处理未定义的斜率问题(如果我们除以 0，doubles 应该返回 NAN，所以它很漂亮易于测试).
I have made sure all polygons are Convex, and have written code to handle the Undefined Slope issue (doubles SHOULD return NAN if we divide by 0, so it's pretty easy to test for that).
那么，这应该可行吗?
推荐答案
我做了一些类似于计算多边形相交的事情，即查找顶点是否位于给定的多边形内.
I did something similar to compute polygon intersections, namely finding if a vertex sits within a given polygon.
您的算法是合理的，并且确实不适用于凹多边形.您选择的线表示在接近无穷大的斜坡上也有问题.我选择使用几个向量，一个用于线方向，一个用于线上的参考点.从这些，我可以很容易地推导出一条线的参数化方程，并以各种方式使用它来找到与其他形状的交点.
Your algorithm is sound, and indeed does not work for concave polys. The line representation you chose is also problematic at slopes approaching infinity. I chose to use a couple of vectors for mine, one for the line direction, and one for a reference point on the line. From these, I can easily derive a parameterized equation of the line, and use that in various ways to find intersections with other shapes.
P = S + t * D
直线上的任意一点 P 都可以用它在直线上的坐标 t 来表示，给定上述关系式，其中 S 是参考点，D 是方向向量.
Any point P of the line can be caracterized by its coordinate t on the the line, given the above relation, where S is the reference point, and D the direction vector.
这种表示方式让您可以轻松定义平面的哪些部分是正的和负的(即在线上方和下方)，这要归功于方向.现在，平面的任何区域都可以定义为几条线的负子平面或正子平面的交点.因此，您的多边形内点"算法可以稍微更改以使用该表示，并添加所有方向顺时针指向的约束，并测试该点是否位于所有线的负子平面中(因此您不需要不再是多边形的中心).
This representation lets you easily define which parts of the plane is the positive and the negative one (ie. above and below the line), thanks to the direction orientation. Now, any region of the plane can be defined as an intersection of several lines' negative or positive subplanes. So your "point within polygon" algorithm could be slightly changed to use that representation, with the added constraint of all the direction pointing clockwise, and testing for the point being in the negative subplane of all the lines (so you don't need the centre of the polygon anymore).
我使用的计算点与直线的边的公式如下:
The formula to compute the side of a point wrt a line I used is the following:
(xs - xp) * yd - (ys - yp) * xd
当 P 点靠近 S 时，这里出现斜率问题.
The slope issue appears here when point P is close to S.
可以使用边顶点来计算该表示，但是为了获得正确的子平面，您必须以连续顺序将顶点保留在多边形中.
That representation can be computed using the edge vertices, but in order to have correct subplanes, you must keep your vertices in your polygon in condecutive orders.
对于凹多边形，问题有点复杂:简而言之，您必须测试该点是否位于两个连续的凸边之间.这可以通过检查投影在边缘上的点的坐标来实现，并确保它位于 0 和 length(edge) 之间(假设方向是标准化).请注意，它归结为检查该点是否属于多边形内的三角形.
For concave polygons, the problem is a bit more complicated: briefly, you have to test that the point is between two consecutive convex edges. This can be achieved by checking the coordinate of the point on the edge when projected on it, and ensuring it stands between 0 and length(edge) (assuming that the direction is normalized). Note that it boils down to check if the point belongs to a triangle within the polygon.
这篇关于任意大小凸多边形之间的碰撞检测算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
