# Check the overlapping area of two rectangles (tricky)

• I guess the most tricky part of this problem is to check whether two rectangles have an overlapping if so how to calculate it.

So here is my "verbose" solution in Java. Hope it is self-explanatory.

``````/**
* Calculate the overlapping area of two rectangles.
*/
public int overlapArea(int A, int B, int C, int D,
int E, int F, int G, int H) {
/* Check if there is indeed an overlap.
* e.g.  E >= C  i.e. the most left point of the rectangle (EFGH) is
*       on the right side of the most right point of the rectangle (ABCD),
*       therefore there is no overlapping.
*/
if ( (E>=C) || (F>= D) || (A>=G) || (B >= H) )
return 0;

/* bottom left point of the overlapping area. */
int bl_x = Math.max(A, E);
int bl_y = Math.max(B, F);

/* top right point of the overlapping area. */
int tr_x = Math.min(C, G);
int tr_y = Math.min(D, H);

return (tr_x - bl_x) * (tr_y - bl_y);
}

/**
* Calculate the area of a single rectangle.
*/
public int computeArea(int A, int B, int C, int D) {
return (C-A) * (D-B);
}

/**
* Find the total area covered by two rectilinear rectangles in a 2D plane.
* Each rectangle is defined by its bottom left corner and top right corner.
*/
public int computeArea(int A, int B, int C, int D,
int E, int F, int G, int H) {
// The addition of area of the two rectangles minus the overlapping area.
return computeArea(A, B, C, D) + computeArea(E, F, G, H) -
overlapArea(A, B, C, D, E, F, G, H);
}``````

• "bl" and "tr" aren't quite self-explanatory... (I know what the values are but I still don't know what your names mean)

• Thanks for pointing that out. I've added more comments in the code. Hope it is clearer now.

• Aaah, yes, bottom-left and top-right makes sense. Thanks. I think the main reason I didn't get it was that I wasn't thinking of two corners. I was thinking of independent left, right, top and bottom. That's why I couldn't make the connection.

• Quite clean solution. Mine is a convoluted one!

• `````` class Solution:
def computeArea(self, A, B, C, D, E, F, G, H):
SA=abs((C-A)*(D-B))
SB=abs((G-E)*(H-F))
if E>=C or A>=G or B>=H or F>=D:
return SA+SB
else:
x1=min(G,C)
x2=max(A,E)
y1=min(D,H)
y2=max(B,F)
return SA+SB-abs((x1-x2)*(y1-y2))
``````

• ``````class Solution:
def computeArea(self, A, B, C, D, E, F, G, H):
SA=abs((C-A)*(D-B))
SB=abs((G-E)*(H-F))
if E>=C or A>=G or B>=H or F>=D:
return SA+SB
else:
x1=min(G,C)
x2=max(A,E)
y1=min(D,H)
y2=max(B,F)
return SA+SB-abs((x1-x2)*(y1-y2))
``````

• Good summary.

• Here I would like to add some additional explanation to the idea of checking whether two rectangles have an overlap.

``````            (C, D)              (G, H)
|-------|           |--------|
|       |           |        |
|-------|           |--------|
(A, B)                (E, F)
``````

As illustrated above, the four points that represent the two rectangles,
actually delimit all the borders of each rectangle as well.

We can say that E is the most left coordinate of rectangle(E, F, G, H)
and C is the most right coordinate of rectangle(A, B, C, D).

If `E >= C`, i.e. the most left coordinate of rectangle(E, F, G, H)
is on the right side of rectangle(A, B, C, D),
then we can be sure that there is no overlap between the two rectangles.

This condition is sufficient but not necessary to conclude the non-overlapping property of two rectangles.

Following the same idea, we could derive the other 3 conditions, as they are symmetrical.

• Or sort the points along the x-axis and y-axis.

int overlappingArea(int A, int B, int C, int D, int E, int F, int G, int H) {

``````    if(E>=C || F>=D || A>G || B>H)
return 0;

int x_axis[4] = {A,C,E,G};
int y_axis[4] = {B,D,F,H};
sort(x_axis,x_axis+4);
sort(y_axis,y_axis+4);

return (x_axis[2] - x_axis[1]) * (y_axis[2] - y_axis[1]);
``````

}

• For the sake of completeness, the 'if' condition should have A>=G and B>=H, since there would be no overlap if they are equal. It would still be handled later since difference will be 0, so product will be zero. But better to handle it before and say that there is no overlap at all.

• ``````
/**
Calculate the area of intersection of two given rectilinear rectangles.

- Author:
Cong Liu <congliu0704 at gmail dot com>

- Returns:
The area of intersection of two given rectilinear rectangles.

- Parameters:
- K: The x coordinate of the lower left point of rectangle A
- L: The y coordinate of the lower left point of rectangle A
- M: The x coordinate of the upper right point of rectangle A
- N: The y coordinate of the upper right point of rectangle A
- P: The x coordinate of the lower left point of rectangle B
- Q: The y coordinate of the lower left point of rectangle B
- R: The x coordinate of the upper right point of rectangle B
- S: The y coordinate of the upper right point of rectangle B

- Assumptions:
All the eight given coordinates (K, L, M, N, P, Q, R and S) are integers
within the range [-2147483648...2147483647], that is, Int32-compatible.
K < M, L < N, P < R, Q < S

- Analysis:
The area of intersected is dyIntersected * dxIntersected.

To find out dyIntersected, consider how y coordinates of two rectangles relate
to each other, by moving rectangle A from above rectangle B down.

Case 1: when N >  L >= S >  Q, dyIntersected = 0
Case 2: when N >= S >  L >= Q, dyIntersected = S - L
Case 3: when S >  N >  L >= Q, dyIntersected = N - L
Case 4: when S >= N >= Q >  L, dyIntersected = N - Q
Case 5: when N >  S >  Q >  L, dyIntersected = S - Q
Cases 2 and 3 can be merged as Case B:
when           L >= Q, dyIntersected = min(N, S) - L
Cases 4 and 5 can be merged as Case C:
when           Q >  L, dyIntersected = min(N, S) - Q
Cases B and C can be merged as Case D:
when      S >  L     , dyIntersected = min(N, S) - max(L, Q)

Likewise, x coordinates of two rectangles relate similarly to each other:
Case 1: when R >  P >= M >  K, dxIntersected = 0
Case 2: when      M >  P     , dxIntersected = min(R, M) - max(P, K)

- Submission Date:
Sat 20 Jan 2018 CST at 23:28 pm

- Performance:
https://leetcode.com/problems/rectangle-area/description/
Status: Accepted
3081 / 3081 test cases passed.
Runtime: 78 ms
*/
class Solution {
public static func computeArea(_ K: Int, _ L: Int, _ M: Int, _ N: Int, _ P: Int, _ Q: Int, _ R: Int, _ S: Int) -> Int {
let areaA : Int = Int((M - K) * (N - L))
let areaB : Int = Int((R - P) * (S - Q))
var xIntersection : Int = 0
var yIntersection : Int = 0
var areaIntersection : Int = 0

if ((min(M, R) - max(K, P)) > 0) {
xIntersection = Int(min(M, R) - max(K, P))
}

if ((min(N, S) - max(L, Q)) > 0) {
yIntersection = Int(min(N, S) - max(L, Q))
}

if ((xIntersection == 0) || (yIntersection == 0)) {
areaIntersection = 0
} else {
areaIntersection = Int(xIntersection * yIntersection)
}

return (areaA + areaB - areaIntersection)
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.