How to efficiently check if a list of boxes overlap with each other?

Question

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

Answer 1

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