How do I determine if two convex polygons intersec

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.

Answer 1

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