How do I determine if two convex polygons intersect?

Answer 1

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.

Answer 2

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

Answer 3

How about this collision algorithm?

Answer 4

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

Answer 5

Here's a simple 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.

Answer 6

GJK collision detection should work.