How to check if two rectangles overlap each other
Problem Statement
An axis-aligned rectangle is represented as a list [x1, y1, x2, y2], where (x1, y1) is the bottom-left corner coordinate and (x2, y2) is the top-right corner coordinate.
Its top and bottom edges are perpendicular to the X-axis, while its left and right edges are perpendicular to the Y-axis.
If the area of their intersection is positive, two rectangles overlap. Two rectangles that touch at the corners or edges do not overlap.
If two axis-aligned rectangles, rec1 and rec2, overlap, it returns true, otherwise, it returns false.
Example 1
- Input:
rec1=[0,0,4,4],rec2=[2,2,3,3] - Output:
true
Example 2
- Input:
rec1=[0,0,2,2],rec2=[2,0,3,1] - Output:
false
Solution
Before jumping to the solution, let’s first visualize the examples with the help of a diagram.
In example 1, we can observe that rec 2 has an overlapping area with rec 1. Hence, we can say that the two rectangles are overlapping.
But in example 2, we can observe that only the corners of the rectangles meet each other. According to the problem definition, the two rectangles are not overlapping.
The intuition to solving this problem is using the area. If the rectangles overlap, they have a positive area. Because the intersection’s bounds are axis-aligned, this region must be a rectangle with both dimensions positive.
As a result, we may simplify the problem to detect if two line segments overlap in one dimension.
The algorithm is as follows:
Assume the intersection area is width * height, where width is the intersection of rectangles projected onto the x-axis and height is the same for the y-axis. We want both the numbers to be positive.
Turning the algorithm above into code:
- For width:
min(rec1[2], rec2[2]) > max(rec1[0], rec2[0]) - For height:
min(rec1[3], rec2[3]) > max(rec1[1], rec2[1])
The width is positive when the smaller of (the largest x-coordinates) is larger than, the larger of (the smallest x-coordinates).
Similarly, the height is positive when the smaller of the largest y-coordinates is larger than, the larger of the smallest y-coordinates.
Code
import java.util.Arrays;class Main{public static boolean isRectangleOverlap(int[] rec1, int[] rec2) {boolean widthIsPositive = Math.min(rec1[2], rec2[2]) > Math.max(rec1[0], rec2[0]);boolean heightIsPositive = Math.min(rec1[3], rec2[3]) > Math.max(rec1[1], rec2[1]);return ( widthIsPositive && heightIsPositive);}public static void main(String[] args) {int[] rec1 = {0,0,2,2};int[] rec2 = {2,0,3,1};System.out.println("Rectange 1 - " + Arrays.toString(rec1));System.out.println("Rectange 2 - " + Arrays.toString(rec2));boolean isOverlapping = isRectangleOverlap(rec1, rec2);System.out.println(isOverlapping?"The rectangles are overlapping":"The rectangles are not overlapping");}}
Explanation
- Lines 5-9 -
isRectangleOverlap()method is defined that implements the logic defined in the solution section to check if two rectangles overlap. - Line 12 - The dimensions of the first rectangle are defined.
- Line 13 - The dimensions of the second rectangle are defined.
- Line 17 -
isRectangleOverlap()method is invoked to check if the two rectangles overlap.