2D Polygon Collision Detection

Question

Does anyone know a simple way to check if two polygons, especially rectangles, are colliding? I found a simple way to see if two are touching by just checking if any lines on the two rectangles are colliding, but this will not work if one polygon is in another. Does anyone know a more efficient way to do this or just a way that works?

Also, can someone please give me a formula for it or something like that and not just your thoughts on the subject.

Thanks

Answer 1

Look up the Separating Axis Theorem. There's a tutorial here.

It's quick, elegant, robust, not too hard, and has lots of resources.

Answer 2

There are several methods, the simple is just to check if there is and overlap in X or Y bounds. This however only works with rectangles aligned with the axis.

There is bounds checking, is the corner of one object withing the bounds of coordinates of the other.

From there collision detection gets more advanced. Checking to see if there is a line one can draw between them in any direction and such.

Answer 3

Example:

Rectangle A

Left, top corner (x,y). Width, height.

Rectangle B

Left, top corner (x1,y1).

Condition

(x>=x1) and (x<=x1+width) => collision for x axis. For y axis this same but with y and y1 and height.

Answer 4

Check out http://www.metanetsoftware.com/technique/tutorialA.html

That site helped me infinitely when developing my own collision detection routines. Depending on the amount of available processing power, you can do just about anything you want in terms of collision accuracy. Starting with the least processor intensive:

1) Bounding box: Good for rectangular shapes and quick to boot. All you need to know is the (x, y) position of the object as well as its width and height.

2) Separating Axis Theorem (SAT): Able to handle more complex shapes and is fairly intuitive.

3) SAT with Voronoi Regions (VR): Uses information on which vertex of any given polygon is closest to in order to reduce the total number of computations.

All of the above is explained in-depth in the above link. It should be noted that, thus far, the methods mentioned are most effective for convex polygons. If you wanted to go into absurd levels of accuracy, you start moving into things like bitmap testing which is horrendously slow and generally overkill for almost anything.