gistfile1.py

from collections import defaultdict
from itertools import chain
from banyan import SortedDict, OverlappingIntervalsUpdator


class Rectangle(object):

    def __init__(self, left, bottom, right, top):
        self.left = left
        self.top = top
        self.right = right
        self.bottom = bottom

    @property
    def vertical(self):
        return (self.bottom, self.top)

    @property
    def horizontal(self):
        return (self.left, self.right)

    def __repr__(self):
        return str((self.left, self.top, self.right, self.bottom))

    __str__ = __repr__

def closed_regions(rects):

    # Sweep Line Algorithm to set up adjacency sets:
    neighbors = defaultdict(set)
    status = SortedDict(updator=OverlappingIntervalsUpdator)
    events = sorted(chain.from_iterable(
            ((r.left, False, r), (r.right, True, r)) for r in set(rects)))
    for _, is_right, rect in events:
        for interval in status.overlap(rect.vertical):
            neighbors[rect].update(status[interval])
        if is_right:
            status.get(rect.vertical, set()).discard(rect)
        else:
            status.setdefault(rect.vertical, set()).add(rect)

    # Connected Components Algorithm for graphs:
    seen = set()
    def component(node, neighbors=neighbors, seen=seen, see=seen.add):
        todo = set([node])
        next_todo = todo.pop
        while todo:
            node = next_todo()
            see(node)
            todo |= neighbors[node] - seen
            yield node
    for node in neighbors:
        if node not in seen:
            yield component(node)

rectangles = [
        Rectangle(90,40,110,70),
        Rectangle(10,40,40,70),
        Rectangle(75,60,95,80),
        Rectangle(30,20,60,50),
        Rectangle(100,20,130,50),
        Rectangle(70,10,85,40)
]

for region in closed_regions(rectangles):
    print(list(region)) #something here :)