如何有效地检查框列表是否相互重叠？

Question

我编写了这段代码来检查框列表是否相互重叠。这似乎非常不够，因为我必须遍历每个框乘以所有其他框。有更好的方法吗？

为了简单起见和更广泛的读者，我在 Python 中写了这篇文章，但最终实施将在 AutoLISP 中进行，因为我在 AutoCAD 中使用它。出于这个原因，我正在寻找一个更通用的 solution/algorithm，它可以在任何语言中工作并且不依赖任何库。

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

当然，第一级优化是将每个框与列表中的以下框进行比较。这仍然是 O(n^2)，但实际比较次数约为 n**2 / 2，因此它是 2 倍的加速。

下一步，你可以将你的飞机分成几个子区域，将每个盒子分配给它的区域，并只比较同一子区域中的盒子。问题是，一个盒子可能在一个子区域中有它的左下角坐标，在另一个子区域中有它的右上角坐标，水平、垂直，甚至两个方向。所以我们需要将该框放在它所属的所有子区域中。但即使进行了进一步检查，速度提升也是惊人的。

下面，check0()是你的原代码，为了能用timeit()稍作修改，check1()是n**2 / 2版本，check2() 是优化版本。 partition(splits) 是创建子区域桶的辅助函数。例如 partition(4) 将创建 4 x 4 子区域。

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

如何有效地检查框列表是否相互重叠？

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

lisp

python

geometry

autocad

autolisp