Rectangle Area

medium math geometry

Problem

Given the bottom-left and top-right corners of two axis-aligned rectangles, compute the total covered area (overlap counted once).

InputA=(-3,0,3,4), B=(0,-1,9,2)

Output45

Areas 24 + 27 − overlap 6 = 45.

ax1

ay1

ax2

ay2

bx1

by1

bx2

by2

def compute_area(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2):
    area_a = (ax2 - ax1) * (ay2 - ay1)
    area_b = (bx2 - bx1) * (by2 - by1)
    ow = max(0, min(ax2, bx2) - max(ax1, bx1))
    oh = max(0, min(ay2, by2) - max(ay1, by1))
    return area_a + area_b - ow * oh

function computeArea(ax1, ay1, ax2, ay2, bx1, by1, bx2, by2) {
  const areaA = (ax2 - ax1) * (ay2 - ay1);
  const areaB = (bx2 - bx1) * (by2 - by1);
  const ow = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
  const oh = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
  return areaA + areaB - ow * oh;
}

class Solution {
    public int computeArea(int ax1, int ay1, int ax2, int ay2,
                          int bx1, int by1, int bx2, int by2) {
        int areaA = (ax2 - ax1) * (ay2 - ay1);
        int areaB = (bx2 - bx1) * (by2 - by1);
        int ow = Math.max(0, Math.min(ax2, bx2) - Math.max(ax1, bx1));
        int oh = Math.max(0, Math.min(ay2, by2) - Math.max(ay1, by1));
        return areaA + areaB - ow * oh;
    }
}

int computeArea(int ax1, int ay1, int ax2, int ay2,
                int bx1, int by1, int bx2, int by2) {
    int areaA = (ax2 - ax1) * (ay2 - ay1);
    int areaB = (bx2 - bx1) * (by2 - by1);
    int ow = max(0, min(ax2, bx2) - max(ax1, bx1));
    int oh = max(0, min(ay2, by2) - max(ay1, by1));
    return areaA + areaB - ow * oh;
}

Explanation

If you simply add the two rectangles' areas, the part where they overlap gets counted twice. The fix is the classic inclusion-exclusion idea: add both areas, then subtract the overlap once.

Each rectangle's area is width times height, e.g. area_a = (ax2 - ax1) * (ay2 - ay1).

The overlap is itself a rectangle. Its left edge is the rightmost of the two left edges (max(ax1, bx1)) and its right edge is the leftmost of the two right edges (min(ax2, bx2)); the difference is the overlap width ow. The height oh works the same way vertically. We wrap each in max(0, ...) so that if the rectangles don't actually overlap, the width or height becomes 0 and the overlap area is 0.

The final answer is area_a + area_b - ow * oh.

Example: A=(-3,0,3,4) has area 24, B=(0,-1,9,2) has area 27, and they overlap in a 3-by-2 block of area 6, so the total is 24 + 27 - 6 = 45.

Time: O(1) Space: O(1)