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

geometryrectangles

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

Best Answer

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$

Related Solutions

[Math] the simplest way to convert two overlapping rectangles into a set of non-overlapping rectangles

This problem is well-studied in computer graphics, because, at its core, it is a special case of clipping. Two traditional solutions are the Weiler–Atherton clipping algorithm, and the Sutherland–Hodgman clipping algorithm. Both are more general than you need. But using the search term "rectangle clipping" will lead you to specific code, e.g., this C++ code. Finally, this question might be better asked at StackExchange. For example: "How to subtract a rectangle from another?."

Geometry – Simplest Way to Calculate Intersection Area of Two Rectangles

Uses only max and min (drag the squares to see the calculation. Forget about most of the code, the calculation is those two lines with the min and max):

http://jsfiddle.net/Lqh3mjr5/

You can also reduce min to max here (or the opposite), i.e. $min\{a,b\} = -max\{-a,-b\}$.

First compute the bounding rectangles rect1 and rect2 with the following properties:

rect = {
  left: x1,
  right: x1 + x2,
  top: y1,
  bottom: y1 + y2,
}

The overlap area can be computed as follows:

x_overlap = Math.max(0, Math.min(rect1.right, rect2.right) - Math.max(rect1.left, rect2.left));
y_overlap = Math.max(0, Math.min(rect1.bottom, rect2.bottom) - Math.max(rect1.top, rect2.top));
overlapArea = x_overlap * y_overlap;

Best Answer

Related Solutions

[Math] the simplest way to convert two overlapping rectangles into a set of non-overlapping rectangles

Geometry – Simplest Way to Calculate Intersection Area of Two Rectangles

Related Question