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.
enumerate
:-/ \$\endgroup\$namedtuple()
might be a bright idea forRectangle
. \$\endgroup\$IntervalTree
changed when I went form[lo, hi]
to[lo:hi]
... Didn't like it, has overhead -> ditched.) \$\endgroup\$