3

Having list of rectangles parallel to axis in form (minx, miny, maxx, maxy):

rectangles = [ Rectangle(90,40,110,70), Rectangle(10,40,40,70), Rectangle(75,60,95,80), Rectangle(30,20,60,50), Rectangle(100,20,130,50), Rectangle(70,10,85,40) ]

I need to get list of groups of rectangles, where each rectangle intersects with at least one other:

[ (Rectangle(10,40,40,70), Rectangle(30,20,60,50)), (Rectangle(70,10,85,40)), (Rectangle(75,60,95,80), Rectangle(90,40,110,70), Rectangle(100,20,130,50)) ]

The algorithm can't be naive, it needs to be fast.

What I tried:

  1. Find python interval tree implementation - I couldn't find anything good...
  2. I tried this repo: https://github.com/booo/rectangleintersection/blob/master/rectangleIntersection.py, it works with the example above but fails with real world data.
  3. I read through scikit image and Shapely documentation but didn't find algorithms for rectangle intersection.
Improve this question
12
  • what are the four values in each rectangle? definitely not a point in a 2D plane. Commented Jan 7, 2014 at 11:50
  • @PhamTrung: minx, miny, max, maxy Commented Jan 7, 2014 at 11:52
  • So these rectangles are parallel with Ox and Oy axis? Commented Jan 7, 2014 at 11:53
  • @richsilv - 1. Each rectangle intersects with at least one other. 2. By fast I mean faster than O^2 as I can do it comparing each rectangle with another. In ideal case it should have O complexity as good as in theory. Commented Jan 7, 2014 at 11:54
  • "Rectangle" that you use is not standard python. where do you import it from? Guess you are using matplotlib, but that has different parameters for defining Rectangles? Commented Jan 7, 2014 at 11:55

1 Answer 1

Reset to default
4

Intersecting rectangles can be viewed as connected nodes in a graph, and sets of "transitively" intersecting rectangles as Connected Components. To find out which rectangles intersect, we first do a Plane Sweep. To make this reasonably fast we need an Interval Tree. Banyan provides one:

from collections import defaultdict from itertools import chain from banyan import SortedDict, OverlappingIntervalsUpdator def closed_regions(rects): # Sweep Line Algorithm to set up adjacency sets: neighbors = defaultdict(set) status = SortedDict(updator=OverlappingIntervalsUpdator) events = sorted(chain.from_iterable( ((r.left, False, r), (r.right, True, r)) for r in set(rects))) for _, is_right, rect in events: for interval in status.overlap(rect.vertical): neighbors[rect].update(status[interval]) if is_right: status.get(rect.vertical, set()).discard(rect) else: status.setdefault(rect.vertical, set()).add(rect) # Connected Components Algorithm for graphs: seen = set() def component(node, neighbors=neighbors, seen=seen, see=seen.add): todo = set([node]) next_todo = todo.pop while todo: node = next_todo() see(node) todo |= neighbors[node] - seen yield node for node in neighbors: if node not in seen: yield component(node)

rect.vertical BTW is the tuple (rect.top, rect.bottom).

Time complexity is O(n log n + k), where n is the number of rectangles and k the number of actual intersections. So it's pretty close to optimal.

edit: Because there was some confusion, I need to add that the rectangles are expected to have left <= right and top <= bottom. IOW, the origin of the coordinate system they are in is in the upper left corner, not in the lower left corner as is usual in geometry.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Thanks, I will definitely give it a try!
Regarding your link: horizontal should be (self.left, self.right). But the main problem is that my code assumes a computer graphics coordinate system where the origin is in the upper left corner, not the lower left corner like in mathematical geometry. So the parameter list of Rectanle.__init__() should be self, left, top, right, bottom, with left <= right and top <= bottom. I tested it like so and it seems to work.
Also, closed_regions() returns an iterator of iterators, so you should print(list(region)).
BTW, you could also change the definition of vertical to (self.bottom, self.top). Then you could keep the origin of the coordinate system in the lower left corner.
Like this gist.github.com/mnowotka/8729240? It's still return nothing. Can you publish your gist so I can see it?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.