Krdytkyu

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?

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

A 2-d R-tree implementation is here:
https://github.com/bzliu94/algorithms/blob/master/r-tree/rtree.py

The important method is doOverlapQuery().

(It's a little disorganized and kludgey.)