1
$\begingroup$

I was trying to determine whether or not two rectangles rotated around their centers were colliding and randomly thought to try the following algorithm:

Rotate both rectangles by the negative rotation angle value of the first rectangle, such that the first rectangle becomes an AABB (axis-aligned bounding box) rectangle. Now calculate the bounding box of the second rotated rectangle and use the simple "are two axis aligned rectangles colliding" function to see if those two rectangles are colliding:

function rectanglesCollide(r1X, r1Y, r1W, r1H, r2X, r2Y, r2W, r2H) {
  return r1X < r2X + r2W && r1X + r1W > r2X && r1Y < r2Y + r2H && r1Y + r1H > r2Y;
}

Now do the same thing but in reverse. That is, rotate both rectangles by the negative rotation angle of the second rectangle, such that now the second rectangle becomes axis-aligned. Then calculate the bounding box for the first rectangle and use the same rectanglesCollide function to determine if those two rectangles are colliding.

From what I can tell, if both of those checks are true, then the rotated rectangles are colliding. I spent a couple days trying to figure out the math and finally got it working! Here's the function for it:

function rotatedRectanglesCollide(r1X, r1Y, r1W, r1H, r1A, r2X, r2Y, r2W, r2H, r2A) {
  let r1CX = r1X + (r1W / 2);
  let r1CY = r1Y + (r1H / 2);
  let r2CX = r2X + (r2W / 2);
  let r2CY = r2Y + (r2H / 2);

  let cosR1A = Math.cos(r1A);
  let sinR1A = Math.sin(r1A);
  let cosR2A = Math.cos(r2A);
  let sinR2A = Math.sin(r2A);

  let r1RX =  cosR2A * (r1CX - r2CX) + sinR2A * (r1CY - r2CY) + r2CX;
  let r1RY = -sinR2A * (r1CX - r2CX) + cosR2A * (r1CY - r2CY) + r2CY;
  let r2RX =  cosR1A * (r2CX - r1CX) + sinR1A * (r2CY - r1CY) + r1CX;
  let r2RY = -sinR1A * (r2CX - r1CX) + cosR1A * (r2CY - r1CY) + r1CY;

  let cosR1AR2A = Math.abs(cosR1A * cosR2A + sinR1A * sinR2A);
  let sinR1AR2A = Math.abs(sinR1A * cosR2A - cosR1A * sinR2A);
  let cosR2AR1A = Math.abs(cosR2A * cosR1A + sinR2A * sinR1A);
  let sinR2AR1A = Math.abs(sinR2A * cosR1A - cosR2A * sinR1A);

  let r1BBH = r1W * sinR1AR2A + r1H * cosR1AR2A;
  let r1BBW = r1W * cosR1AR2A + r1H * sinR1AR2A;
  let r1BBX = r1RX - r1BBW / 2;
  let r1BBY = r1RY - r1BBH / 2;

  let r2BBH = r2W * sinR2AR1A + r2H * cosR2AR1A;
  let r2BBW = r2W * cosR2AR1A + r2H * sinR2AR1A;
  let r2BBX = r2RX - r2BBW / 2;
  let r2BBY = r2RY - r2BBH / 2;

  return r1X < r2BBX + r2BBW && r1X + r1W > r2BBX && r1Y < r2BBY + r2BBH && r1Y + r1H > r2BBY &&
        r2X < r1BBX + r1BBW && r2X + r2W > r1BBX && r2Y < r1BBY + r1BBH && r2Y + r2H > r1BBY;
}

I was wondering if this is novel, known, or even correct? The closest thing I could find was this answer on the original post that I found afterwards that seems to be pretty similar, or maybe it's the exact same thing coded differently? I'm not entirely sure how his code works or whether or not it's a different technique. Also, could this be optimized in any way?

Not sure if my explanation was any good but I ended up making a post about it with more details and a demo if that helps understanding at all.

$\endgroup$
1
  • 2
    $\begingroup$ Googling for "Separating axis theorem" yields gamedevelopment.tutsplus.com/tutorials/…, which seems similar to what you propose. I think this question probably isn't a research-level question in theoretical CS, so perhaps should be migrated to cs.stackexchange.com. $\endgroup$
    – Neal Young
    Sep 14 at 12:04
1
$\begingroup$

If you rotate your rectangles through a common origin, then your method works. Your method works if there always exists a separating line that is parallel to a side of one of your rectangles. Such a line indeed exists. To see this, start from an arbitrary separating line and rotate it until it hits both rectangles, say in vertices $p$ and $q$. For a given angle $\alpha$, consider the line $l_p(\alpha)$ through $p$ and $l_q(\alpha)$ through $q$. By construction, there exists some $\alpha$ such that these lines coincide (and pass through both $p$ and $q$) and are both separating lines. Now rotate these separating lines by varying $\alpha$ until one of them hits a second vertex of a rectangle. If a separating line hits vertices of different rectangles, then the separating lines must coincide (because the region between $l_p(\alpha)$ and $l_q(\alpha)$ contains no rectangles), so one of the separating lines hits two vertices of the same rectangle, and hence coincides with an side of a rectangle. Therefore, your method works if you rotate your rectangles through a common origin.

Prior answer: In my original answer, I misinterpreted your method and assumed that you rotated your rectangles around their respective centers. Under that assumption, the method may falsely report that rectangles collide, as illustrated in the figure below. The blue squares do not overlap, but their axis-aligned bounding boxes do. Rotating the squares to make the top right square axis aligned results in the red squares, whose axis-aligned bounding boxes also overlap.

Squares

$\endgroup$
11
  • $\begingroup$ Sorry, I'm not sure if I'm understanding you but I tried to make a reproduction of the case that you're describing here jsfiddle.net/4rhyp1q5 (move the rectangle with wasd), and I'm not seeing that issue. Maybe you could edit the fiddle with the case that you're describing? $\endgroup$ Sep 13 at 23:57
  • $\begingroup$ This answer looks incorrect to me. When you make the first blue square axis-aligned, there is overlap in the bounding boxes, but when you make the second blue square axis-aligned, there is no overlap in the bounding boxes. Consequently the proposed method does not claim they collide -- the proposed method seems to work fine on the blue squares. $\endgroup$
    – D.W.
    Sep 14 at 3:39
  • $\begingroup$ I find the picture confusing because it shows 4 squares, but the question talks about 2 squares. I suggest you try to draw a picture with two squares, where you show the result of the first check (rotate to make the first square axis-aligned); and a separate picture with two squares, where you show the result of the second check (rotate to make the second square axis-aligned), and I think you'll see why this counterexample doesn't work. $\endgroup$
    – D.W.
    Sep 14 at 3:39
  • $\begingroup$ I updated the figure. $\endgroup$
    – Tim
    Sep 14 at 8:08
  • $\begingroup$ @Tim are you still saying that this is indeed a counter-example in some way? $\endgroup$ Sep 14 at 8:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.