Source code for tryalgo.union_rectangles

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Union of rectangles
jill-jênn vie et christoph dürr - 2014-2019
"""
# pylint: disable=too-many-arguments, too-many-locals


# snip{ union_intervals
from collections import Counter
# snip}


# weighted variant of tryalgo.range_minimum_query.LazySegmentTree
# snip{ cover-query
[docs]class CoverQuery: """Segment tree to maintain a set of integer intervals and permitting to query the size of their union. """ def __init__(self, L): """creates a structure, where all possible intervals will be included in [0, L - 1]. """ assert L != [] # L is assumed sorted self.N = 1 while self.N < len(L): self.N *= 2 self.c = [0] * (2 * self.N) # --- covered self.s = [0] * (2 * self.N) # --- score self.w = [0] * (2 * self.N) # --- length for i, _ in enumerate(L): self.w[self.N + i] = L[i] for p in range(self.N - 1, 0, -1): self.w[p] = self.w[2 * p] + self.w[2 * p + 1]
[docs] def cover(self): """:returns: the size of the union of the stored intervals """ return self.s[1]
[docs] def change(self, i, k, offset): """when offset = +1, adds an interval [i, k], when offset = -1, removes it :complexity: O(log L) """ self._change(1, 0, self.N, i, k, offset)
def _change(self, p, start, span, i, k, offset): if start + span <= i or k <= start: # --- disjoint return if i <= start and start + span <= k: # --- included self.c[p] += offset else: self._change(2 * p, start, span // 2, i, k, offset) self._change(2 * p + 1, start + span // 2, span // 2, i, k, offset) if self.c[p] == 0: if p >= self.N: # --- leaf self.s[p] = 0 else: self.s[p] = self.s[2 * p] + self.s[2 * p + 1] else: self.s[p] = self.w[p]
# snip} # snip{ union_intervals OPENING = +1 # constants for events CLOSING = -1 # -1 has higher priority
[docs]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 multiset of intervals. an interval is a pair of values. :returns: size of the union of those intervals :complexity: :math:`O(n \\log 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
# snip} # snip{ union_rectangles
[docs]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
# snip} # snip{ union_rectangles_fast
[docs]def union_rectangles_fast(R): """Area of union of rectangles :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)` """ X = set() # set of all x coordinates in the input events = [] # events for the sweep line for x1, y1, x2, y2 in R: assert x1 <= x2 and y1 <= y2 X.add(x1) X.add(x2) events.append((y1, OPENING, x1, x2)) events.append((y2, CLOSING, x1, x2)) # array of x coordinates in left to right order i_to_x = list(sorted(X)) # inverse dictionary maps x coordinate to its rank x_to_i = {xi: i for i, xi in enumerate(i_to_x)} # nb_current_rectangles[i] = number of rectangles intersected # by the sweepline in interval [i_to_x[i], i_to_x[i + 1]] nb_current_rectangles = [0] * (len(i_to_x) - 1) area = 0 length_union_intervals = 0 previous_y = 0 # arbitrary initial value, # because length is 0 at first iteration for y, offset, x1, x2 in sorted(events): area += (y - previous_y) * length_union_intervals i1 = x_to_i[x1] i2 = x_to_i[x2] # update nb_current_rectangles for j in range(i1, i2): length_interval = i_to_x[j + 1] - i_to_x[j] if nb_current_rectangles[j] == 0: length_union_intervals += length_interval nb_current_rectangles[j] += offset if nb_current_rectangles[j] == 0: length_union_intervals -= length_interval previous_y = y return area
# snip} # snip{ union_rectangles_fastest
[docs]def union_rectangles_fastest(R): """Area of union of rectangles :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 \\log n)` """ if R == []: # segment tree would fail on an empty list return 0 X = set() # set of all x coordinates in the input events = [] # events for the sweep line for Rj in R: (x1, y1, x2, y2) = Rj assert x1 <= x2 and y1 <= y2 X.add(x1) X.add(x2) events.append((y1, OPENING, x1, x2)) events.append((y2, CLOSING, x1, x2)) i_to_x = list(sorted(X)) # inverse dictionary x_to_i = {i_to_x[i]: i for i in range(len(i_to_x))} L = [i_to_x[i + 1] - i_to_x[i] for i in range(len(i_to_x) - 1)] C = CoverQuery(L) area = 0 previous_y = 0 # arbitrary initial value, # because C.cover() is 0 at first iteration for y, offset, x1, x2 in sorted(events): area += (y - previous_y) * C.cover() i1 = x_to_i[x1] i2 = x_to_i[x2] C.change(i1, i2, offset) previous_y = y return area
# snip} # snip{ union_rectangles_naive
[docs]def rectangles_contains_point(R, x, y): """Decides if at least one of the given rectangles contains a given point either strictly or on its left or top border """ for x1, y1, x2, y2 in R: if x1 <= x < x2 and y1 <= y < y2: return True return False
[docs]def union_rectangles_naive(R): """Area of union of rectangles :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^3)` """ X = set() # set of all x coordinates in the input Y = set() # same for y for x1, y1, x2, y2 in R: assert x1 <= x2 and y1 <= y2 X.add(x1) X.add(x2) Y.add(y1) Y.add(y2) j_to_x = list(sorted(X)) i_to_y = list(sorted(Y)) # X and Y partition space into a grid area = 0 for j in range(len(j_to_x) - 1): # loop over columns in grid x1 = j_to_x[j] x2 = j_to_x[j + 1] for i in range(len(i_to_y) - 1): # loop over rows y1 = i_to_y[i] # (x1,...,y2) is the grid cell y2 = i_to_y[i + 1] if rectangles_contains_point(R, x1, y1): area += (y2 - y1) * (x2 - x1) # cell is covered return area
# snip}