Home
Tutorials
Code Snippets
Code Samples
Downloads
The Forum
Links

The Blog
Our Projects
Guest Book
About
Contact

ShOuT b0X:
::Add RageStorm to Favorites!::

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

 
Tutorial - 2D Rotated Rectangles Collision Detection
Author:Oren
Category:Miscellaneous
Uploaded at:29-May-03
Views:66602
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(21)
 [1] John Folks | 2005-10-17 16:58:50

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

very useful
thanks a lot
 [3] steve novick | 2006-04-30 23:00:14

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

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

This is great! It helped me enormously. Many thanks, Oren!
 [6] Windsor Schmidt | 2006-12-05 23: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 14:29:32

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

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

Thanks! Very usesful and easy to understand :D
 [10] name | 2010-04-05 20:34:25

If anyone's having problems with the detection, you may want to change some of the code, particularly the ones that get the dimensions(the 2D vector S of a rotated rectangle); I had to resize it down to half the width and height to get it to work:

BL -= rr2->S / 2;
TR += rr2->S / 2;
...
 A.x = -(rr1->S.y / 2) * sina;
...
 t = (rr1->S.x / 2) * cosa;
...
 A.y = (rr1->S.y / 2) * cosa;
...
 t = (rr1->S.x / 2) * sina;
 [11] spstanley | 2011-02-10 14:37:19

@name Thanks for the tip! I thought that looked a bit odd....
 [12] Willi Burkhardt | 2011-09-07 03:47:56

@oren, thanks a lot for this algorithm. It's simple to use in C and simple to convert to a C++ class. I found that the comment by @name is indeed valid. One thing that got me is that all trigonometric functions in C or C++ are in radians. So, either you treat the _RotRect as radians or you convert to radians on the fly:

#ifndef M_PI    // in case we miss it in <cmath>
#define M_PI 3.14159265358979
#endif
const float PI_180 = (float)M_PI / 180.f;
cosa = cos(ang * PI_180);
sina = sin(ang * PI_180);
 [13] GwenMcneil24 | 2011-11-13 13:16:38

Make your own life time easier get the <a href="http://goodfinance-blog.com/topics/credit-loans">credit loans</a> and all you require.
 [14] zhuzhu | 2013-02-28 02:21:57

Our store are powerful and reliable, [url=http://www.gw2gw2.com/gold.html]Guild Wars 2 Gold[/url] You can buy gw2 gold,gw2 items,gw2 powerleveling,gw2 cdkey in our store. [url=http://www.findelicacy.com]Find Delicacy[/url] We will provide you the best service. [url=http://www.gw2gw2.com/gold.html]cheap GW2 Gold[/url] GW2 cd key with secure transaction. Buy Guild Wars 2 CD Key right now! Guild Wars 2 Item Shop and GW2 Gold enjoys cheap price.Guild Wars 2 Gold. [url=http://www.gw2gw2.com/gold.html]gw2 gold[/url] all your wants relating to Guild Wars 2 game are going to be met with 100% satisfaction here!
 [15] Agnes | 2013-03-07 03:25:54

Wizardry Gold <a href="http://www.thepowerlevel.com/Gold.php?N=Wizardry">Wizardry Gold</a> is a recreation of the critically acclaimed Wizardry VII, Crusaders of the Dark Savant. The primary differences in this incarnation are the markedly improved graphics and enhanced sound score. <a href="http://www.thepowerlevel.com/Gold.php?N=Wizardry">Buy Wizardry Gold</a> In Gold, you control a group of adventurers that embark on a mission to find the Astral Dominae and guard it against the Dark Savant, <a href="http://www.thepowerlevel.com/Gold.php?N=Wizardry">cheap Wizardry Online Gold</a> an evil overlord who needs the Dominae for supreme rulership.
 [16] goldrunescape | 2013-06-13 05:20:51

Make your own life time easier get the [url=http://www.vipmmohome.com/]WOW Gold Buy[/url] and all you require.
 [17] wowgold5 | 2013-08-29 03:24:15

A very unique perspective for your article, I agree with your point of view.I also hope that you are at work is to be able to relax, this is what I recommend to your game, you can click on http://www.rsgold2buy.com/
 [18] diablo3tips | 2013-08-29 03:26:23

I am agree with your point of view very much &#65292;I think it's doors very well this is our game sites recommended to http://www.d3joy.com/
 [19] David | 2013-11-20 01:30:07

@name
something like this works:

// calculate vertices of (moved and axis-aligned := 'ma') rr2
BL = TR = C;
SubVectors2D(&BL, &(_Vector2D){ rr2->size.x/2, rr2->size.y/2 });
AddVectors2D(&TR, &(_Vector2D){ rr2->size.x/2, rr2->size.y/2 });

// calculate vertices of (rotated := 'r') rr1
A.x = -(rr1->size.y / 2) * sina;
B.x = A.x;
t = (rr1->size.x / 2) * cosa;
A.x += t;
B.x -= t;
A.y = (rr1->size.y / 2) * cosa;
B.y = A.y;
t = (rr1->size.x / 2) * sina;
A.y += t;
B.y -= t;
 [20] PKCLsoft | 2014-01-07 09:05:19

I too found that @David and @name were correct in order to get this to work.
 [21] lily | 2014-07-05 00:16:37

Hello. I believe that this article has some really great information for everyone! http://www.friv5gamer.com | http://www.friv4gamer.net
NOTE:
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:
Name:
email:
Comment:
::Top 5 Tutorials::
Embedded Python[80782]
2D Rotated Rectangles Collision Detection[66602]
Keyboard Hook[62768]
UDP[44365]
HTTP Proxy[32009]

::Top 5 Samples::
2D ColDet Rotated Rectangles[9572]
PS2 Mouse Driver[5650]
Reading FAT12[4479]
Wave Format Player[4469]
CodeGuru[4145]

::Link to RageStorm::

::Affiliates::
AngelCode
YOV408 Technologies
FireStorm


All rights reserved to RageStorm © 2009