6
\$\begingroup\$

I am trying to find an efficient solution for finding overlapping of n rectangles where rectangles are stored in two separate lists. We are looking for all rectangles in listA that overlap with rectangles in listB (and vice versa). Comparing one element from the first list to second list could take immensely large amount of time. I am looking for an efficient solution.

I have two lists of axis-aligned rectangles:

rect = Rectangle(10, 112, 56, 15)
rect2 = Rectangle(0, 0, 1, 15)
rect3 = Rectangle (10, 12, 56, 15)

listA = [rect, rect2]
listB= [rect3]

which is created from the class:

import numpy as np
import itertools as it


class  Rectangle(object):
    def __init__(self, left, right, bottom, top):
        self. left = left
        self.bottom = bottom
        self.right = right
        self.top = top

    def overlap(r1, r2):
        hoverlaps = True
        voverlaps = True
        if r1.left > r2.right or r1.right < r2.left:
            hoverlaps = False
        if r1.top < r2.bottom or r1.bottom > r2.top:
            voverlaps = False
        return hoverlaps and voverlaps

I need to compare rectangle in listA to listB the code goes like this which is highly inefficient - comparing one by one

for a in it.combinations(listB) :
    for b in it.combinations(listA):
        if a.overlap(b):

Any better efficient method to deal with the problem?

\$\endgroup\$
8
  • 1
    \$\begingroup\$ "overlapping of n rectangles where rectangles are stored in two separate lists." What does this mean? I don't understand what you are saying. Are you saying that we have 2 lists of rectangles listA = [...]; listB = [...];, and we are looking for all rectangles in listA that overlap with rectangles in listB (and vice versa)? Or that we are looking for the region that is the overlap of all rectangles? Or something else? \$\endgroup\$
    – Justin
    Nov 16, 2016 at 8:51
  • \$\begingroup\$ for a,b in it.combinations(listA,2):: I see only one list used here, what is listB good for? Also can you provide a bit more context around this for loop (what do you do when they overlap, how do you initialize stuff if any)? \$\endgroup\$ Nov 16, 2016 at 9:16
  • 1
    \$\begingroup\$ I understand the requirements you have, it's just that the code does not match, and I am trying to understand why. \$\endgroup\$ Nov 16, 2016 at 9:32
  • \$\begingroup\$ Have you been introduced to line sweep / sweep line algorithms? (Please describe the meaning of the parameters defining a Rectangle: radious, in particular.) \$\endgroup\$
    – greybeard
    Nov 16, 2016 at 10:45
  • \$\begingroup\$ @greybeard No. What is it ? Where I can find the implementation to understand it? \$\endgroup\$
    – karu
    Nov 16, 2016 at 10:47

1 Answer 1

4
\$\begingroup\$

Dec. 10, 2018

The simple answer is to use a 2-d segment tree.


Given that we have low value for dimension (i.e. two), an appropriate approach would be to use a 2-d segment tree. We use what is known as stabbing query or intersection query. Let list one be the list that is smaller. Store all rectangles from list one in such a tree. Query using rectangles from list two. Time to construct and query are \$O(n_1 \cdot \log^2(n_1))\$ and \$O(\log^2(n_1) \cdot k)\$, respectively, s.t. \$k\$ is number of matches to report. If we use fractional cascading and interval tree, times become \$O(n_1 \cdot \log(n_1))\$ and \$O(\log(n_1) \cdot k)\$, respectively. Assuming these better times, time for all queries is \$O(\textrm{max}(n_2, k_\textrm{overall}) \cdot \log(n_1))\$. Overall time becomes \$O((\textrm{max}(n_2, k_\textrm{overall}) + n_1) \cdot \log(n_1))\$. Given that \$k_\textrm{overall}\$ is in \$O(n_1 \cdot n_2)\$, time could be loosely \$O((n_1 \cdot n_2) \cdot \log(n_1))\$.

If rectangles are not axis-aligned, one might wish to have bounding boxes and then use a tree. In principle we then could use a segment tree again, but a natural alternative (though we usually do not have good guaranteed theoretical running time for it unless we use "look-ahead") could be an R-tree.

\$\endgroup\$
3
  • \$\begingroup\$ (This answer was given when it wasn't clear that the rectangles were aligned.) \$\endgroup\$
    – greybeard
    Nov 18, 2016 at 11:22
  • \$\begingroup\$ @bziliu If you could provide the implement the code, I would accept the answer \$\endgroup\$
    – karu
    Nov 19, 2016 at 22:26
  • \$\begingroup\$ (Just noticed your answer wasn't eligible to be awarded (half of) the bounty automatically. 100 of karu's reputation points gone - nowhere.) \$\endgroup\$
    – greybeard
    Nov 26, 2016 at 12:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.