任意大小的凸多边形之间的碰撞检测算法 [英] Algorithms for Collision Detection between Arbitrarily sized Convex Polygons
问题描述
我正在研究小行星克隆。一切都是2D的，用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:
- 它不适用于凹面多边形，并且
- 对于边坡未定义的Edge情况有问题。
我确保所有多边形都是凸面的，并且已经写过代码来处理未定义的坡度问题（如果我们除以 0 ，则应该加倍返回 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）<之间来实现。 / code>（假设方向已标准化）。请注意，它归结为检查点是否属于多边形内的三角形。
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屋！
