如何高效检测列表中的多个矩形是否存在互相重叠的情况？

前置小优化：减少重复比对 #

你当前的双层循环存在重复比对问题：A矩形和B矩形比对一次后，遍历到B时又会和A再比对一次，仅需修改循环范围即可直接减少一半计算量：

# 原循环的优化版，仅比对两两组合一次
for i in range(len(boxes)):
    thisBox = boxes[i]
    multiplesFound = 0
    for j in range(i+1, len(boxes)):
        otherBox = boxes[j]
        if thisBox.Overlaps(otherBox):
            print(f"{thisBox} overlaps with {otherBox}")
            multiplesFound += 1
    if multiplesFound >= 1:
        pass # highlight overlapping objects

1 修复重叠判断逻辑缺陷 #

你当前的Overlaps方法仅判断对方矩形的四个顶点是否落在当前矩形内部，存在严重漏判：比如一个矩形完全覆盖另一个、两个矩形十字交叉但顶点都不在对方内部的场景，都会错误返回不重叠结果。
针对轴对齐矩形（你当前的实现以及AutoCAD中未旋转的矩形都属于这类），可以用分离轴定理的简化版实现无漏判的重叠判断，逻辑更简单、性能更高：

# 替换原有Overlaps方法即可
def Overlaps(self, box):
    # X轴投影分离则不重叠
    if self.UpperRight.x < box.LowerLeft.x or self.LowerLeft.x > box.UpperRight.x:
        return False
    # Y轴投影分离则不重叠
    if self.UpperRight.y < box.LowerLeft.y or self.LowerLeft.y > box.UpperRight.y:
        return False
    # 两个轴投影都重叠则矩形重叠
    return True

2 大幅降低时间复杂度的通用算法：排序扫掠线法 #

不需要依赖任何第三方库，可在任意编程语言实现，时间复杂度可以从原来的O(n²)降低到O(n log n)，矩形数量越多性能提升越明显：

实现逻辑 #

• 为每个矩形生成两个事件：左边界事件（值为矩形左x坐标，标记为添加事件，关联矩形对象）、右边界事件（值为矩形右x坐标，标记为移除事件，关联矩形对象）
• 将所有事件按x坐标从小到大排序
• 初始化一个空的活跃矩形集合，用于存储x轴投影和当前扫掠位置重叠的矩形
• 按顺序遍历所有事件：
  • 遇到添加事件时，将当前关联的矩形和活跃集合内的所有矩形逐一做重叠判断，记录重叠结果
  • 判断完成后将当前矩形加入活跃集合
  • 遇到移除事件时，将对应矩形从活跃集合中移除

该方案的核心是仅对x轴投影已经重叠的矩形做判断，避免了大量无意义的比对，300个矩形的场景下通常可减少90%以上的比对次数。如果要进一步提升性能，还可以将活跃集合按Y轴坐标排序，判断时仅比对Y轴投影重叠的矩形即可。

AutoLISP适配提示 #

上述所有逻辑都可以直接在AutoLISP中实现，不需要额外依赖：

• 事件排序直接用AutoLISP自带的sort函数按x坐标排序即可
• 活跃集合用普通列表存储，增删操作直接对列表处理
• 重叠判断的逻辑直接对应翻译成AutoLISP的条件表达式即可

内容的提问来源于stack exchange，提问作者johnfree