How do I determine if two convex polygons intersect?

Question

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.

Meuse

Beware of floating-point precision problems when deciding colinearity of non-vertical, non-horizontal line segments, should you choose to go that way. – Illative

check out this answer from math.stackexchange which explains the algorithm, which is also referenced here – Beggar

Answer 1

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.

Palaestra

Unfortunately the site you are referencing in your answer has now closed down; you may want to either change the link or remove it from your answer. – Usual

Fortunately the page has been saved by the Wayback Machine. Please donate to the internet archive if this answer helped you. – Palaestra

While checkin if the edge E forms a separating line, the perpendicalar/projection part can be replaced by a vectorial-product (determinant in 2 dimensions) computation, which is easier IMO : All the vertex of the polygon A lie in the same side of E (i.e same sign of the determinant) and all the vertex of the polygon B lie in the other side of E. (the other sign of determinant). – Pessimism

"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 is incorrect. The pair of points, one in A and one in B, that are the closest to each other, may be two corner points. – Conflict

If you have two quadratangles, you don't even have to find the convex hull first, just check for each side if the remaining points of the quadratangle are on one side of the line and all points of the other quadratangle are on the other side of the line. – Trunnion

Answer 2

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:

1. Sweep line based algorithm. As you mentioned you can perform a sweep line procedure and keep the intervals resulting from the intersection of the polygons with the sweeping line. If at any time the intervals overlap, then the polygons intersect. The complexity is O((r + b) log (r + b)) time.
2. Rotating Callipers based algorithm. See here and here for more details. The complexity is O(r + b) time.
3. The most efficient methods can be found here and here. These algorithms take O(log r + log b) time.

Lichen

Answer 3

• 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.

Folliculin

1) How do I programatically eliminate those edges? 2) That's the third case illustrated above. – Meuse

Your edge elimination method seems like it might not work if the amount of overlap is very high. – Meuse

Answer 4

GJK collision detection should work.

Illative

It gives more information than you need (the minimum distance b/w two N-dimensional convex polytopes, not just whether that distance is 0 (collision) or not), but there's not a significant performance overhead for doing so. The MollyRocket link has a good intuitive explanation. – Illative

This answer references great information, but you really should split each link into separate sentences or at least use a bulleted list. – Anthurium

Answer 5

Since altCognito already gave you a solution, I'll only point out an excellent book on computational geometry that might interest you.

Amerind

Thanks, I have come across that in my searching, and I'm considering purchasing it. I have already borrowed another comp. geom. book from another programmer. – Meuse

Answer 6

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.

Brownfield

Thanks. I do indeed to test with complex shapes, not the rectangles I've drawn here. They're just easier to draw. All of my polygons are convex, though, so I don't have any U-shapes. – Meuse

Your algorithm should work fine. The algorithm referenced by MaxVT may be faster, but yours should work. It should handle non-convex polys just as easily, too. – Brownfield

Yeah i like this algorithm also. I am testing very small shapes (quadrilaterals and triangles) so it's easier to just test if every edge can be a separating axis. probably faster too. – Queston

Answer 7

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.

Anvers

I down-voted this answer because the second bullet is not correct, according to the following concrete example using two convex quadrilaterals: Quad #1: {-50, 3} {0, 4} {50, 3} {0, 2}; Quad #2: {-1, -1} {-1, 1} {1, 1} {1, -1}. The center of Quad #2 is the origin, and the two nearest points are {0, 2} and {0, 4}, respectively, which are NOT adjacent points in Quad #1. – Virgy