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]

# 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)

(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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.