Rectangle Area
Medium · Math & Geometry · Explanation and code example
Subtract Rectangle Intersection
How it works
The union area is the sum of the two rectangle areas minus their overlap. The overlap width and height come from the intersection of the two axis intervals, with a negative or zero extent treated as no overlap.
Steps
- Compute each rectangle area.
- Find the intersecting x and y extents and clamp them at zero.
- Subtract overlap width times height from the area sum.
Complexity
- Time: O(1).
- Space: O(1).
Things to watch for
- Touching edges have zero overlap area.
- Coordinates may be negative.
- Subtract only the intersection, rather than a bounding rectangle.
Python code example
class Solution:
def computeArea(self,
A: int, B: int, C: int, D: int,
E: int, F: int, G: int, H: int) -> int:
x = min(C, G) - max(A, E) if max(A, E) < min(C, G) else 0
y = min(D, H) - max(B, F) if max(B, F) < min(D, H) else 0
return (C - A) * (D - B) + (G - E) * (H - F) - x * y
C++ code example
class Solution {
public:
int computeArea(long A, long B, long C, long D, //
long E, long F, long G, long H) {
const long x = max(A, E) < min(C, G) ? (min(C, G) - max(A, E)) : 0;
const long y = max(B, F) < min(D, H) ? (min(D, H) - max(B, F)) : 0;
return (C - A) * (D - B) + (G - E) * (H - F) - x * y;
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.