# Find overlaps between lists of axis-aligned rectangles using line sweep

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[0]
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 IntervalTree.)
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.

• Found enumerate :-/ – greybeard Nov 25 '16 at 1:11
• Come to think of it, namedtuple()might be a bright idea for Rectangle. – greybeard Nov 25 '16 at 1:28
• For all the traffic this already generated, I took the liberty to incorporate "self-suggested" simplifications. – greybeard Nov 26 '16 at 11:38
• (My luck using "the []-interface" to IntervalTree changed when I went form [lo, hi] to [lo:hi]… Didn't like it, has overhead -> ditched.) – greybeard Dec 6 '16 at 12:15