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

0Sophie 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) );

}

0Sophie Che said on May 13, 2011

Notice that we don’t need to compare X_A1 and X_B1 at all. Thus, we have:

-1jeff 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 )

+9jeff 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 )

+10jeff said on July 26, 2011

+1sunvssoon said on October 3, 2013

I agree with u

-1cwy 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?

____

| |

___|___|___

| | | |

| | | |

|___|___|___|

| |

|___|

-1cwy 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)

-1Adam 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)

+1Ashok Koyi said on November 11, 2011

How do you compute that C?

-1Anwit said on January 16, 2014

Thanks… this is useful…

0Gators07 said on November 17, 2011

How would this work for a two rectangles which overlap so as to make a symbol like + ?

-1chaos 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:

__

____|__|_____

|___ |__|____|

|__|

-1chaos 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.

-1liny 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.

-1Lin 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

-1Hardy 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 ??

-1Yi 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.

0Yi Shan said on March 21, 2013

Please check http://technologiquepanorama.files.wordpress.com/2009/02/overlap21.gif?w=386&h=137

-1Y 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 bif (a.max.y

b.max.y) return false; // a is below breturn true; // boxes overlap

}

0Terry 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

}

-1Sumit said on May 27, 2013

To embed your code, please use

.

-1Mayank said on January 30, 2014

Here is a code that I believe should print ‘YES’ if rectangles overlap, otherwise ‘NO’…

0Andreas Schuldei said on March 5, 2014

you write

but clearly something was lost on the way.

i assume you mean

+1Andreas Schuldei said on March 5, 2014

i guess something in this websites code is flawed, it eats stuff!

0abhishek samanta said on March 22, 2014

The statement “two rectangles overlap, one rectangle’s corner point(s) must contain in the other rectangle. ” is clearly wrong.

0Pranaya said on March 28, 2014

This is written in Java: Hope this will help

————————————————–

import java.util.Arrays;

public class Rectangle {

public class Point {

/*

* This is a 2D point with coordinate (x,y)

*/

double x;

double y;

Point() {

this.x = 0;

this.y = 0;

}

Point(double x, double y) {

this.x = x;

this.y = y;

}

public String show() {

return “( ” + x + ” , ” + y + ” )”;

}

public boolean isEqual(Point p) {

return this.x == p.x && this.y == p.y;

}

}

/**

* Rectangle is constructed by any two corner points p1 and p2

*/

Point p1, p2;

public Rectangle() {

this.p1 = new Point();

this.p2 = new Point();

}

public Rectangle(double x1, double y1, double x2, double y2) {

this.p1 = new Point(x1, y1);

this.p2 = new Point(x2, y2);

}

public Rectangle(Point p1, Point p2) {

this.p1 = p1;

this.p2 = p2;

}

public void show() {

System.out.println(“———- ” + this + ” ————”);

System.out.println(“Point p1 is : ” + p1.show());

System.out.println(“Point p2 is : ” + p2.show());

}

public boolean validate() {

if (this.p1.x != this.p2.x && this.p1.y != this.p2.y)

return true;

else

return false;

}

public double getArea() {

double height = Math.abs(p1.y – p2.y);

double width = Math.abs(p1.x – p2.x);

return height * width;

}

/**

* This is like a utility method

*

* @param rect1

* @param rect2

* @return

*/

public static Rectangle getIntersectedRectangle(Rectangle rect1,

Rectangle rect2) {

if (!hasCommonArea(rect1, rect2))

return null;

/*

* If Common area exists then find Rectangle

*

* Two x-coordinate of intersected rectangle will be middle two

* x-coordinate of four x-coordinates

*/

double[] dXArr = new double[] { rect1.p1.x, rect1.p2.x, rect2.p1.x,

rect2.p2.x };

double[] dYArr = new double[] { rect1.p1.y, rect1.p2.y, rect2.p1.y,

rect2.p2.y };

Arrays.sort(dXArr);

Arrays.sort(dYArr);

Rectangle inRect = new Rectangle(dXArr[1], dYArr[1], dXArr[2], dYArr[2]);

inRect.show();

return inRect;

}

/**

* This is like a utility method

*

* @param rect1

* @param rect2

* @return

*/

public static boolean hasCommonArea(Rectangle rect1, Rectangle rect2) {

boolean flag1 = true, flag2 = true;

if ((Math.min(rect1.p1.x, rect1.p2.x) >= Math.max(rect2.p1.x,

rect2.p2.x))

|| (Math.max(rect1.p2.x, rect1.p2.x) = Math.max(rect2.p1.y,

rect2.p2.y))

|| (Math.max(rect1.p2.y, rect1.p2.y) <= Math.min(rect2.p1.y,

rect2.p2.y))) {

flag2 = false;

}

if (!(flag1 && flag2))

System.out.println("Common Area doesnot exist");

// System.out.println("flag1 " + flag1 + " flag2 :y " + flag2);

return flag1 && flag2;

}

public static void main(String[] args) {

// TODO Auto-generated method stub

Rectangle rect1 = new Rectangle(1, 1, 6, 6);

Rectangle rect2 = new Rectangle(1, 16, 6, 20);

if (null != getIntersectedRectangle(rect1, rect2))

System.out.println("Area is : "

+ getIntersectedRectangle(rect1, rect2).getArea()

+ " sq unit");

}

}

