60

I have two rectangles characterized by 4 values each :

Left position X, top position Y, width W and height H:

X1, Y1, H1, W1
X2, Y2, H2, W2

Rectangles are not rotated, like so:

+--------------------> X axis
|
|    (X,Y)      (X+W, Y)
|    +--------------+
|    |              |
|    |              |
|    |              |
|    +--------------+
v    (X, Y+H)     (X+W,Y+H)

Y axis

What is the best solution to determine whether the intersection of the two rectangles is empty or not?

5

8 Answers 8

97
if (X1+W1<X2 or X2+W2<X1 or Y1+H1<Y2 or Y2+H2<Y1):
    Intersection = Empty
else:
    Intersection = Not Empty

If you have four coordinates – ((X,Y),(A,B)) and ((X1,Y1),(A1,B1)) – rather than two plus width and height, it would look like this:

if (A<X1 or A1<X or B<Y1 or B1<Y):
    Intersection = Empty
else:
    Intersection = Not Empty
8
  • 4
    Doesn't work if one rectangle is completely inside the other. Commented Sep 26, 2014 at 12:43
  • @AnkeshAnand could you elaborate? When I run through this algorithm, it appears to handle the "completely inside" situation fine. Commented Sep 28, 2014 at 23:31
  • 1
    @TopherHunt It detects an intersection in this case where there isn't any. Commented Sep 29, 2014 at 13:37
  • 2
    Ah got it. thanks for clarifying. I didn't pick up on that because in my case I care about overlap, which this algorithm handles perfectly. Commented Sep 29, 2014 at 20:51
  • 16
    @AnkeshAnand intersection means boolean intersection - i.e. whether some area of rectangle 1 overlaps some area of rectangle 2 - not whether the "outlines" of the rectangles cross each other.
    – d7samurai
    Commented May 12, 2015 at 19:59
5

Best example..

/**
 * Check if two rectangles collide
 * x_1, y_1, width_1, and height_1 define the boundaries of the first rectangle
 * x_2, y_2, width_2, and height_2 define the boundaries of the second rectangle
 */
boolean rectangle_collision(float x_1, float y_1, float width_1, float height_1, float x_2, float y_2, float width_2, float height_2)
{
  return !(x_1 > x_2+width_2 || x_1+width_1 < x_2 || y_1 > y_2+height_2 || y_1+height_1 < y_2);
}

and also one other way see this link ... and code it your self..

0
3

Should the two rectangles have the same dimensions you can do:

if (abs (x1 - x2) < w && abs (y1 - y2) < h) {
    // overlaps
}
0

I just tried with a c program and wrote below.

#include<stdio.h>

int check(int i,int j,int i1,int j1, int a, int b,int a1,int b1){
    return (\
    (((i>a) && (i<a1)) && ((j>b)&&(j<b1))) ||\ 
    (((a>i) && (a<i1)) && ((b>j)&&(b<j1))) ||\ 
    (((i1>a) && (i1<a1)) && ((j1>b)&&(j1<b1))) ||\ 
    (((a1>i) && (a1<i1)) && ((b1>j)&&(b1<j1)))\
    );  
}
int main(){
    printf("intersection test:(0,0,100,100),(10,0,1000,1000) :is %s\n",check(0,0,100,100,10,0,1000,1000)?"intersecting":"Not intersecting");
    printf("intersection test:(0,0,100,100),(101,101,1000,1000) :is %s\n",check(0,0,100,100,101,101,1000,1000)?"intersecting":"Not intersecting");
    return 0;
}
0

Using a coordinate system where (0, 0) is the left, top corner.

I thought of it in terms of a vertical and horizontal sliding windows and come up with this:

(B.Bottom > A.Top && B.Top < A.Bottom) && (B.Right > A.Left && B.Left < A.Right)

Which is what you get if you apply DeMorgan’s Law to the following:

Not (B.Bottom < A.Top || B.Top > A.Bottom || B.Right < A.Left || B.Left > A.Right)

  1. B is above A
  2. B is below A
  3. B is left of A
  4. B is right of A
0

Circle approach is more straightforward. I mean when you define a circle as a center point and radius. Same thing here except you have a horizontal radius (width / 2) and a vertical one (height /2) and 2 conditions for horizontal and for vertical distance.

abs(cx1 – cx2) <= hr1 + hr2 && abs(cy1 - cy2) <= vr1 + vr2

If you need to exclude the case with sides not intersecting filter out these with one rectangle smaller in both dimensions and not enough distance (between centers) from the bigger one to reach one of its edges.

abs(cx1 – cx2) <= hr1 + hr2 && abs(cy1 - cy2) <= vr1 + vr2 &&
!(abs(cx1 – cx2) < abs(hr1 - hr2) && abs(cy1 - cy2) < abs(vr1 - vr2) && sign(hr1 - hr2) == sign(vr1 – vr2))
0
Rectangle = namedtuple('Rectangle', 'x y w h')

def intersects(rect_a: Rectangle, rect_b: Rectangle):
    if (rect_a.x + rect_a.w < rect_b.x) or (rect_a.x > rect_b.x + rect_b.w) or (rect_a.y + rect_a.h < rect_b.y) or (rect_a.y > rect_b.y + rect_b.h):
        return False

    else:
        return True
1
  • Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center.
    – Community Bot
    Commented Dec 26, 2022 at 11:23
-1

if( X1<=X2+W2 && X2<=X1+W1 && Y1>=Y2-H2 && Y2>=Y1+H1 ) Intersect

In the question Y is the top position..

Note: This solution works only if rectangle is aligned with X / Y Axes.

1
  • That means it is not a general solution Commented Oct 3, 2016 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.