Triggered by Finding overlaps between two lists of axis-aligned rectangles, I tried to code "rectilinear" intersection using line sweep - in python.
I'm not keen on discussing (2D) line sweep in general here (which is why this isn't tagged algorithm).
The code looks small enough to stay a single module.
I didn't take the time to digest PEP 8 & Co.
""" intersection/overlap between iso-oriented(axis-aligned) rectangles from separate collections relies on left < right with every rectangle """ from collections import namedtuple from intervaltree import IntervalTree#, Interval from heapq import heapify, heappop, heapreplace Rectangle = namedtuple('Rectangle', 'xLow yLow, xHigh yHigh') Event = namedtuple('LineSweepEvent', 'x y, r, category') # from karu's # "Finding overlaps between two lists of axis-aligned rectangles" # (https://codereview.stackexchange.com/q/147177/93149) rect = Rectangle(10, 12, 56, 15) rect2 = Rectangle( 0, 0, 1, 15) rect3 = Rectangle(10, 12, 56, 15) listA = (rect, rect2, Rectangle(1, 5, 16, 17)) listB = (rect3, Rectangle(0, 1, 2, 13)) # event queue processing relies on indexing the next three alike lists = (listA, listB) labels = ('listA', "listB") intervals = tuple(IntervalTree() for l in lists) nCategories = len(lists) # find overlaps by line sweep: # "put left edges in event queue" events = [Event(r.xLow, r.yLow, r, category) for category, items in enumerate(lists) for r in items] heapify(events) # process event queue while (events): e = events c = e.category # print(e) if e.x == e.r.xLow: # left edge intervals[c].addi(e.y, e.r.yHigh, e.r) # e.x = e.r.xHigh # replace left edge event by right heapreplace(events, e._replace(x=e.r.xHigh)) headerShown = False for o in range(nCategories): if o != c: found = intervals[o].search(e.y, e.r.yHigh) if found: if not headerShown: print(labels[c], e.r, " overlaps") headerShown = True print("\t" + labels[o], [iv.data for iv in found]) else: # right edge intervals[c].removei(e.y, e.r.yHigh, e.r) heappop(events)
(I had no luck using "the -interface" to
I have an idea what made me refrain from creating a class to (temporarily) keep a rectangle list, its label and its intervals "on the sweep-line" together - would a "named tuple" be/look more lightweight?
Is ("avoidably") creating a new object using
_replace() too costly?
Suggestions (/edits) to make this code more readable or pythonesque (pythonic? "less irritating to those well versed in python") welcome.