Rob Burke - 1 year ago 81

C++ 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 Source

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

.