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, 1 12, 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?

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?

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 list of rectangles

rect = Rectangle(10, 1 12, 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 ??

Update: rectangles are "axis-aligned"

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, 1 12, 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?