Determine if two rectangles overlap each other?

Question

Hi folks,

I am trying to write a C++ program that takes the following inputs from the user to construct rectangles (between 2 and 5): height, width, x-pos, y-pos. All of these rectangles will exist parallel to the x and the y axis, that is all of their edges will have slopes of 0 or infinity.

I've tried to implement what is mentioned in this question but I am not having very much luck.

My current implementation does the following:

// Gets all the vertices for Rectangle 1 and stores them in an array -> arrRect1
// point 1 x: arrRect1[0], point 1 y: arrRect1[1] and so on...
// Gets all the vertices for Rectangle 2 and stores them in an array -> arrRect2

// rotated edge of point a, rect 1
int rot_x, rot_y;
rot_x = -arrRect1[3];
rot_y = arrRect1[2];
// point on rotated edge
int pnt_x, pnt_y;
pnt_x = arrRect1[2]; 
pnt_y = arrRect1[3];
// test point, a from rect 2
int tst_x, tst_y;
tst_x = arrRect2[0];
tst_y = arrRect2[1];

int value;
value = (rot_x * (tst_x - pnt_x)) + (rot_y * (tst_y - pnt_y));
cout << "Value: " << value;

However I'm not quite sure if (a) I've implemented the algorithm I linked to correctly, or if I did exactly how to interpret this?

Any suggestions?

Answer 1

if (RectA.X1 < RectB.X2 && RectA.X2 > RectB.X1 &&
    RectA.Y1 < RectB.Y2 && RectA.Y2 > RectB.Y1)

say you have Rect A, and Rect B. Proof is by contradiction. Any one of four conditions guarantees that NO OVERLAP CAN EXIST.

Cond1.  If A's left edge is to the right of the B's right edge,
           -  then A is Totally to right Of B
Cond2.  If A's right edge is to the left of the B's left edge,
           -  then A is Totally to left Of B
Cond3.  If A's top edge is below B's bottom  edge,
           -  then A is Totally below B
Cond4.  If A's bottom edge is above B's top edge,
           -  then A is Totally above B

So condition for Non-Overlap is

Cond1 Or Cond2 Or Cond3 Or Cond4

Therefore, a sufficient condition for Overlap is the opposite (De Morgan)

Not Cond1 AND Not Cond2 And Not Cond3 And Not Cond4

this is equivilent to

A's Left Edge to left of B's right edge  And
A's right edge to right of B's left edge And
A's top above B's bottom And
A's bottom below B's Top

Answer 2

i would think the solution to your problem doesn't involve any multiplication.

Answer 3

@Charles Bretana:

Assuming our rectangle is shaped like so:

d---------c
|         |
|         |
a---------b

RectA.X1 is the X value at point a? RectA.X2 is the X value at point b?

Similar for RectB. Or am I mistaken?

Answer 4

I have implemented a C# version, it is easily converted to C++.

public bool Intersects ( Rectangle rect )
{
  float ulx = Math.Max ( x, rect.x );
  float uly = Math.Max ( y, rect.y );
  float lrx = Math.Min ( x + width, rect.x + rect.width );
  float lry = Math.Min ( y + height, rect.y + rect.height );

  return ulx <= lrx && uly <= lry;
}

Answer 5

Ask yourself the opposite question: How can I determine if two rectangles do not intersect at all? Obviously, a rectangle A completely to the left of rectangle B does not intersect. Also if A is completely to the right. And similarly if A is completely above B or completely below B. In any other case A and B intersect.

What follows may have bugs, but I am pretty confident about the algorithm:

struct Rectangle { int x; int y; int width; int height; };

bool is_left_of(Rectangle const & a, Rectangle const & b) {
   if (a.x + a.width <= b.x) return true;
   return false;
}
bool is_right_of(Rectangle const & a, Rectangle const & b) {
   return is_left_of(b, a);
}

bool not_insersect( Rectangle const & a, Rectangle const & b) {
   if (is_left_of(a, b)) return true;
   if (is_right_of(a, b)) return true;
   // Do the same for top/bottom...
 }

bool insersect(Rectangle const & a, Rectangle const & b) {
  return !not_insersect(a, b);
}

Answer 6

struct Rect
{
    Rect(int x1, int x2, int y1, int y2)
    : x1(x1), x2(x2), y1(y1), y2(y2)
    {
        assert(x1 < x2);
        assert(y1 < y2);
    }

    int x1, x2, y1, y2;
};

