3

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.

Paŭlo Ebermann
  • 73,284
  • 20
  • 146
  • 210
Matt
  • 1,151
  • 3
  • 13
  • 34

2 Answers2

5

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

Community
  • 1
  • 1
phkahler
  • 5,687
  • 1
  • 23
  • 31
3

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.

Edwin Buck
  • 69,361
  • 7
  • 100
  • 138
  • -1 for only mentioning the optimization and ignoring the essential functionality (e.g. you do not mention testing whether a vertex of one rectangle is contained in the other rectangle.) – finnw Jun 02 '11 at 17:22
  • Actually that's just a "quick check" to avoid a more expensive analysis when applicable (please read 2nd half of the post). therefore +1 – ignis Jun 02 '11 at 17:26
  • 1
    There is no actual solution given here. – phkahler Jun 02 '11 at 17:41
  • @finnw, so the checking for overlapping pixels doesn't actually check for overlapping objects? Seems like someone was skimming the answer. – Edwin Buck Jun 02 '11 at 19:10
  • Not in 3D, which this will be in. But since the the rotation of my 3D object is only on the Y axis, all I need to know is how to find if rotated rects are colliding. – Matt Jun 02 '11 at 20:12
  • @Matt, Good point. I guess I've been doing too much 2D for my own good. – Edwin Buck Jun 03 '11 at 00:19