I wrote this code that checks if a list of boxes overlap with each other. This seems very insufficient though because I have to loop over each box multiplied by all of the other boxes. It there a better way to do this?
For simplicity sake and broader audience I wrote this in Python but the final implementation will be in AutoLISP because I'm using this inside of AutoCAD. For that reason I'm looking for a more general solution/algorithm that will work in any language and doesn't rely on any libraries.
from random import *
from collections import namedtuple
Point = namedtuple("Point", "x y")
class Box:
def __init__(self):
center = Point(x = randint(0, 100), y = randint(0, 100))
self.UpperLeft = Point(center.x - 2, center.y + 2)
self.UpperRight = Point(center.x + 2, center.y + 2)
self.LowerRight = Point(center.x + 2, center.y - 2)
self.LowerLeft = Point(center.x - 2, center.y - 2)
def __str__(self):
return f"Box LL: {self.LowerLeft.x},{self.LowerLeft.y} and UR: {self.UpperRight.x},{self.UpperRight.y}"
def Overlaps(self, box):
if self.LowerLeft.x < box.UpperLeft.x < self.UpperRight.x and \
self.LowerLeft.y < box.UpperLeft.y < self.UpperRight.y :
return True
if self.LowerLeft.x < box.UpperRight.x < self.UpperRight.x and \
self.LowerLeft.y < box.UpperRight.y < self.UpperRight.y :
return True
if self.LowerLeft.x < box.LowerRight.x < self.UpperRight.x and \
self.LowerLeft.y < box.LowerRight.y < self.UpperRight.y :
return True
if self.LowerLeft.x < box.LowerLeft.x < self.UpperRight.x and \
self.LowerLeft.y < box.LowerLeft.y < self.UpperRight.y :
return True
return False
boxes = [Box() for _ in range(300)]
for thisBox in boxes:
multiplesFound = 0
for otherBox in boxes:
if thisBox is otherBox:
continue
elif thisBox.Overlaps(otherBox):
print(f"{thisBox} overlaps with {otherBox}")
multiplesFound += 1
if multiplesFound >= 1:
pass # highlight overlapping objects
A first level of optimization, of course, is to compare each box to only the following ones in the list. Ths is still O(n^2), but the actual number of comparisons is about n**2 / 2so it is a 2x speed-up.
Next step, you could split your plane in a few sub-areas, assign each box to its area and compare only the boxes in the same sub-area. The issue is, a box may have it lower left coordinate in a sub-area, and its upper right one in another sub-area, horizontally, vertically, or even in both directions. So we need to put that box in all the sub-areas it pertains to. But even with this further check, the speed-up is dramatic.
In the following, check0() is your original code, slightly modified in order to be able to use timeit(), check1() is the n**2 / 2 version, check2() is the optimized version. partition(splits) is the helper function that creates the sub-area buckets. For instance partition(4) will create 4 x 4 sub-areas.
def partition(splits):
for thisBox in boxes:
threshold = 100 // splits
llxPart = abs(thisBox.LowerLeft.x) // threshold
llyPart = abs(thisBox.LowerLeft.y) // threshold
partitions[(llxPart, llyPart)].append(thisBox)
urxPart = abs(thisBox.UpperRight.x) // threshold
uryPart = abs(thisBox.UpperRight.y) // threshold
if urxPart > llxPart:
partitions[(urxPart, llyPart)].append(thisBox)
if uryPart > llyPart:
partitions[(llxPart, uryPart)].append(thisBox)
if urxPart > llxPart:
partitions[(urxPart, uryPart)].append(thisBox)
def check0():
totalMultiples = 0
for thisBox in boxes:
multiplesFound = 0
for otherBox in boxes:
if thisBox is otherBox:
continue
elif thisBox.Overlaps(otherBox):
##print(f"{thisBox} overlaps with {otherBox}")
multiplesFound += 1
if multiplesFound >= 1:
pass # highlight overlapping objects
totalMultiples += multiplesFound
return totalMultiples
def check1():
totalMultiples = 0
for i,thisBox in enumerate(boxes):
multiplesFound = 0
for otherBox in boxes[i+1:]:
if thisBox.Overlaps(otherBox):
##print(f"{thisBox} overlaps with {otherBox}")
multiplesFound += 1
if multiplesFound >= 1:
pass # highlight overlapping objects
totalMultiples += multiplesFound
return totalMultiples
def check2():
totalMultiples = 0
for part in partitions.values():
for i,thisBox in enumerate(part):
multiplesFound = 0
for otherBox in part[i+1:]:
if thisBox.Overlaps(otherBox):
##print(f"{thisBox} overlaps with {otherBox}")
multiplesFound += 1
if multiplesFound >= 1:
pass # highlight overlapping objects
totalMultiples += multiplesFound
return totalMultiples
from timeit import timeit
partition(4)
timeit("check0()", globals=globals(), number=1000)
6.7651189999999986
timeit("check1()", globals=globals(), number=1000)
3.5294421000000007
timeit("check2()", globals=globals(), number=1000)
0.45386700000000246