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?

Bewick

possible duplicate of Algorithm to detect intersection of two rectangles? – Crim

here's a start on a solution: gamedev.stackexchange.com/questions/25818/… – Stonwin

@Crim in the other question ..at an arbitrary angle.. my question is simpler and thus i'm looking for a simpler answer – Bewick

@RayTayek it sure is a start, thanks :) – Bewick

Possible duplicate of Determine if two rectangles overlap each other? – Levison

Answer 1

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

Guy

Doesn't work if one rectangle is completely inside the other. – Humpy

@AnkeshAnand could you elaborate? When I run through this algorithm, it appears to handle the "completely inside" situation fine. – Mariannmarianna

@TopherHunt It detects an intersection in this case where there isn't any. – Humpy

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

@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. – Slumgullion

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<X2-epsilon or X2+W2<X1-epsilon or Y1+H1<Y2-epsilon or Y2+H2<Y1-epsilon) Intersection = Empty else Intersection = Not Empty – Lanctot

If you're doing intersection with four coordinates, this formula will not work for all point orderings. – Becalmed

My first question is why there's () around the expression, but not around the sums... – Erotomania

Answer 2

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

Leavening

Answer 3

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

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

Roux

Answer 4

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

Brasher

Answer 5

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

Jayme

Answer 6

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

Tern

Answer 7

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

Riviera

Answer 8

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

Fulgent

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

Answer 9

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.

Panda

That means it is not a general solution – Hartzel