c++algorithmgeometryoverlaprectangles

Determine if two rectangles overlap each other?


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?


Solution

  • if (RectA.Left < RectB.Right && RectA.Right > RectB.Left &&
         RectA.Top > RectB.Bottom && RectA.Bottom < RectB.Top ) 
    

    or, using Cartesian coordinates

    (With X1 being left coord, X2 being right coord, increasing from left to right and Y1 being Top coord, and Y2 being Bottom coord, increasing from bottom to top -- if this is not how your coordinate system [e.g. most computers have the Y direction reversed], swap the comparisons below) ...

    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:

    So condition for Non-Overlap is

    NON-Overlap => Cond1 Or Cond2 Or Cond3 Or Cond4

    Therefore, a sufficient condition for Overlap is the opposite.

    Overlap => NOT (Cond1 Or Cond2 Or Cond3 Or Cond4)

    De Morgan's law says
    Not (A or B or C or D) is the same as Not A And Not B And Not C And Not D
    so using De Morgan, we have

    Not Cond1 And Not Cond2 And Not Cond3 And Not Cond4

    This is equivalent to:

    Note 1: It is fairly obvious this same principle can be extended to any number of dimensions.
    Note 2: It should also be fairly obvious to count overlaps of just one pixel, change the < and/or the > on that boundary to a <= or a >=.
    Note 3: This answer, when utilizing Cartesian coordinates (X, Y) is based on standard algebraic Cartesian coordinates (x increases left to right, and Y increases bottom to top). Obviously, where a computer system might mechanize screen coordinates differently, (e.g., increasing Y from top to bottom, or X From right to left), the syntax will need to be adjusted accordingly/