bool
overlap(const Rect &r1, const Rect &r2)
{
    // The rectangles don't overlap if
    // one rectangle's minimum in some dimension 
    // is greater than the other's maximum in
    // that dimension.

    bool noOverlap = r1.x1 > r2.x2 ||
                     r2.x1 > r1.x2 ||
                     r1.y1 > r2.y2 ||
                     r2.x1 > r1.y2;

    return !noOverlap;
}

Answer 7

In the question, you link to the maths for when rectangles are at arbitrary angles of rotation. If I understand the bit about angles in the question however, I interpret that all rectangles are perpendicular to one another.

A general knowing the area of overlap formula is:

Using the example:

   1   2   3   4   5   6

1  +---+---+
   |       |   
2  +   A   +---+---+
   |       | B     |
3  +       +   +---+---+
   |       |   |   |   |
4  +---+---+---+---+   +
               |       |
5              +   C   +
               |       |
6              +---+---+

1) collect all the x coordinates (both left and right) into a list, then sort it and remove duplicates

1 3 4 5 6

2) collect all the y coordinates (both top and bottom) into a list, then sort it and remove duplicates

1 2 3 4 6

3) create a 2D array by number of gaps between the unique x coordinates * number of gaps between the unique y coordinates.

4 * 4

4) paint all the rectangles into this grid, incrementing the count of each cell it occurs over:

   1   3   4   5   6

1  +---+
   | 1 | 0   0   0
2  +---+---+---+
   | 1 | 1 | 1 | 0
3  +---+---+---+---+
   | 1 | 1 | 2 | 1 |
4  +---+---+---+---+
     0   0 | 1 | 1 |
6          +---+---+

5) As you paint the rectangles, its easy to intercept the overlaps.

Answer 8

Asuming the points for all rectangles are always set in this order:

P1----P2
|      |
P3----P4

then, the problem is just only to check if the point P1 of the second rectangle falls into the first rectangle, that is:

def Intersects (Rect1, Rect2)
    return (Rect1.P1.x < Rect2.P1.x < Rect1.P2.x) and (Rect1.P1.y > Rect2.P1.y > Rect1.P3.y)

You can get an idea.

Answer 9

There's a great interactive tutorial on collision detection at http://www.harveycartel.org/metanet/tutorials/tutorialA.html. He starts off with perpendicular rectangles, then moves onto all kinds of other shapes.

Answer 10

struct Rect
{
   Rect(int x1, int x2, int y1, int y2)
   : x1(x1), x2(x2), y1(y1), y2(y2)
   {
       assert(x1 < x2);
       assert(y1 < y2);
   }

   int x1, x2, y1, y2;
};

//some area of the r1 overlaps r2
bool overlap(const Rect &r1, const Rect &r2)
{
    return r1.x1 < r2.x2 && r2.x1 < r1.x2 &&
           r1.y1 < r2.y2 && r2.x1 < r1.y2;
}

//either the rectangles overlap or the edges touch
bool touch(const Rect &r1, const Rect &r2)
{
    return r1.x1 <= r2.x2 && r2.x1 <= r1.x2 &&
           r1.y1 <= r2.y2 && r2.x1 <= r1.y2;
}

Answer 11

Don't think of coordinates as indicating where pixels are. Think of them as being between the pixels. That way, the area of a 2x2 rectangle should be 4, not 9.

bool bOverlap = !((A.Left >= B.Right || B.Left >= A.Right)
               && (A.Bottom >= B.Top || B.Bottom >= A.Top));

Answer 12

This is similar to the question about comparing date ranges, here.

The same type of solution applies, except that it is in two directions.

Answer 13

This answer should be the top answer:

if the rectangles overlap then the overlap area will be greater than zero. Now let us find the overlap area:

if they overlap then the left edge of overlap-rect will be the max(r1.x1,r2.x1) and right edge will be min(r1.x2,r2.x2). so the length of the overlap will be min(r1.x2,r2.x2)-max(r1.x1,r2.x1)

so the area will be: area = (max(r1.x1, r2.x1) - min(r1.x2, r2.x2)) * (max(r1.y1, r2.y1) - min(r1.y2, r2.y2))

if area = 0 then they dont overlap. Simple isn't it?

Answer 14

function collision(r1, r2) 
{
    var dx = Math.abs(r2.x - r1.x) + r2.w;
    var dy = Math.abs(r2.y - r1.y) + r2.h;

    return (dx < r1.w + r2.w && dy < r1.h + r2.h);
}

if (collision(rectangleA, rectangleB)) 
{
    // Collision!
}

Answer 15

sorry to be a dumb. how do i add this to my favourites?