1
$\begingroup$

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.

enter image description here

$\endgroup$
  • 1
    $\begingroup$ Can you give more precisions? Around which point can they rotate? What are the parameters of your problem etc.?? $\endgroup$ – Martigan May 12 '15 at 12:59
  • $\begingroup$ Can they be rotated about any corner or just one of them? $\endgroup$ – Gregory Grant May 12 '15 at 13:04
  • $\begingroup$ They can be rotated around any point. The angle can be detected from three points $\endgroup$ – Semen Tykhonenko May 12 '15 at 13:05
  • $\begingroup$ @Semen Tykhonenko . About definition of "intersect" : In the case of a small rectangle entirely inside a big rectangle, what do you say : intersect or not intersect ? I mean : is it the intersection of the surface of the rectangles, or is it the intersection of the edges that are considered ? $\endgroup$ – JJacquelin May 12 '15 at 13:19
  • $\begingroup$ JJacquelin, not intersect $\endgroup$ – Semen Tykhonenko May 12 '15 at 13:21
0
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ This will not work for a case, where two rectangles intersect each other like 'X' character. $\endgroup$ – Semen Tykhonenko May 12 '15 at 13:15
  • $\begingroup$ @SemenTykhonenko It will work. Perhaps you have an old version of the post? $\endgroup$ – dtldarek May 12 '15 at 13:18
  • $\begingroup$ How can I check if two edges intersect? $\endgroup$ – Semen Tykhonenko May 12 '15 at 13:22
  • $\begingroup$ @SemenTykhonenko Two lines $AB$ and $CD$ intersect if $A$ and $B$ are on different sides of $CD$ and $C$ and $D$ are on different sides of $AB$. Four cross products and you are done. $\endgroup$ – dtldarek May 12 '15 at 13:25
0
$\begingroup$

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.).

$\endgroup$

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.