How do I determine if two convex polygons intersect?
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.
Answer
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.
