找到N个矩形重叠的有效方法

Question

我试图找到一个有效的解决方案,找到n个矩形的重叠,其中矩形存储在两个单独的列表中.我们正在寻找listA与矩形重叠的所有矩形listB(反之亦然).将第一个列表中的一个元素与第二个列表进行比较可能需要花费大量时间.我正在寻找一个有效的解决方案.

我有两个矩形列表

rect = Rectangle(10, 12, 56, 15)
rect2 = Rectangle(0, 0,1, 15)
rect3 = Rectangle (10,  12, 56, 15)

listA = [rect, rect2]
listB = [rect3]

这是从类创建的:

import numpy as np
import itertools as it

class  Rectangle(object):
    def __init__(self, left, right, bottom, top):
        self.left = left
        self.bottom = right
        self.right = bottom
        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

我需要比较矩形listA到listB代码就像这样效率非常低 - 逐个比较

for a in it.combinations(listB):
    for b in it.combinations(listA):
        if a.overlap(b):

有没有更有效的方法来处理这个问题？

Answer 1

首先:与计算几何中的许多问题一样,指定生长顺序分析的参数需要注意:调用列表m和n的长度,仅在那些参数中最坏的情况是Ω(m×n),因为所有区域都可能重叠(在这方面,问题的算法是渐近最优的).通常包括输出的大小:t = f(m,n,o)(输出敏感算法).
平凡地,对于所提出的问题,f∈Ω(m + n + o).

线扫描是一种通过一维减少几何问题的范例 - 从原始形式,从2D到1D,从平面到线.

想象一下飞机上的所有矩形,列表的不同颜色.
 现在在这个平面上扫描一条线 - 从左到右,传统上,并且无限地向右进一步"对于低y坐标"(处理坐标增加x次序,增加y次序,等于  x).
 对于所有这种扫描(或扫描),每种颜色保持一组代表当前x坐标处所有矩形的"y间隔",从空开始.(在支持插入,删除和枚举与查询间隔重叠的所有间隔的数据结构中:请参见下文.)
 遇到矩形的左侧,将该段添加到数据结构中以获取其颜色.报告任何其他颜色的重叠间隔/矩形.
 在右侧,删除该段.
 根据"重叠"的定义,在右侧之前处理左侧 - 或者反之亦然.

有许多数据结构支持插入和删除间隔,并查找与查询间隔重叠的所有间隔.目前,我认为增强搜索树可能最容易理解,实现,测试,分析......
使用这个,枚举所有o交叉的轴对齐矩形对(a,b),listA并且listB应该可以在O((m + n)中)log(m + n)+ o)时间和O(m + n)空间.对于相当大的问题实例,避免需要多于线性空间的数据结构((原始)段树,对于与间隔重叠有关的一个示例).

算法设计的另一个范例是Divide&Conquer:有计算几何问题,选择一个维度可以将问题分成独立的部分,一个坐标使得"坐标下方"和"上方坐标"的子问题接近预期的运行时间.很可能,需要解决另一个(和不同的)子问题"包括坐标".当a)解决子问题的运行时间是"超对数线性"时,这往往是有益的,并且b)有一种廉价(线性)方法从子问题的解决方案构建整体解决方案.
这有助于同时解决问题,并且可以与任何其他方法一起用于子问题,包括线扫描.

有很多方法可以调整每种方法,首先忽略不可能对输出做出贡献的输入项.要"公平地"比较类似增长顺序的算法的实现,不要追求公平的"调整水平":尝试投入大量时间进行调整.

Answer 2

一些潜在的小的效率改进.首先,修复你的overlap()功能,它可能不需要进行计算:

def overlap(r1, r2):

    if r1.left > r2.right or r1.right < r2.left:
        return False

    if r1.top < r2.bottom or r1.bottom > r2.top:
        return False

    return True

其次,计算其中一个列表的控制矩形,并使用它来筛选另一个列表 - 不需要对所有与其相关的矩形进行测试:

def containing_rectangle(rectangles):
    return Rectangle(min(rectangles, key=lambda r: r.left).left,
        max(rectangles, key=lambda r: r.right).right,
        min(rectangles, key=lambda r: r.bottom).bottom,
        max(rectangles, key=lambda r: r.top).top
    )

c = containing_rectangle(listA)

for b in listB:
    if b.overlap(c):
        for a in listA:
            if b.overlap(a):

在我使用数百个随机矩形的测试中,这避免了对单个数字百分比(例如2%或3%)的顺序进行比较,并且偶尔会增加比较次数.但是,据推测,您的数据并非随机,并且可能会通过此类筛查获得更好的效果.

根据数据的性质,您可以将其分解为容器矩形检查,以检查50K中的每批10K矩形,或者切片可以提供最高效率.在将矩形分配给容器批次之前,可能会预先确定矩形(例如,通过它们的中心).

我们可以拆分并使用容器矩形批处理两个列表:

listAA = [listA[x:x + 10] for x in range(0, len(listA), 10)]

for i, arrays in enumerate(listAA):
    listAA[i] = [containing_rectangle(arrays)] + arrays

listBB = [listB[x:x + 10] for x in range(0, len(listB), 10)]

for i, arrays in enumerate(listBB):
    listBB[i] = [containing_rectangle(arrays)] + arrays

for bb in listBB:
    for aa in listAA:
        if bb[0].overlap(aa[0]):
            for b in bb[1:]:
                if b.overlap(aa[0]):
                    for a in aa[1:]:
                        if b.overlap(a):

使用我的随机数据,这减少了15%到20%的比较,甚至计算容器矩形比较.上面的矩形批处理是任意的,你可能会做得更好.