Determine If Two Rectangles Overlap
May 12, 2011 in Uncategorized
Given two axis-aligned rectangles A and B. Write a function to determine if the two rectangles overlap.
Hint:
If you are coming up with a complicated set of conditionals, you might think too hard. There is an easier way. Try to think in the opposite direction.
Two overlapping rectangles. A rectangle can be defined by its upper left and lower right corner.
Solution:
Assume that the two rectangles are given as point (P1, P2) and (P3, P4) respectively. One direct way to attempt this problem is when two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle. Do keep in mind of the following cases:
More overlapping rectangles cases to consider.
As you can see, the conditionals can be pretty complicated as there are a total eight of them. Can we simplify it further?
A much easier and better approach would be to think from the opposite. How about asking yourself how the two rectangles cannot overlap each other? Two rectangles do not overlap when one is above/below, or to the left/right of the other rectangle.
The condition’s expression is:
! ( P2.y < P3.y || P1.y > P4.y || P2.x < P3.x || P1.x > P4.x )
Using De Morgan’s law, we can further simplify the above expression to:
( P2.y = P3.y && P1.y = P4.y && P2.x = P3.x && P1.x = P4.x )
Further Thoughts:
- What if the two rectangles are not necessarily axis-aligned? (That is, the rectangles can be rotated around its center at a certain angle.) Solving this problem requires more Math and understanding of linear algebra, so if you’re interested see my post on: How to determine if a point is inside a rectangle.
- Given a list of rectangles, how would you determine the set of overlapping rectangles efficiently? Why would this be useful? Imagine you have a number of windows opened on your desktop. The operating system would need to know the overlapped windows in order to repaint the dirty region as windows are being moved around.
battosai said on May 13, 2011
Given two rectangles consider their left bottom coordinates – (x1, y1) and (x2, y2) and their length and breadth – L1, B1 & L2, B2 respectively. Call rectangle with smaller x coordinate as rect A, the other one rect B.
Now for A and B to intersect:
segment (x1, y1) – (x1, y1+B1) must intersect with (x2, y2) – (x2, y2+B2)
and
segment (x1, y1) – (x1+L1, y1) must intersect with (x2, y2) – (x2 + L2, y2).
Sophie Che said on May 13, 2011
Suppose rect A is (X_A1, X_A2, Y_A1, Y_A2) and rect B is (X_B1, X_B2, Y_B1, Y_B2), where X_A1 < X_A2, Y_A1 < Y_A2, …
Start from the basic idea: compare the x coordinates,
bool x_ins = false;
if (X_A1 X_B1);
else x_ins = (X_A1 X_B1) && (X_A1 Y_B1) && (Y_A1 < Y_B2) );
}
Sophie Che said on May 13, 2011
Notice that we don’t need to compare X_A1 and X_B1 at all. Thus, we have:
jeff said on July 26, 2011
Your expression is wrong according to your graph, it should be:
! ( P2.y > P3.y || P1.y < P4.y || P2.x P4.x )
=>
( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )
jeff said on July 26, 2011
Ah, it eats my answer!
Your expression is wrong according to your graph, it should be:
! ( P2.y > P3.y || P1.y < P4.y || P2.x P4.x )
=>
( P2.y ≤ P3.y && P1.y ≥ P4.y && P2.x ≥ P3.x && P1.x ≤ P4.x )
jeff said on July 26, 2011
cwy said on August 29, 2011
Consider the following example, the corner of one rectangle does not necessarily contain in another, does the solution work for this case?
____
| |
___|___|___
| | | |
| | | |
|___|___|___|
| |
|___|
cwy said on August 29, 2011
sorry for the messed graph, the corners of the first rectangle is (0,1) and (10,0) and the second rectangle (3,3) (4,-4)
Adam said on September 6, 2011
Another way to think about this:
For two axis-aligned rectangles A and B, with axis-aligned bounding box C,
A and B do NOT intersect if:
C.width > (A.width + B.width)
OR
C.height > (A.height + B.height)
Ashok Koyi said on November 11, 2011
How do you compute that C?
Gators07 said on November 17, 2011
How would this work for a two rectangles which overlap so as to make a symbol like + ?
chaos said on December 8, 2011
1337c0d3r, I don’t think the statement you made is correct:
” when two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle”
Try the following case:
__
____|__|_____
|___ |__|____|
|__|
chaos said on December 8, 2011
Sorry, the drawing above is messed up. I find a picture on the Internet that describes what I attempted to draw:
http://enchantia.com/graphapp/doc/tech/overlap.gif
Although the rectangles are overlapped, none of their corners is being contained.
liny said on March 13, 2012
It’s better to consider the overlap problem of two lines firstly, because this one is easier to solve and gives good hits to our real problem.
Lin said on November 17, 2012
Can I think it like this? If the Rectangles satisfy one of the following conditions, those two will overlap:
p1.x<=p3.x=p1.y
p3.x<=p1.x=p3.y
Hardy said on January 6, 2013
How about seeing the distance between their repsective coordinates of centers and if it is less than half of their side ??
Yi Shan said on March 21, 2013
“One direct way to attempt this problem is when two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle. ”
The above statement is not correct.
Yi Shan said on March 21, 2013
Please check http://technologiquepanorama.files.wordpress.com/2009/02/overlap21.gif?w=386&h=137
Y Wu said on April 9, 2013
See http://gamemath.com/2011/09/detecting-whether-two-boxes-overlap/
bool BoxesIntersect(const Box2D &a, const Box2D &b)
{
if (a.max.x b.max.x) return false; // a is right of b
if (a.max.y b.max.y) return false; // a is below b
return true; // boxes overlap
}
Terry said on April 11, 2013
bool BoxesIntersect(const Box2D &a, const Box2D &b)
{
if (p2.x p4.x) return false; // a is right of b
if (p1.y p3.y) return false; // a is below b
return true; // boxes overlap
}