2
\$\begingroup\$

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.

asked Nov 25, 2016 at 0:58
\$\endgroup\$
4
  • \$\begingroup\$ Found enumerate :-/ \$\endgroup\$ Commented Nov 25, 2016 at 1:11
  • 1
    \$\begingroup\$ Come to think of it, namedtuple()might be a bright idea for Rectangle. \$\endgroup\$ Commented Nov 25, 2016 at 1:28
  • \$\begingroup\$ For all the traffic this already generated, I took the liberty to incorporate "self-suggested" simplifications. \$\endgroup\$ Commented Nov 26, 2016 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\$ Commented Dec 6, 2016 at 12:15

0

Know someone who can answer? Share a link to this question via email, Twitter, or Facebook.

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.