CODEWITHSUNDEEP
javageometryrotationcollision-detection
Matt
Matt

Reputation: 1211

Rotated rectangle Collision

What is the most efficient way to find out if one axis aligned rectangle is colliding with one rotated rectangle? Each class has a position vector and a size vector and the rotated class has an angle value.

Upvotes: 3

Views: 1994

Answers (2)

phkahler
phkahler

Reputation: 5767

You want to use the Separating Axis Theorem (SAT). Normally it's used in 3d, but it collapses to 2d quite well. Since you've got a special case, the only axis you need to consider are 4 main axis of your rectangles:

[ 1,0 ]
[ 0,1 ]
[ sin(theta), cos(theta) ]
[ -cos(theta), sin(theta) ]

To check an axis, compute the dot product of every vertex with that axis. Then check the min and max of the 2 sets of values to see if they overlap. If any of the 4 axis gives ranges that don't overlap then the rectangles do not overlap (you've found a separating axis). If all 4 axis show overlap then the rectangles intersect.

Here is a recent SO question on the same problem: Separating Axis Theorem and Python

And here is the wikipedia article

http://en.wikipedia.org/wiki/Separating_axis_theorem

Upvotes: 5

Edwin Buck
Edwin Buck

Reputation: 70999

The most efficent way is to create a larger rectangle which bounds the rotated rectangle, and the do collision detection based on the bounding rectangles.

This means that bounding rectangle collisions don't signify "hits" but rather conditions which merit further investigation. Means of investigating differ depending on what assumptions you can make. In the simplest cases, you could AND pixels checking for a true output.

You could then use this "confirmed" hit to do an analysis with a more sophisticated model; one that takes into account the angles, velocities, geometry, and elasticity of the collision (or whatever you're interested in).

More sophisticated models exist, but generally the more sophisticated models require more computational power. It's easier to save your computational power by setting up a series of fast, quick checks and only bring out the heavy compute cycles for the cases where they are going to pay off.

Upvotes: 3

Related Questions