如何确定两个凸多边形是否相交？ [英] How do I determine if two convex polygons intersect?

问题描述

假设在一个平面上有许多凸多边形，也许是一张地图。这些多边形可以相互碰撞并分享边缘，但不能重叠。

P 和 Q 是否重叠，首先我可以在 P 中测试每条边，看它是否与 Q 中的任何边相交。如果找到交点，我声明 P 和 Q 相交。如果没有相交，那么我必须测试 P 完全被 Q 包含的情况，反之亦然。接下来，就是 P == Q 的情况。最后，有这样的情况，分享一些优势，但不是全部。 （后两种情况可能被认为是相同的一般情况，但这可能并不重要。）

我有一种算法可以检测两条线段相交的位置。如果这两个部分是共线的，他们不会被认为是相交的。

我是否正确列举了这些情况？任何建议测试这些案件？

请注意，我不想找到新的凸多边形是交集，我只想知道是否存在交集。有很多有据可查的算法可以找到相交点，但我不需要花费所有的努力。

可以使用这种碰撞算法 ：

为了能够决定两个凸多边形是否相交（相互接触），我们可以使用分离轴定理。从本质上讲：

• 如果两个凸多边形不相交，则会在它们之间传递一条直线。


• 如果其中一个多边形的其中一边形成这样一条线，则只存在这样一条线。

第一条语句很简单。由于多边形都是凸起的，因此除非它们相交，否则可以在一侧绘制一条多边形，而另一侧绘制另一条多边形。第二个稍微不太直观。请看图1.除非最接近的多边形彼此平行，否则它们彼此最接近的点是一个多边形的一个角与另一个多边形的一侧最接近的点。这边将在多边形之间形成一个分离轴。如果两边平行，它们都是分离轴。

那么这个具体的帮助我们决定多边形A和B是否相交呢？那么，我们只是遍历每个多边形的每一边，并检查它是否形成一个分离轴。要做到这一点，我们将使用一些基本的矢量数学来压缩两个多边形的所有点到垂直于潜在分离线的线上（见图2）。现在整个问题都很方便。我们可以确定每个多边形的点所在的区域，如果这些区域不重叠，则这条线是一个分离轴。 //i.stack.imgur.com/CNeSx.pngalt =>

如果在检查两个多边形中的每条线之后没有找到分离轴，已经证明多边形相交并且必须做些什么。

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.

解决方案

You could use this collision algorithm:

To be able to decide whether two convex polygons are intersecting (touching each other) we can use the Separating Axis Theorem. Essentially:

• If two convex polygons are not intersecting, there exists a line that passes between them.
• Such a line only exists if one of the sides of one of the polygons forms such a line.

The first statement is easy. Since the polygons are both convex, you'll be able to draw a line with one polygon on one side and the other polygon on the other side unless they are intersecting. The second is slightly less intuitive. Look at figure 1. Unless the closest sided of the polygons are parallel to each other, the point where they get closest to each other is the point where a corner of one polygon gets closest to a side of the other polygon. This side will then form a separating axis between the polygons. If the sides are parallel, they both are separating axes.

So how does this concretely help us decide whether polygon A and B intersect? Well, we just go over each side of each polygon and check whether it forms a separating axis. To do this we'll be using some basic vector math to squash all the points of both polygons onto a line that is perpendicular to the potential separating line (see figure 2). Now the whole problem is conveniently 1-dimensional. We can determine a region in which the points for each polygon lie, and this line is a separating axis if these regions do not overlap.

If, after checking each line from both polygons, no separating axis was found, it has been proven that the polygons intersect and something has to be done about it.

这篇关于如何确定两个凸多边形是否相交？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！