Rob Burke Rob Burke - 4 months ago 26
C++ Question

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?

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

or, using Cartesian coordinates...

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 equivalent to:

  • A's Left Edge to left of B's right edge, [RectA.Left < RectB.Right], and
  • A's right edge to right of B's left edge, [RectA.Right > RectB.Left], and
  • A's top above B's bottom, [RectA.Top > RectB.Bottom], and
  • A's bottom below B's Top [RectA.Bottom < RectB.Top]

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