How to check intersection between 2 rotated rectan

Question

Can someone explain how to check if one rotated rectangle intersect other rectangle?

Answer 1

Check out the method designed by Oren Becker to detect intersection of rotated rectangles with form:

struct _Vector2D 
{
    float x, y;
};

// C:center; S: size (w,h); ang: in radians, 
// rotate the plane by [-ang] to make the second rectangle axis in C aligned (vertical)
struct _RotRect 
{
    _Vector2D C;
    _Vector2D S;
    float ang;
};

And calling the following function will return whether two rotated rectangles intersect or not:

// Rotated Rectangles Collision Detection, Oren Becker, 2001
bool check_two_rotated_rects_intersect(_RotRect * rr1, _RotRect * rr2)
{
    _Vector2D A, B,   // vertices of the rotated rr2
       C,      // center of rr2
       BL, TR; // vertices of rr2 (bottom-left, top-right)

 float ang = rr1->ang - rr2->ang, // orientation of rotated rr1
       cosa = cos(ang),           // precalculated trigonometic -
       sina = sin(ang);           // - values for repeated use

 float t, x, a;      // temporary variables for various uses
 float dx;           // deltaX for linear equations
 float ext1, ext2;   // min/max vertical values

 // move rr2 to make rr1 cannonic
 C = rr2->C;
 SubVectors2D(&C, &rr1->C);

 // rotate rr2 clockwise by rr2->ang to make rr2 axis-aligned
 RotateVector2DClockwise(&C, rr2->ang);

 // calculate vertices of (moved and axis-aligned := 'ma') rr2
 BL = TR = C;
 /*SubVectors2D(&BL, &rr2->S);
 AddVectors2D(&TR, &rr2->S);*/

 //-----------------------------------
 BL.x -= rr2->S.x/2;    BL.y -= rr2->S.y/2;
 TR.x += rr2->S.x/2;    TR.y += rr2->S.y/2;

 // calculate vertices of (rotated := 'r') rr1
 A.x = -(rr1->S.y/2)*sina; B.x = A.x; t = (rr1->S.x/2)*cosa; A.x += t; B.x -= t;
 A.y =  (rr1->S.y/2)*cosa; B.y = A.y; t = (rr1->S.x/2)*sina; A.y += t; B.y -= t;
 //---------------------------------------

 //// calculate vertices of (rotated := 'r') rr1
 //A.x = -rr1->S.y*sina; B.x = A.x; t = rr1->S.x*cosa; A.x += t; B.x -= t;
 //A.y =  rr1->S.y*cosa; B.y = A.y; t = rr1->S.x*sina; A.y += t; B.y -= t;

 t = sina*cosa;

 // verify that A is vertical min/max, B is horizontal min/max
 if (t < 0)
 {
  t = A.x; A.x = B.x; B.x = t;
  t = A.y; A.y = B.y; B.y = t;
 }

 // verify that B is horizontal minimum (leftest-vertex)
 if (sina < 0) { B.x = -B.x; B.y = -B.y; }

 // if rr2(ma) isn't in the horizontal range of
 // colliding with rr1(r), collision is impossible
 if (B.x > TR.x || B.x > -BL.x) return 0;

 // if rr1(r) is axis-aligned, vertical min/max are easy to get
 if (t == 0) {ext1 = A.y; ext2 = -ext1; }
 // else, find vertical min/max in the range [BL.x, TR.x]
 else
 {
  x = BL.x-A.x; a = TR.x-A.x;
  ext1 = A.y;
  // if the first vertical min/max isn't in (BL.x, TR.x), then
  // find the vertical min/max on BL.x or on TR.x
  if (a*x > 0)
  {
   dx = A.x;
   if (x < 0) { dx -= B.x; ext1 -= B.y; x = a; }
   else       { dx += B.x; ext1 += B.y; }
   ext1 *= x; ext1 /= dx; ext1 += A.y;
  }

  x = BL.x+A.x; a = TR.x+A.x;
  ext2 = -A.y;
  // if the second vertical min/max isn't in (BL.x, TR.x), then
  // find the local vertical min/max on BL.x or on TR.x
  if (a*x > 0)
  {
   dx = -A.x;
   if (x < 0) { dx -= B.x; ext2 -= B.y; x = a; }
   else       { dx += B.x; ext2 += B.y; }
   ext2 *= x; ext2 /= dx; ext2 -= A.y;
  }
 }

 // check whether rr2(ma) is in the vertical range of colliding with rr1(r)
 // (for the horizontal range of rr2)
 return !((ext1 < BL.y && ext2 < BL.y) ||
      (ext1 > TR.y && ext2 > TR.y));
}

inline void AddVectors2D(_Vector2D * v1, _Vector2D * v2)
{ 
    v1->x += v2->x; v1->y += v2->y; 
}

inline void SubVectors2D(_Vector2D * v1, _Vector2D * v2)
{ 
    v1->x -= v2->x; v1->y -= v2->y; 
}

inline void RotateVector2DClockwise(_Vector2D * v, float ang)
{
    float t, cosa = cos(ang), sina = sin(ang);
    t = v->x; 
    v->x = t*cosa + v->y*sina; 
    v->y = -t*sina + v->y*cosa;
}