57

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?

meetar
  • 7,099
  • 7
  • 41
  • 71
Majid Laissi
  • 18,348
  • 18
  • 64
  • 104
  • possible duplicate of [Algorithm to detect intersection of two rectangles?](http://stackoverflow.com/questions/115426/algorithm-to-detect-intersection-of-two-rectangles) – Perception Nov 15 '12 at 01:46
  • here's a start on a solution: http://gamedev.stackexchange.com/questions/25818/how-to-implement-a-2d-collision-detection-for-android#40235 – Ray Tayek Nov 15 '12 at 01:48
  • @Perception in the other question `..at an arbitrary angle..` my question is simpler and thus i'm looking for a simpler answer – Majid Laissi Nov 15 '12 at 01:50
  • @RayTayek it sure is a **start**, thanks :) – Majid Laissi Nov 15 '12 at 01:51
  • Possible duplicate of [Determine if two rectangles overlap each other?](http://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other) – Dakusan Dec 16 '16 at 16:45

7 Answers7

94
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
meetar
  • 7,099
  • 7
  • 41
  • 71
Tao Peng
  • 2,578
  • 21
  • 20
  • 3
    Doesn't work if one rectangle is completely inside the other. – Ankesh Anand Sep 26 '14 at 12:43
  • @AnkeshAnand could you elaborate? When I run through this algorithm, it appears to handle the "completely inside" situation fine. – Topher Hunt Sep 28 '14 at 23:31
  • 1
    @TopherHunt It detects an intersection in this case where there isn't any. – Ankesh Anand Sep 29 '14 at 13:37
  • 1
    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. – Topher Hunt Sep 29 '14 at 20:51
  • 14
    @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 May 12 '15 at 19:59
  • In some cases it's interesting to allow a "proximity tolerancy", so you can admit crossing when both rectangles are not separated by too much distance. Code becomes this : float epsilon = 0.1; if (X1+W1 – Francis Pierot Oct 13 '16 at 09:23
  • If you're doing intersection with four coordinates, this formula will not work for all point orderings. – Azmisov Nov 13 '16 at 02:48
  • My first question is why there's () around the expression, but not around the sums... – Henrik Erlandsson Sep 07 '17 at 13:19
6

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

Zar E Ahmer
  • 32,807
  • 18
  • 222
  • 281
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;
}
Balamurugan A
  • 1,786
  • 2
  • 16
  • 19
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
Darrel Lee
  • 2,154
  • 19
  • 22
0

If the rectangles' coordinates of the lower left corner and upper right corner are :
(r1x1, r1y1), (r1x2, r1y2) for rect1 and
(r2x1, r2y1), (r2x2, r2y2) for rect2
(Python like code below)

    intersect = False
    for x in [r1x1, r1x2]:
        if (r2x1<=x<=r2x2):
            for y in [r1y1, r1y2]:
                if (r2y1<=y<=r2y2):
                    intersect = True
                    return intersect
                else:
                    for Y in [r2y1, r2y2]:
                        if (r1y1<=Y<=r1y2):
                            intersect = True
                            return intersect
        else:  
            for X in [r2x1, r2x2]:
                if (r1x1<=X<=r1x2):
                    for y in [r2y1, r2y2]:
                        if (r1y1<=y<=r1y2):
                            intersect = True
                            return intersect
                        else:
                            for Y in [r1y1, r1y2]:
                                if (r2y1<=Y<=r2y2):
                                    intersect = True
                                    return intersect
    return intersect
jepaljey
  • 15
  • 9
-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.

Suresh
  • 1