Method to detect intersection between a rectangle and a polygon?

What is the best method to detect whether the red rectangle overlaps the black polygon?开发者_开发知识库 Please refer to this image:

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.

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.

If you know for a fact that the red rectangle is always axis-aligned and that the black region consists of several axis-aligned rectangles (I'm not sure if this is just a coincidence or if it's inherent to the problem), then you can use the rectangle-on-rectangle intersection algorithm to very efficiently compute whether the two shapes overlap and, if so, where they overlap.

If you use axis-aligned rectangles and polygons consist of rectangles only, templatetypedef's answer is what you need.

If you use arbitrary polygons, it's a much more complex problem. First, you need to subdivide polygons into convex parts, then perform collision detection using, for example, the SAT algorithm

Simply to find whether there is an intersection, I think you may be able to combine two algorithms.

1) The ray casting algorithm. Using the vertices of each polygon, determine if one of the vertices is in the other. Assuming you aren't worried about the actual intersection region, but just the existence of it. http://en.wikipedia.org/wiki/Point_in_polygon

2) Line intersection. If step 1 produces nothing, check line intersection.

I'm not certain this is 100% correct or optimal.

If you actually need to determine the region of the intersection, that is more complex, see previous SO answer:

A simple algorithm for polygon intersection