Solution: Rectangle Overlap

Statement

An axis-aligned rectangle is represented by a list $[x_1, y_1, x_2, y_2]$, where:

• $(x_1, y_1)$ denotes the coordinates of the bottom-left corner.

• $(x_2, y_2)$ denotes the coordinates of the top-right corner.

The rectangle’s sides are aligned with the axes:

• The top and bottom edges are parallel to the $\text{X-axis}$.

• The left and right edges are parallel to the $\text{Y-axis}$.

Note: Two rectangles are considered to overlap if their intersection forms a region with a positive area. Rectangles that touch only at the edges or corners are not considered to overlap.

Determine if the two axis-aligned rectangles, rec1 and rec2, overlap. Return TRUE if they overlap; otherwise, return FALSE.

Constraints:

• rec1.length $== 4$

• rec2.length $== 4$

• $-10^4 \leq$ rec1[i], rec2[i] $\leq10^4$

• rec1 and rec2 represent a valid rectangle with a non-zero area.

Solution

The solution uses the math and geometry pattern to determine if two axis-aligned rectangles overlap. It simplifies the problem into one-dimensional interval overlaps for the x-axis and y-axis projections. The overlap of two rectangles corresponds to the overlap of these projections, forming a region with positive width and height. Using this geometric insight, the solution checks for overlaps cleanly and seamlessly.

Now, let’s dive deep into the key intuition of the solution:

Rectangle overlap definition:
Two rectangles overlap if the area of their intersection is positive. This means the intersection’s width (x-axis overlap) and height (y-axis overlap) must be positive.

Mathematical representation of width overlap:

The overlap along the x-axis is positive when:

            $\text{min(rec1[2], rec2[2]) > max(rec1[0], rec2[0])}$

Here, $\text{rec1[0]}$ and $\text{rec2[0]}$ are the left boundaries, while $\text{rec1[2]}$ and $\text{rec2[2]}$ are the right boundaries of the rectangles. This ensures that the smaller of the two rectangles’ right boundaries is greater than the larger of their left boundaries.

Mathematical representation of height overlap:

The overlap along the y-axis is positive when:

            $\text{min(rec1[3], rec2[3]) > max(rec1[1], rec2[1])}$

Similarly, $\text{rec1[1]}$ and $\text{rec2[1]}$ are the bottom boundaries, while $\text{rec1[3]}$ and $\text{rec2[3]}$ are the top boundaries of the rectangles. This ensures that the smaller of the two rectangles’ top boundaries is greater than the larger of their bottom boundaries.

Reduction to 1D interval overlap:
The problem is reduced to determining whether two line segments overlap in 1D space. For an axis-aligned rectangle:

• The width is the overlap of its x-axis projection.

• The height is the overlap of its y-axis projection.

So, the width and height overlaps must be positive for the rectangles to overlap. If either overlap is zero or negative, the rectangles do not overlap.

Now, let’s look at the solution steps below:

1. To check width overlap:

   1. Calculate the smallest right boundary: min(rec1[2],rec2[2]).

   2. Calculate the largest left boundary: max(rec1[0],rec2[0]).

   3. Verify if the width overlap is positive by checking if min(rec1[2],rec2[2]) > max(rec1[0],rec2[0]). If TRUE, there is a positive width overlap.

2. To check height overlap:

   1. Calculate the smallest top boundary: min(rec1[3],rec2[3]).

   2. Calculate the largest bottom boundary: max(rec1[1],rec2[1]).

   3. Verify if the height overlap is positive by checking if min(rec1[3],rec2[3]) > max(rec1[1],rec2[1]). If TRUE, there is a positive height overlap.

3. Combine the above conditions and return TRUE if the width and height overlaps are positive. Otherwise, return FALSE.

Let’s look at the following illustration to get a better understanding of the solution: