This is a follow up for merging intervals. Instead of merging 1D items, consider the case when each interval comes with a height, and compute the total overlapping area. We would use a sweep line algorithm for this question.
Maintain a horizontal projection for all rectangles. Use 1D union to compute the total union area.
OPENING = 1
CLOSING = -1 # you may choose different value for open and closing case by case
def union_rectangles(R):
"""Area of union of rectangles.
Sweep from top to bottom.
Maintain in a set the horizontal projection of rectangles,
for which the top border has been processed but not yet the bottom.
:param R: list of rectangles defined by (x1, y1, x2, y2)
where (x1, y1) is top left corner and (x2, y2) bottom right corner
:returns: area
:complexity: :math:`O(n^2 \\log n)`
"""
events = []
for x1, y1, x2, y2 in R: # initialize events
assert x1 <= x2 and y1 <= y2
events.append((y1, OPENING, x1, x2))
events.append((y2, CLOSING, x1, x2))
current_intervals = Counter()
area = 0
previous_y = 0 # arbitrary initial value,
# ok, because union_intervals is 0 at first event
for y, offset, x1, x2 in sorted(events): # sweep top down
area += (y - previous_y) * union_intervals(current_intervals)
previous_y = y
current_intervals[x1, x2] += offset
return area
Union Intervals
This question can also be solved using a sweep line algorithm.
Sweep line algorithm explained: A Youtube Video
OPENING = 1
CLOSING = -1 # you may choose different value for open and closing case by case
def union_intervals(intervals):
"""Size of the union of a set of intervals
Sweep from left to right.
Maintain in a counter number of opened intervals
minus number of closed intervals.
:param intervals: Counter, which describes a multi-set of intervals.
an interval is a pair of values.
:returns: size of the union of those intervals
:complexity: :math:`O(nlog n)`
"""
union_size = 0
events = []
for x1, x2 in intervals:
for _ in range(intervals[x1, x2]):
assert x1 <= x2
events.append((x1, OPENING))
events.append((x2, CLOSING))
previous_x = 0 # arbitrary initial value
# ok, because opened == 0 at first event
opened = 0
for x, offset in sorted(events):
if opened > 0:
union_size += x - previous_x
previous_x = x
opened += offset
return union_size
Resources:
- Find faster implementation here: Union Rectangle as fast as O(nlogn)
- Follow up: N Rectangles Intersection Area
- Follow up: Leetcode Skyline
Si Qi Cao 