+1rong said on July 17, 2014

According to the graph, it should be:

! ( P2.y > P3.y || P1.y < P4.y || P2.x P4.x )

That is I will compare the one’s lower point with the other’s higher point.

0sabz said on July 22, 2014

The mathematical definition of two overlapped rectangles should be a part of one rectangle is within the other rectangle. The original declaration that one corner of a rectangle is in another rectangle is incorrect. The declaration that two non-overlapping rectangles are side by side or one on top of the other is incorrect either. Some replies have pointed out if the two rectangles form a cross, the can still overlap.

A complete solution is to check if any point of one rectangle is completely inside another rectangle. To do this, find the lower left corner (min, min) and upper right corner (max, max) of the reference rectangle and use the expression, supposing the coordinates of point to be checked is (px, py) and the corners are (low, left) and (upper, right):

lower<=py && py<=upper && left<=px && px<=py.

One can iterate all the points in the rectangle to be checked and exit as soon as any point matches the predicate. A better approach is using binary search. One rectangle overlaps with another rectangle if either the left half or the right half or the upper half or the bottom half of the rectangle overlaps with the other rectangle.

0sabz said on July 22, 2014

The mathematical definition of two overlapped rectangles should be a part of one rectangle is within the other rectangle. The original declaration that one corner of a rectangle is in another rectangle is incorrect. The declaration that two non-overlapping rectangles are side by side or one on top of the other is incorrect either. Some replies have pointed out if the two rectangles form a cross, the can still overlap.

A complete solution is to check if any point of one rectangle is completely inside another rectangle. To do this, find the lower left corner (min, min) and upper right corner (max, max) of the reference rectangle and use the expression, supposing the coordinates of point to be checked is (px, py) and the corners are (low, left) and (upper, right):

lower<=py && py<=upper && left<=px && px<=right.

This works if the rectangles align with the axes,

One can iterate all the points in the rectangle to be checked and exit as soon as any point matches the predicate. A better approach is using binary search. One rectangle overlaps with another rectangle if either the left half or the right half or the upper half or the bottom half of the rectangle overlaps with the other rectangle.

0Richiban said on September 30, 2014

As others have pointed out, the given “solution” will only return true for pairs of rectangles where corners are contained within another rectangle. If we define a rectangle as a centre point combined with a width and a height (rather than a top left corner and bottom right corner) it is easy to calculate the distance between the centres of the two shapes. In order for the two rectangles to be overlapping the x-distance between their centres must be less than their average width AND the y-distance between their centres must be less than their average height. Here’s a solution in F#:

type Point = { x : float; y : float }

type Rectangle = { centre : Point; width : float; height : float }

let overlapping r1 r2 =

let deltaX = r1.centre.x – r2.centre.x |> Math.Abs

let deltaY = r1.centre.y – r2.centre.y |> Math.Abs

let averageWidth = (r1.width + r2.width) / 2.

let averageHeight = (r1.height + r2.height) / 2.

deltaX <= averageWidth && deltaY <= averageHeight

+1