Two Rectangles intersection

Question

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?

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

score 98 · Accepted Answer · edited Feb 28 '15 at 02:06

98

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

edited Feb 28 '15 at 02:06

meetar

7,443
8
42
73

answered Nov 15 '12 at 01:58

Tao Peng

2,688
22
20

4

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
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. – Topher Hunt Sep 29 '14 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 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

score 6 · Answer 2 · answered May 26 '14 at 11:50

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

score 3 · Answer 3 · answered Jul 07 '17 at 06:25

3

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

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

answered Jul 07 '17 at 06:25

score 0 · Answer 4 · answered Sep 15 '13 at 14:57

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;
}

Darrel Lee · Answer 5 · 2015-07-22T01:08:56.760

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)

B is above A
B is below A
B is left of A
B is right of A

jepaljey · Answer 6 · 2017-11-24T19:08:38.253

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

score 0 · Answer 7 · answered Oct 17 '22 at 21:46

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

score 0 · Answer 8 · answered Dec 25 '22 at 10:55

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

answered Dec 25 '22 at 10:55

Marina

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](/help/how-to-answer). – Community Dec 26 '22 at 11:23

score -1 · Answer 9 · answered Oct 02 '16 at 23:48

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

answered Oct 02 '16 at 23:48

Suresh

1

That means it is not a general solution – Enamul Hassan Oct 03 '16 at 00:08

Two Rectangles intersection

9 Answers9

Linked

Related