Method to detect intersection between a rectangle and a polygon?

Question

What is the best method to detect whether the red rectangle overlaps the black polygon? Please refer to this image:

Answer 1

There are four cases.

1. Rect is outside of Poly
2. Rect intersects Poly
3. Rect is inside of Poly
4. Poly is inside of Rect

First: check an arbitrary point in your Rect against the Poly (see Point in Polygon). If it's inside you are done, because it's either case 3 or 2. If it's outside case 3 is ruled out.

Second: check an arbitrary point of your Poly against the Rect to validate/rule out case 4.

Third: check the lines of your Rect against the Poly for intersection to validate/rule out case 2.

This should also work for Polygon vs. Polygon (convex and concave) but this way it's more readable.

Answer 2

If your polygon is not convex, you can use tessellation to subdivide it into convex subparts. Since you are looking for methods to detect a possible collision, I think you could have a look at the GJK algorithm too. Even if you do not need something that powerful (it provides information on the minimum distance between two convex shapes and the associated witness points), it could prove to be useful if you decide to handle more different convex shapes.

Christer Ericson made a nice Powerpoint presentation if you want to know more about this algorithm. You could also take a look at his book, Real-Time Collision Detection, which is both complete and accessible for anyone discovering collision detection algorithms.