Separating axis test, detecting if a rotated rectangle overlap an other flat rectangle

Question

Hello,

I read about intersection rectangles on:

http://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles

But i have trouble to implement it.

If R1 (A,B,C,D) is my rotated rectangle and R2(A',B',C',D') the other rectangle with no rotation.

The formula extracted in from the link above is:

  edge = v(n) - v(n-1)

You can get a perpendicular to this by rotating it by 90°. In 2D this is easy as:

  rotated.x = -unrotated.y
  rotated.y =  unrotated.x

  // rotated: your rotated edge
  // v(n-1) any point from the edge.
  // testpoint: the point you want to find out which side it's on.

  side = sign (rotated.x * (testpoint.x - v(n-1).x) + 
               rotated.y * (testpoint.y - v(n-1).y);

My rotated edges will be from R1 with

AB (xB-xA, yB-yA) so rotated x is xB-xA ? BC (xC-xB, yC-y1) CD ... AD ...

Testpoint will be A', B', C', D' from R2 So i have to check the sign of the result from all points of R2 against the 4 edges from R1. Thats 16 comparisons if intersecting. How do i know if i found a separating edge ?

Thanks

Answer 1

If for any given edge, the signs of any of the dot products testing against that edge don't match, then you have an intersection. The sign of the dot product will be the same for all points on one side of the line.