Skip to content

Instantly share code, notes, and snippets.

Created January 31, 2014 14:29
Show Gist options
  • Save anonymous/8733039 to your computer and use it in GitHub Desktop.
Save anonymous/8733039 to your computer and use it in GitHub Desktop.
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 :)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment