Code Snippets
Code Samples

The Blog
Our Projects

::Add RageStorm to Favorites!::

The Blog | Our Projects | Guest Book | About | Contact

Tutorial - 2D Rotated Rectangles Collision Detection
Uploaded at:29-May-03
Testing whether two rotated rectangles intersect is a bit complicated, but there exists a surprisingly efficient solution.

Let me first describe a simple partial solution for people who just want something to understand quickly:
"For each of the 2 rectangles, check whether any of its vertices is within the the other rectangle."

That's a short explanation, isn't it? It's just too bad that it doesn't work sometimes. Can you see when?
When can two rectangles partly overlap without any of them having any of its vertices within the other rectangle? If you haven't got it, think of a cross, or just click here.
In most simulations, such situations aren't supposed to occur since the collision response mechanism detaches the rectangular objects before they can form a cross. However, who said this routine is to be used for physical simulation only? Another note to justify the explanation to come of the more complicated solution is that it's efficient (note that you can optimize the vertex check solution by combinining the tests of the vertices in the same rectangle, but it still doesn't get as fast as the following solution).

Each rectangle will be represented by [center{x,y}, size{w,h}, alpha]. First, let's translate the plane by (-rect1.center.x, -rect1.center.y) to make rect1.center unify with the origin. Second, we'll rotate the plane by -rect2.alpha to make the second rectangle axis aligned. Note that it works even though rect2.center doesn't necessarily unify with the origin.

Note: I'd suggest you download the C sourcecode attached and follow it as you read the tutorial if you have problems understanding any part of this tutorial.

We now have the first rectangle (rect1) centered around the origin and the second rectangle (rect2) axis-aligned (we have somehow spread the complex properties rectangles may have, uniformly between the two rectangles). We'll now note the obvious features of rect2 (or any axis aligned rectangle), namely that: (1) It's wholly contained between its left side, x=Left, and its right side, x=Right (We'll call that region the Horizontal Range, H-Range in the applet), and (2) in this limited region, it covers the whole area between its upper side, Y=Top, and its bottom, Y=Bottom (This is NOT the V-Range in the applet, it is the region Rectangle 2 cuts from the H-Range). Due to (1), it's obvious that we can check for collision between rect2 and the part of the rect1 which is bounded by the infinite lines x=Left and x=Right, we'll call this part, Shape1 (if this region does not contain any part of the rect1, collision is impossible. I'd suggest you play with the applet to understand what Shape1 is). (2) makes it clear that it is enough to check whether Shape1 has any point bounded between the upper side of the second rectangle and its bottom.

But a rectangle is a convex polygon and therefore Shape1 will be cut "in one piece". That means, for our purposes, that if (X1, MaxY) is the highest point of Shape1, and (X2, MinY) is the lowest point of Shape1, then for any Y between MinY and MaxY, there's an X such that (X, Y) is a point within Shape1. Therefore, checking if Shape1 has any point bounded between the upper side of the second rectangle and its bottom, is equivalent to checking whether there's any Y value between MinY and MaxY, which is also between Top and Bottom. This is equivalent to checking whether two segments in a 1D enviroment intersect. We've actually found a general algorithm of testing for intersection between a rectangle and any convex polygon, but in the rest of this article we'll assume that this other convex polygon is a rectangle too.

This leaves us to find a way to quickly find MinY and MaxY (The region between MinY and MaxY is called the Vertical Range, the V-Range in the applet):

Since rect1 is centered around the origin, it is symmetric around the X Axis and around the Y Axis. It has two pairs of opposing vertices, one which is the highest and lowest points of the rectangle and one which is the leftest and rightest points. Due to the symmetry just mentioned, we'll denote these pairs of vertices (A, -A) - Vertical Min/Max, and (B, -B) - Horizontal Min/Max.

The orientation of rect2 determines which pair of vertices is (A, -A), and which is (B, -B). This property flips every 90 degrees of rotation and therefore it can be figured out by the sign of sin(rect2.alpha)*cos(rect2.alpha) (this is done after rotation of the plane by -rect1.alpha, so the actual angle here is rect2.alpha-rect1.alpha = ang, see the C source code attached).

First, we'll check whether Shape1 exists, by comparing the ranges [B, -B] and [Left, Right].

We don't have to check which of A and -A is the vertical maximum and which is the minimum because we treat them in the same manner. We'll find Shape1's highest and lowest Y values, MaxY and MinY, and store them in the variables ext1 and ext2 (without knowing which is the maximum and which is the minimum).

We'll check whether A is in the Horizontal Range (between x=Left and x=Right). If it is, it is obviously Shape1's extremity. If it's on the right of this region, the extrimity would be the interestion point of the segment AB and the line x=Left. If it's on the left, the extrimity would be the intersection point of the segment A(-B) and the line x=Right.

To code this well, first compute the differences Right-A.x, Left-A.x. If they have different signs, A.x is between them and A.y is our extremity. If they have the same sign, check which sign it is. If it's negative (case 1), A.x is on the right, and if the sign is positive (case 2), A.x in on the left. Now calculate the slope, case 1: (A.y-B.y)/(A.x-B.x) or case 2: (A.y-(-B.y))/(A.x-(-B.x)), multiply it by the precalculated horizontal distnace from A: case 1: Right-A.x or case 2: Left-A.x and add this to A.y to get the extremity.

	dx1 = Left-A.x; dx2 = Right-A.x; // Calculate difference
	ext1 = A.y;
	// If A.x is within x=Left and x=Right, this is the exterimity,
	// otherwise, it will be used to calculate dy (= A.y-B.y or A.y-(-B.y) = ext-B.y or ext+B.y).

	if (dx1*dx2 > 0)
	 dx = A.x;
         // dx = (A.x-B.x),    dy = (A.y-B.y),    dx1 = (Right-A.x)
	 if (dx1 < 0) { dx -= B.x; ext1 -= B.y; dx1 = dx2; }
         // dx = (A.x-(-B.x)), dy = (A.y-(-B.y))  dx1 = (Left-A.x)
	 else         { dx += B.x; ext1 += B.y; }
         // ext1 = A.y + (dy/dx)*dx1
	 ext1 *= dx1; ext1 /= dx; ext1 += A.y;
Nifty code, isn't it?

Do the same with -A instead of A to find the other extrimity, ext2.
Now conduct 1D segment intersection test between [ext1, ext2] and [top, bottom].

That's it! See the C source code attached: CDRR.C

User Contributed Comments(9)
 [1] John Folks | 2005-10-17 20:58:50

I understood!
 [2] Karthik VS | 2006-01-06 06:07:45

very useful
thanks a lot
 [3] steve novick | 2006-05-01 03:00:14

would be nice to have the source for the applet.. i'd rather do java than C
 [4] arkon | 2006-05-06 18:51:05

The source code of the applet is uploaded and can be found in samples section.
 [5] Tony | 2006-07-11 19:33:27

This is great! It helped me enormously. Many thanks, Oren!
 [6] Windsor Schmidt | 2006-12-06 04:27:51

This is really cool, thanks for sharing it! I'm wondering if there is a good way to determine the point of collision, assuming the rectangles are just beginning to overlap slightly? Thanks, Windsor.
 [7] manuel | 2007-02-04 19:29:32

Great method indeed!
But how to be able to derive a collision normal?
 [8] Jeffrey | 2007-09-12 11:07:05

Thanks Oren! It help me a lot!
 [9] Parrebuff | 2008-03-05 07:32:44

Thanks! Very usesful and easy to understand :D
Comments that will hurt anyone in any way will be deleted.
Don't ask for features, advertise or curse.
If you want to leave a message to the author use the contacts,
if you have any question in relation to your comments please use the forum.
Comments which violate any of these requests will be deleted without further
notice. Use the comment system decently.

Post your comment:
::Top 5 Tutorials::
Embedded Python[112014]
2D Rotated Rectangles Collision Detection[85866]
Keyboard Hook[73857]
HTTP Proxy[39106]

::Top 5 Samples::
2D ColDet Rotated Rectangles[11194]
PS2 Mouse Driver[6623]
Wave Format Player[5455]
Reading FAT12[5319]

All rights reserved to RageStorm © 2009