1. The Problem — Plain English
Imagine dropping several cardboard boxes on the floor. Some overlap, some do not. How much floor is actually covered?
That’s the Rectangle Union problem. Given N rectangles (some overlapping), find the total area of their union — counting overlapping regions only once.
| The naive answer — just add up all rectangle areas — overcounts overlap regions. We need something smarter. |
Example: Three rectangles with areas 100, 80, and 60 have a naive sum of 240. But if two of them share a 30-unit overlap, the real union area is only 210.
2. How the Sweep Line Solves It
Think of pulling a thin vertical sheet of glass slowly from the left side of your floor to the right. At any position x, the glass cuts through some number of rectangles. Those rectangles leave segments of the glass covered.
If we know the total covered length on the glass at position x, then a tiny step dx contributes exactly:
dArea = covered_height(x) × dx
Sum that across all steps and you have the union area.
In practice we don’t use infinitely small steps. Instead we notice that covered_height(x) only changes at rectangle left and right edges. So we jump the sweep line from edge to edge — these are our events.
| Between two consecutive events the covered height is constant. So: area of slab = width × covered_height. Sum all slabs = total union area. |
3. Algorithm — Step by Step
| 1 | Build the event queue For each rectangle collect its left edge (ENTER event) and right edge (EXIT event). Sort all events by x-coordinate. Ties: ENTER before EXIT. |
| 2 | Sweep left to right Process each event. Before updating the active set, measure the current slab: width = (current_x − previous_x), height = union of all active y-intervals. Add slab area to total. |
| 3 | Update active set On ENTER add the rectangle’s y-interval. On EXIT remove it. |
| 4 | Compute union height To get the covered height at any moment, merge the y-intervals of all active rectangles (sort by y1, greedily merge overlaps). Sum the merged lengths. |
| 5 | Done After the last event the total area is complete. Time complexity: O(N² ) for the basic version (y-interval merge at each event), O(N log N) with a segment tree. |
4. Worked Example — 4 Rectangles
Each rectangle is defined as (x1, y1, x2, y2). All coordinates are on a 100×100 grid.
| Rect | x1 | y1 | x2 | y2 | Description |
| R1 | 10 | 20 | 50 | 70 | Tall left rectangle |
| R2 | 30 | 40 | 80 | 90 | Wide middle, overlaps R1 |
| R3 | 60 | 10 | 100 | 55 | Top-right rectangle |
| R4 | 20 | 60 | 70 | 100 | Bottom-center rectangle |
4.1 Events (sorted by x)
| x | Type | Rect | Active y-intervals after |
| 10 | ENTER | R1 | [20–70] |
| 20 | ENTER | R2 | [20–70], [40–90] → merged [20–90] |
| 30 | ENTER | R3 | [20–90], [10–55] → merged [10–90] |
| 50 | EXIT | R1 | [40–90], [10–55] → merged [10–90] |
| 60 | EXIT | R2 | [10–55] |
| 70 | ENTER | R4 | [10–55], [60–100] — two separate intervals |
| 80 | EXIT | R3 | [60–100] |
| 100 | EXIT | R4 | (empty) |
4.2 Slab Area Calculation
Between each pair of consecutive events we compute one slab:
Slab [10→20]: width=10, covered_height=50 (20–70) area = 500 Slab [20→30]: width=10, covered_height=70 (20–90) area = 700 Slab [30→50]: width=20, covered_height=80 (10–90) area = 1600 Slab [50→60]: width=10, covered_height=80 (10–90) area = 800 Slab [60→70]: width=10, covered_height=45 (10–55) area = 450 Slab [70→80]: width=10, covered_height=85 (10–55 + 60–100) = 550 Slab [80→100]:width=20, covered_height=40 (60–100) area = 800 ──────── Total Union = 5400 |
5. Pseudocode
ALGORITHM: RectangleUnionArea(rectangles) BUILD event queue: for each rect R: add (x=R.x1, ENTER, R) add (x=R.x2, EXIT, R) sort events by x (ENTER before EXIT on ties) active ← empty list of y-intervals total_area ← 0 prev_x ← first event x FOR each event E: slab_width ← E.x − prev_x covered_h ← union_length(active) // merge y-intervals total_area += slab_width × covered_h if E.kind == ENTER: active.add(E.rect.y1, E.rect.y2) if E.kind == EXIT: active.remove(E.rect.y1, E.rect.y2) prev_x ← E.x RETURN total_area FUNCTION union_length(intervals): sort intervals by start merge overlapping intervals return sum of merged lengths |
6. Python Implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
# rect_union.py — Rectangle Union Area via Line Sweep from dataclasses import dataclass from typing import List, Tuple @dataclass class Rect: x1: float; y1: float x2: float; y2: float label: str = "" def union_length(intervals: List[Tuple[float, float]]) -> float: """Compute total length covered by a set of 1D intervals.""" if not intervals: return 0.0 intervals = sorted(intervals) # sort by start total = 0.0 cur_start, cur_end = intervals[0] for start, end in intervals[1:]: if start <= cur_end: # overlapping — extend cur_end = max(cur_end, end) else: # gap — flush and reset total += cur_end - cur_start cur_start, cur_end = start, end total += cur_end - cur_start return total def rect_union_area(rects: List[Rect]) -> float: """ Compute the area of the union of rectangles using a line sweep. Time: O(N^2) — merge step is O(N) per event, 2N events. Space: O(N) """ # ── Build events ───────────────────────────────────────── events = [] for r in rects: events.append((r.x1, 0, r)) # 0 = ENTER (before EXIT) events.append((r.x2, 1, r)) # 1 = EXIT events.sort(key=lambda e: (e[0], e[1])) # ── Sweep ──────────────────────────────────────────────── active: List[Tuple[float, float]] = [] # active y-intervals total_area = 0.0 prev_x = events[0][0] for x, kind, rect in events: # Accumulate slab before updating active set slab_w = x - prev_x if slab_w > 0: h = union_length(active) total_area += slab_w * h print(f" Slab [{prev_x}→{x}]: w={slab_w}, h={h:.1f} +{slab_w*h:.1f}") if kind == 0: # ENTER active.append((rect.y1, rect.y2)) print(f" ENTER {rect.label}") else: # EXIT active.remove((rect.y1, rect.y2)) print(f" EXIT {rect.label}") prev_x = x return total_area if __name__ == "__main__": rectangles = [ Rect(10, 20, 50, 70, "R1"), Rect(30, 40, 80, 90, "R2"), Rect(60, 10, 100, 55, "R3"), Rect(20, 60, 70, 100, "R4"), ] print("Rectangle Union — Line Sweep") print("=" * 40) area = rect_union_area(rectangles) print("=" * 40) print(f"Total Union Area: {area}") |
Expected Output
Rectangle Union — Line Sweep ======================================== ENTER R1 Slab [10→20]: w=10, h=50.0 +500.0 ENTER R2 Slab [20→30]: w=10, h=70.0 +700.0 ENTER R3 Slab [30→50]: w=20, h=80.0 +1600.0 EXIT R1 Slab [50→60]: w=10, h=80.0 +800.0 EXIT R2 Slab [60→70]: w=10, h=45.0 +450.0 ENTER R4 Slab [70→80]: w=10, h=55.0 +550.0 EXIT R3 Slab [80→100]: w=20, h=40.0 +800.0 EXIT R4 ======================================== Total Union Area: 5400.0 |
7. Complexity
| Version | Time | Notes |
| Simple (list merge) | O(N²) | Merge N intervals per event × 2N events |
| Segment tree (advanced) | O(N log N) | Each event updates tree in O(log N) |
| Space (both) | O(N) | Event list + active intervals |
| Naïve (bounding grid) | O(A) | A = grid cells; impractical for large coords |
| For competitive programming and most real-world tasks, the O(N²) list-merge version is perfectly fine for N ≤ 1000. Only reach for a segment tree if N exceeds ~10,000. |
I hope this tutorial will create a good foundation for you. If you want tutorials on another topic or you have any queries, please send an mail at contact@spatial-dev.guru.