How to check if two rectangles intersect? Rectangles can be rotated

Question

How to check if two rectangles intersect? Each rectangle is defined by three points in 2d space. The rectangles can be rotated around any point as on the image below.

Answer 1

Hint:

• You can use 2D cross product of vectors to decide whether a point is on the left- or right-hand side of some given vector.
• You can use the above to check if a point is inside or outside a convex polygon by checking each edge.
• You can use the first bullet point to check if two vectors intersect.
• Two rectangles $A$ and $B$ intersect if and only if at least one of the following is satisfied
  1. a corner of $A$ is inside $B$;
  2. a corner of $B$ is inside $A$;
  3. some edge of $A$ intersect with some edge of $B$.

I hope this helps $\ddot\smile$

Answer 2

If they can be rotated around any point (or corner by the way).

Take rectangle $R_1$ with corners $A_1$, $B_1$ etc.

You have four circles of center $A_1$, $B_1$ etc. and of radius $A_1C_1$, $B_1D_1$ etc.

You just have to check if any of these four circle intersect with any of the four other circles defined the same way with rectangle $R_2$ (points $A_2$, $B_2$ and radii $A_2C_2$ etc.).

Answer 3

It is never too late to answer an interesting question.

The answer provided by @dtldarek is correct for general polygon intersection detection. However, there is a fast way to check intersections for rectangles.

In the picture above, if we project the vertexes of rectangle EFGH on line segment AB, the projections will be all negative, meaning that all points of rectangle EFGH are on the left side of DA. Thus we can safely declare that the rectangle EFGH does not intersect with rectangle ABCD.

In another case, if the projections of EFGH on AB are all greater than |AB|, which means that all points of rectangle EFGH are on the right side of CB, we can also declare that there is no intersection.

In general, if one of the following is true, then there is no intersection:

1. the projection of EFGH on AB are all negative or all greater than |AB|;
2. the projection of EFGH on AD are all negative or all greater than |AD|;
3. the projection of ABCD on EF are all negative or all greater than |EF|;
4. the projection of ABCD on EH are all negative or all greater than |EH|;

Otherwise, the two rectangles intersect with each other.

This approach is simpler than the general polygon intersection algorithm as it only needs simple projections. In the contrast, the general approach requires a point-in-polygon algorithm and a line intersection algorithm.

This approach is also faster. If the rectangles are mostly not overlapping, the algorithm is likely to stop after one or two checks. In the worst case, it involves 4 projection operations. In the contrast, the general approach requires 8 PIP checks and 16 line segment intersection checks. As projection can be easily vectorized, this can be a boost to the speed.