如何判断两个凸多边形是否相交？
假设一个平面（也许是一张地图）上有许多凸多边形。 这些多边形可以相互碰撞并共享一条边，但不能重叠。
要测试两个多边形 P 和 Q 是否重叠，首先，我可以测试 P 中的每条边，看看它是否与 Q 中的任何边相交。 如果找到交集，我声明 P 和 Q 相交。 如果没有相交，那么我必须测试 P 完全包含在 Q 中的情况，反之亦然。 接下来是P==Q的情况。 最后，还有一种情况有一些共同点，但不是全部。 （最后两种情况可能被认为是相同的一般情况，但这可能并不重要。）
我有一个算法可以检测两条线段相交的位置。 如果这两个线段共线，则出于我的目的，它们不被视为相交。
我是否正确地列举了这些案例？ 对这些情况进行测试有什么建议吗？
请注意，我并不是要寻找作为交点的新凸多边形，我只是想知道是否存在交点。 有许多记录良好的算法用于查找交集，但我不需要付出所有努力。
Suppose there are a number of convex polygons on a plane, perhaps a map. These polygons can bump up against each other and share an edge, but cannot overlap.
To test if two polygons P and Q overlap, first I can test each edge in P to see if it intersects with any of the edges in Q. If an intersection is found, I declare that P and Q intersect. If none intersect, I then have to test for the case that P is completely contained by Q, and vice versa. Next, there's the case that P==Q. Finally, there's the case that share a few edges, but not all of them. (These last two cases can probably be thought of as the same general case, but that might not be important.)
I have an algorithm that detects where two line segments intersect. If the two segments are co-linear, they are not considered to intersect for my purposes.
Have I properly enumerated the cases? Any suggestions for testing for these cases?
Note that I'm not looking to find the new convex polygon that is the intersection, I just want to know if an intersection exists. There are many well documented algorithms for finding the intersection, but I don't need to go through all the effort.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
这是一个想法：
找到每个多边形的中心点
找到每个多边形中最接近另一个多边形中心点的两个点。 它们将是凸多边形中的相邻点。 这些定义了每个多边形的最近边缘，我们将点称为 {A, B} 和 {Y, Z}
找到线 AB 和 YZ 的交点。 如果线段交叉（AB 上的交点位于 A 和 B 之间），则多边形相交。 如果AB和XY平行，忽略这个条件，下一步就会陷入困境。
您还需要检查另一种情况，即当多边形相交足够严重时，AB 和 XY 完全相互交叉并且实际上并不相交。
要捕获这种情况，请计算 AB 和 XY 到每个多边形中心点的垂直距离。 如果任一中心点更接近相对多边形的线段，则多边形会严重重叠。
Here's an idea:
Find the center point of each polygon
Find the two points of each polygon closest to the center point of the other. They will be adjacent points in convex polygons. These define the nearest edge of each polygon, let's call the points {A, B} and {Y, Z}
Find the intersection of lines AB and YZ. If the line segments cross (the intersection on AB lies between A and B), your polygons intersect. If AB and XY are parallel ignore this condition, the next step will trap the problem.
There is one more case you need to check for, which is when the polygons intersect heavily enough that AB and XY are completely past each other and don't actually intersect.
To trap this case, calculate the perpendicular distances of AB and XY to each polygons center points. If either center point is closer to the opposite polygon's line segment your polygon overlap heavily.
您可以使用此碰撞算法：
You could use this collision algorithm:
有多种方法可以检测凸多边形之间的相交和/或包含。 这完全取决于您希望算法的效率如何。 考虑两个分别具有 r 和 b 顶点的凸多边形 R 和 B：
There are several ways to detect intersection and / or containment between convex polygons. It all depends on how efficient you want the algorithm to be. Consider two convex polygons R and B with r and b vertices, respectively:
如果多边形总是凸的，首先计算从多边形中心到中心绘制的直线的角度。 然后，您可以消除测试与其他多边形成 180 度的多边形的一半的边缘段的需要。
要消除边缘，请从左侧的多边形开始。 从多边形中心取与前一个项目符号的线段垂直的线段，并接触多边形的两侧。 将此线段称为 p，其顶点为 p1 和 p2。 然后，对于所有顶点，如果x坐标小于p1.x和p2.x，则该顶点可以进入“安全桶”。
如果没有，您必须检查以确保它位于线路的“安全”一侧（也只需检查 y 坐标）
- 如果多边形中的线段的所有顶点都在“安全桶”中，则可以忽略它。
-反转极性，以便第二个多边形“向右”。
if the polygons are always convex, first calculate the angle of a line drawn from center to center of the polygons. you can then eliminate needing to test edge segments in the half of the polygon(s) 180 degrees away from the other polygon(s).
to eliminate the edges, Start with the polygon on the left. take the line segment from the center of the polygon that is perpendicular to the line segment from the previous bullet, and touches both sides of the polygon. call this line segment p, with vertexes p1 and p2. Then, for all vertexes if the x coordinate is less than p1.x and p2.x That vertex can go in the "safe bucket".
if it doesn't, you have to check to make sure it is on the "safe" side of the line (just check the y coordinates too)
-if a line segment in the polygon has all vertexes in the "safe bucket" you can ignore it.
-reverse the polarity so you are "right oriented" for the second polygon.
GJK 碰撞 检测 应该 工作。
GJK collision detection should work.
由于 altCognito 已经给了你一个解决方案，我只会指出一本关于计算几何的优秀书籍 您可能感兴趣。
Since altCognito already gave you a solution, I'll only point out an excellent book on computational geometry that might interest you.
您的测试用例应该有效，因为您正在检查多边形根本不相交（完全在外部或完全在内部）的情况，以及存在任何形式的部分相交的情况（如果存在重叠，边缘总是相交） 。
对于测试，我只是确保测试每个可能的组合。 从我所看到的上面缺少的是共享单边，但一个多边形包含在另一个多边形中。 我还会添加对一些更复杂的多边形形状的测试，从 tri -> 多方面的，只是作为预防措施。
另外，如果你有一个 U 形聚合物完全包围聚合物，但不重叠，我相信你的情况可以处理这个问题，但我也会将其添加为检查。
Your test cases should work, since you're checking the case where the polygons don't intersect at all (completely outside or completely inside), as well as where there is any form of partial intersection (edges intersect always if there is overlap).
For testing, I would just make sure to test every potential combination. The one missing above from what I see is a single edge shared, but one poly contained in the other. I would also add tests for some more complex poly shapes, from tri -> many sided, just as a precaution.
Also, if you had a U shaped poly that completely surrounded the poly, but didn't overlap, I believe your case would handle that, but I would add that as a check, as well.