How do I get the rectangles which would fill out a space *excluding* some other rectangles?

Question

Title says it all. For example: I want to get all the green rectangles, given the red rectangles. I know the size of the bounding rectangle.

The red rectangles may overlap.

Answer 1

Here's a divide-and-conquer algorithm; the idea is broadly similar to quicksort. I've assumed that the rectangles don't overlap, and that they are all contained within the bounding box, although the boundaries might touch.

• If the bounding box is degenerate (i.e. zero width or zero height), do nothing.
• Otherwise if there are no rectangles, then just yield the bounding box itself.
• Otherwise:
  • Choose a rectangle from the list to be the "pivot".
  • Create new bounding boxes for "above", "left", "right" and "below" the pivot.
  • Build lists of rectangles "above", "left", "right" and "below" the pivot by filtering the list for rectangles which intersect each new bounding box, and clipping them to the bounding box.
  • Recursively subdivide the "above", "left", "right" and "below" bounding boxes by the new lists of rectangles that are within them, respectively.

Each rectangle can be involved in at most 2 of the 4 recursive calls. If the pivot is chosen randomly, and most rectangles don't overlap vertically with most other rectangles, then on average each rectangle is involved in one recursive call. Since the non-recursive work takes linear time, the expected running time in that case is O(n log n) where n is the number of rectangles.

An implementation in Python:

import random
from collections import namedtuple

Rectangle = namedtuple('Rectangle', 'x1 y1 x2 y2')

def intersects(b, r):
    return b.x1 < r.x2 and b.x2 > r.x1 and b.y1 < r.y2 and b.y2 > r.y1

def clip_rect(b, r):
    return Rectangle(
        max(b.x1, r.x1), max(b.y1, r.y1),
        min(b.x2, r.x2), min(b.y2, r.y2)
    )

def clip_rects(b, rects):
    return [clip_rect(b, r) for r in rects if intersects(b, r)]

def split_rectangles(b, rects):
    if b.x1 >= b.x2 or b.y1 >= b.y2:
        pass
    elif not rects:
        yield b
    else:
        # randomize to avoid O(n^2) runtime in typical cases
        # change this if deterministic behaviour is required
        pivot = random.choice(rects)

        above = Rectangle(b.x1,     b.y1,     b.x2,     pivot.y1)
        left  = Rectangle(b.x1,     pivot.y1, pivot.x1, pivot.y2)
        right = Rectangle(pivot.x2, pivot.y1, b.x2,     pivot.y2)
        below = Rectangle(b.x1,     pivot.y2, b.x2,     b.y2)

        yield from split_rectangles(above, clip_rects(above, rects))
        yield from split_rectangles(left,  clip_rects(left,  rects))
        yield from split_rectangles(right, clip_rects(right, rects))
        yield from split_rectangles(below, clip_rects(below, rects))

Example: as you can see, it doesn't use a minimal number of rectangles, since there are two on the right-hand side that could be joined together vertically.

If minimising the number of rectangles is important, you would want to consider different bounding boxes for "above", "left", "right" and "below", and do a second pass over the result to join any rectangles together if they have two sides which are equal as line segments.

Answer 2

The most simple solution is as follows.

Create two lists xlist and ylist, for each red rectangle and each corner of it, insert the x coordinate of that point into xlist and the y coordinate into ylist. Do the same with the bounding box.

Sort and remove duplicates from xlist and ylist.

For each two neighbouring elements x1, x2 in xlist and each two neighbouring elements y1, y2 in ylist (two nested for loops), create a new green rectangle using the coordinates x1, x2, y1, y2 (unless the new green rectangle overlaps with any of the red rectangles).

This will give you more green rectangles than necessary, but you did not give any restrictions, so here it goes ;)

You could easily merge neighbouring green rectangles in one line if you'd like to limit the number of rectangles.