How can I tell if two polygons intersect?

Question

Hello,

Imagine I have the coordinate of 4 points that form a polygon. These points are represented using PointF in C#. If I have 2 polygons (using 8 points), how can I tell if they intersect?

Rectangle class has a method called IntersectsWith but I couldn't find something similar for GraphicsPath or Region.

Any advice would be greatly appreciated.

Mosh

Answer 1

If your polygons are convex then you should be able to use separating axis theorem. A demo is available here (It's in actionscript but the code should be easy to port to c#)

This is really not my area but I hope it helps anyway.

Answer 2

As Charlie already pointed out you can use the Separating Axis theorem. Check out this article for a C# implementation and example of polygon collision detection.

I have also answered this question here which deals with 2D collision in C#.

Answer 3

Strictly speaking, the other answers suggesting an algorithm are probably your best bet. But performance aside, you mentioned that you couldn't find anything like IntersectsWith for GraphicsPath or Region. However there is an Intersect method that updates a region to be the intersection of itself and another region or path. You could create two regions, Intersect() one with the other, then test for Region.IsEmpty().

But I imagine this is probably a pretty slow way to do it and would probably result in a lot of allocations if done in a loop.