Determine if two rectangles overlap each other?

Question

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 you perform subtraction x or y coordinates corresponding to the vertices of the two facing each rectangle, if the results are the same sign, the two rectangle do not overlap axes that" (i am sorry, i am not sure my translation is correct)

Source: http://www.ieev.org/2009/05/kiem-tra-hai-hinh-chu-nhat-chong-nhau.html

Answer 2

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 3

bool Square::IsOverlappig(Square &other)
{
    bool result1 = other.x >= x && other.y >= y && other.x <= (x + width) && other.y <= (y + height); // other's top left falls within this area
    bool result2 = other.x >= x && other.y <= y && other.x <= (x + width) && (other.y + other.height) <= (y + height); // other's bottom left falls within this area
    bool result3 = other.x <= x && other.y >= y && (other.x + other.width) <= (x + width) && other.y <= (y + height); // other's top right falls within this area
    bool result4 = other.x <= x && other.y <= y && (other.x + other.width) >= x && (other.y + other.height) >= y; // other's bottom right falls within this area
    return result1 | result2 | result3 | result4;
}

Answer 4

Java code to figure out if Rectangles are contacting or overlapping each other
...

        for (int i = 0;i < n;i++) {
          for (int j = 0;j < n; j++) {
            if (i != j) {
                Rectangle rectangle1 = rectangles.get(i);
                Rectangle rectangle2 = rectangles.get(j);

                int l1 = rectangle1.l; //left
                int r1 = rectangle1.r; //right
                int b1 = rectangle1.b; //bottom
                int t1 = rectangle1.t; //top

                int l2 = rectangle2.l;
                int r2 = rectangle2.r;
                int b2 = rectangle2.b;
                int t2 = rectangle2.t;

                boolean topOnBottom = t2 == b1;
                boolean bottomOnTop = b2 == t1;
                boolean topOrBottomContact = topOnBottom || bottomOnTop;

                boolean rightOnLeft = r2 == l1;
                boolean leftOnRight = l2 == r1;
                boolean rightOrLeftContact = leftOnRight || rightOnLeft;

                boolean leftPoll = l2 <= l1 && r2 >= l1;
                boolean rightPoll = l2 <= r1 && r2 >= r1;
                boolean leftRightInside = l2 >= l1 && r2 <= r1;
                boolean leftRightPossiblePlaces = leftPoll || rightPoll || leftRightInside;

                boolean bottomPoll = t2 >= b1 && b2 <= b1;
                boolean topPoll = b2 <= b1 && t2 >= b1;
                boolean topBottomInside = b2 >= b1 && t2 <= t1;
                boolean topBottomPossiblePlaces = bottomPoll || topPoll || topBottomInside;


                boolean topInBetween = t2 > b1 && t2 < t1;
                boolean bottomInBetween = b2 > b1 && b2 < t1;
                boolean topBottomInBetween = topInBetween || bottomInBetween;

                boolean leftInBetween = l2 > l1 && l2 < r1;
                boolean rightInBetween = r2 > l1 && r2 < r1;
                boolean leftRightInBetween = leftInBetween || rightInBetween;

                if ( (topOrBottomContact && leftRightPossiblePlaces) || (rightOrLeftContact && topBottomPossiblePlaces) ) {
                    path[i][j] = true;
                }
            }
        }
    }

...

Answer 5

Here's how it's done in the Java API:

public boolean intersects(Rectangle r) {
    int tw = this.width;
    int th = this.height;
    int rw = r.width;
    int rh = r.height;
    if (rw <= 0 || rh <= 0 || tw <= 0 || th <= 0) {
        return false;
    }
    int tx = this.x;
    int ty = this.y;
    int rx = r.x;
    int ry = r.y;
    rw += rx;
    rh += ry;
    tw += tx;
    th += ty;
    //      overflow || intersect
    return ((rw < rx || rw > tx) &&
            (rh < ry || rh > ty) &&
            (tw < tx || tw > rx) &&
            (th < ty || th > ry));
}

Answer 6

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