寻找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):

有更好的高效方法来解决这个问题吗？

- karu

---

试试使用[rect]吧。看起来这正是你想做的。 - Jed Fox

list_of_rectangles = [rect, rect2]。或者 list_of_rectangles = list()，list_of_rectangles.append(rect)，list_of_rectangles.append(rect2) 分别写在三行。 - PM 2Ring

你需要做到以下两点：1）给论坛足够的时间回答问题（我的看法是至少60个小时，8天最好），2）自己添加交叉引用。 - greybeard

每个列表中的矩形可以重叠吗？ - n. m.

请问我的理解是否正确，您需要一种高效的算法来查找两个矩形列表中所有重叠的矩形对 (R1, R2)，其中 R1 来自第一个列表，R2 来自第二个列表？ - otmar

Answer 1

首先，和许多计算几何问题一样，需要仔细指定渐近增长分析的参数：将列表长度称为m和n，最坏情况仅限这些参数是Ω(m×n)，因为所有区域可能重叠（在这方面，问题中的算法是渐近最优的）。通常需要包括输出的大小：t = f(m, n, o)（输出敏感算法）。

对于所提出的问题，显然有。

---

扫描线算法是一种通过降低一个维度来减少几何问题的范例 - 在其原始形式中，从2D到1D，平面到直线。

想象一下在平面上的所有矩形，不同颜色表示列表。
现在在这个平面上扫过一条线 - 从左到右，按传统方式，以及“对于低y坐标而言向右无限小”（按递增的x顺序处理坐标，对于相等的x，按递增的y顺序处理）。
在这个扫描过程中，每种颜色都保留一个集合，在当前x坐标处表示所有矩形的“y间隔”，起始为空。（在支持插入、删除和枚举所有与查询间隔重叠的数据结构中：见下文。）
遇到一个矩形的左侧时，将该段添加到其颜色的数据结构中。报告任何其他颜色中的重叠间隔/矩形。
在右侧，删除该段。
根据“重叠”的定义，处理左侧和右侧 - 或者反过来处理。

---

有许多数据结构支持插入和删除区间，并查找所有与查询区间重叠的区间。目前，我认为增强搜索树可能是最容易理解、实现、测试和分析的。
使用此方法，从listA和listB中枚举所有与轴对齐矩形(a, b)相交的o对应该可以在O((m+n)log(m+n)+o)时间和O(m+n)空间内完成。对于较大的问题实例，请避免使用需要更多线性空间的数据结构（例如与区间重叠相关的一种示例：段树）。

---

算法设计中的另一个范例是分而治之：对于计算几何问题，选择一个维度，使问题可以分成独立部分，并选择一个坐标，使得“坐标下方”和“坐标上方”的子问题在预期运行时间上接近。很可能还需要解决另一个（不同的）包含坐标的子问题。当a）解决子问题的运行时间“超级对数线性”时，b）有一种便宜（线性）的方法从子问题的解构造整体解时，这往往是有益的。
这适用于并发问题解决，并可与任何其他子问题方法一起使用，包括线性扫描。

---

有许多方法可以调整每种方法，其中之一是忽略无法对输出产生贡献的输入项。为了公平地比较具有类似增长顺序的算法实现，请不要追求公平的“调整水平”：尝试投入相同的时间进行调整。

- greybeard

---

可以在此处找到应用于矩形相交问题的扫描线算法的动画演示：http://bl.ocks.org/ufenegga/1a8e84a8ef7c5da945ba。该实现使用Javascript编写，应该很容易移植到Python。该程序在单个列表内查找交点，而不是在两个列表之间查找，但这并不重要。 - n. m.

这是扫描线算法。动画仅显示线交点，但包含关系由算法自然处理。 - n. m.

由于在平衡树中进行搜索/插入/删除的复杂度为_log(N)_，因此复杂度似乎为_O((m+n)*log(m+n))_。 - ivan_pozdeev

我记得在线段树的实现中，从 O(o+(m+n)*log²(m+n)) 到 O(o+(m+n)*log(m+n)) 的转换相当费力。没有好的书籍，也没有找到我的讲座笔记（三十年前的）。 - greybeard

我不熟悉Python，所以我开始对使用线性扫描查找轴对齐矩形列表之间的重叠部分进行代码审查。 - greybeard

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％）的比较，并有时增加了比较次数。但是，您的数据可能不是随机的，并且使用此类筛选可能会更好。

根据您的数据性质，您可以将其拆分为每批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%左右。上述矩形的批处理是任意的，您很可能可以做得更好。

- cdlane

Answer 3

使用numpy实现的方法，根据我的测试，速度比本问题中的方法快了大约35-40倍。对于每个包含10000个随机矩形的2个列表，该方法花费了2.5秒，而问题中的方法花费了约90秒。就复杂度而言，它仍然是O（N ^ 2），与问题中的方法相同。

import numpy as np

rects1=[
    [0,10,0,10],
    [0,100,0,100],
]

rects2=[
    [20,50,20,50],
    [200,500,200,500],
    [0,12,0,12]
]

data=np.asarray(rects2)


def find_overlaps(rect,data):
    data=data[data[::,0]<rect[1]]
    data=data[data[::,1]>rect[0]]
    data=data[data[::,2]<rect[3]]
    data=data[data[::,3]>rect[2]]
    return data


for rect in rects1:
    overlaps = find_overlaps(rect,data)
    for overlap in overlaps:
        pass#do something here

- OMRY VOLK

Answer 4

你所遇到的异常来自你展示的代码的最后一行。表达式list[rect]是无效的，因为list是一个类，在这种情况下，[]语法试图对其进行索引。你可能只需要[rect]（它创建一个包含单个项目rect的新列表）。

你的代码还存在其他几个基本问题。例如，你的Rect.__init__方法没有设置left属性，而你在碰撞测试方法中似乎期望有这个属性。此外，你在overlap方法的不同部分使用了不同的大小写形式r1和r2（Python认为r1与R1不同）。

这些问题与测试两个以上矩形并没有太大关系，而你的问题正是问到如何测试两个以上的矩形。如果你遇到像上述问题这样的基本问题，我强烈建议你坚持使用简单的算法。最简单的方法是使用现有的配对测试将每个矩形与其他矩形进行比较。你可以使用itertools.combinations轻松获取可迭代对象（如列表）中的所有项目对。

list_of_rects = [rect1, rect2, rect3, rect4] # assume these are defined elsewhere

for a, b in itertools.combinations(list_of_rects, 2):
    if a.overlap(b):
        # do whatever you want to do when two rectangles overlap here

- Blckknght

---

这意味着有更有效的算法来解决那个问题。你能否建议我这些算法？我相信我的解决方案会非常低效。 - karu

对于相对较少的矩形（例如10或20个而不是10000个），此算法的性能将是良好的。除非您绝对确定需要（例如因为您尝试了简单算法并且速度太慢），否则不要担心更大问题的性能。 - Blckknght

我有超过50000个矩形需要检查。我可以更新代码。 - karu

Answer 5

显然，如果您的列表（至少是listB）按r2.xmin排序，则可以在listB中搜索r1.xmax，并停止在此listB中测试r1的重叠（其余部分将在右侧）。这将是O(n·log(n))。

排序向量比排序列表具有更快的访问速度。

我假设矩形边缘与轴向相同。

同时根据cdlane的解释修复您的overlap()函数。

- Ripi2

Answer 6

如果您知道坐标的上下限，可以通过将坐标空间分成正方形（例如100x100）来缩小搜索范围。

• 每个坐标正方形制作一个“集合”。
• 遍历所有正方形，将它们放在任何重叠正方形的“集合”中。

另请参见使用分区加速图形操作的平铺渲染。

    // Stores rectangles which overlap (x, y)..(x+w-1, y+h-1)
    public class RectangleSet
    {
       private List<Rectangle> _overlaps;

       public RectangleSet(int x, int y, int w, int h);
    }

    // Partitions the coordinate space into squares
    public class CoordinateArea
    {
       private const int SquareSize = 100;

       public List<RectangleSet> Squares = new List<RectangleSet>();

       public CoordinateArea(int xmin, int ymin, int xmax, int ymax)
       {
          for (int x = xmin; x <= xmax; x += SquareSize)
          for (int y = ymin; y <= ymax; y += SquareSize)
          {
              Squares.Add(new RectangleSet(x, y, SquareSize, SquareSize);
          }
       }

       // Adds a list of rectangles to the coordinate space
       public void AddRectangles(IEnumerable<Rectangle> list)
       {
          foreach (Rectangle r in list)
          {
              foreach (RectangleSet set in Squares)
              {
                  if (r.Overlaps(set))
                      set.Add(r);
              }
          }
       }
    }

现在你有了一个更小的矩形集合用于比较，这应该会使速度更快。

CoordinateArea A = new CoordinateArea(-500, -500, +1000, +1000);
CoordinateArea B = new CoordinateArea(-500, -500, +1000, +1000);  // same limits for A, B

A.AddRectangles(listA);
B.AddRectangles(listB);

for (int i = 0; i < listA.Squares.Count; i++)
{
    RectangleSet setA = A[i];
    RectangleSet setB = B[i];

    // *** small number of rectangles, which you can now check thoroghly for overlaps ***

}

- user1023602

Answer 7

我认为您需要设置一个额外的数据结构（空间索引），以便快速访问附近的矩形，这些矩形可能重叠，从而将时间复杂度从二次降低到线性对数级别。

另请参见：

• https://en.wikipedia.org/wiki/Spatial_database（空间数据库）
• Spatial Index for Rectangles With Fast Insert（具有快速插入功能的矩形空间索引）
• find overlapping rectangles algorithm（查找重叠矩形算法）

- otmar

---

有_set_/static_问题，也有_query/_dynamic_问题：这个问题是一个set问题；据我所知，这些链接都是关于query问题的。 （查询算法为集合问题复杂性提供了上限。） - greybeard

@Greybeard，您说得对。然而，同样的数据结构经常可以用于高效解决集合问题。不必为每个查询使用它，通常可以使用相同的数据结构进行迭代，以解决集合问题。空间索引可用于迭代可能重叠的矩形对。 - otmar

Answer 8

对于一个简单的解决方案，如果矩形相对稀疏，则可以改进纯暴力方法：

• 将所有Y坐标排序到一个单一列表中，并为每个坐标存储矩形的索引、原始列表和用于区分底部和顶部的标志；

• 从底部向顶部扫描列表，维护两个“活动列表”，每个矩形集合一个列表；

  • 当遇到底部时，在其活动列表中插入矩形索引，并与另一个列表中的所有矩形进行比较，以检测X上的重叠；

  • 当遇到顶部时，从其活动列表中删除矩形索引。

假设使用简单的线性列表，更新和搜索将花费与活动列表大小成正比的时间。因此，您将执行M x n + m x N次比较，其中m和n表示平均列表大小，而不是M x N次比较。（如果矩形在其集合内不重叠，则可以预期平均列表长度不超过√M和√N。）

- user1196549

Answer 9

我认为下面的代码会很有用。

print("Identifying Overlap between n number of rectangle")
#List to be used in set and get_coordinate_checked_list
coordinate_checked_list = []

def get_coordinate_checked_list():
    #returns the overlapping coordinates of rectangles
    """
    :return: list of overlapping coordinates
    """
    return coordinate_checked_list

def set_coordinate_checked_list(coordinates):
    #appends the overlapping coordinates of rectangles
    """
    :param coordinates: list of overlapping coordinates to be appended in coordinate_checked_list
    :return:
    """
    coordinate_checked_list.append(coordinates)

def overlap_checked_for(coordinates):
    # to find rectangle overlap is already checked, if checked "True" will be returned else coordinates will be added
    # to coordinate_checked_list and return "False"
    """
    :param coordinates: coordinates of two rectangles
    :return: True if already checked, else False
    """
    if coordinates in get_coordinate_checked_list():
        return True
    else:
        set_coordinate_checked_list(coordinates)
        return False

def __isRectangleOverlap(R1, R2):
    #checks if two rectangles overlap
    """
    :param R1: Rectangle1 with cordinates [x0,y0,x1,y1]
    :param R2: Rectangle1 with cordinates [x0,y0,x1,y1]
    :return: True if rectangles overlaps else False
    """
    if (R1[0] >= R2[2]) or (R1[2] <= R2[0]) or (R1[3] <= R2[1]) or (R1[1] >= R2[3]):
        return False
    else:
        print("Rectangle1 {} overlaps with Rectangle2 {}".format(R1,R2))
        return True


def __splitByHeightandWidth(rectangles):
    # Gets the list of rectangle, divide the paged with respect to height and width and position
    # the rectangle in suitable section say left_up,left_down,right_up,right_down and returns the list of rectangle
    # grouped with respect to section

    """
    :param rectangles: list of rectangle coordinates each designed as designed as [x0,y0,x1,y1]
    :return:list of rectangle grouped with respect to section, suspect list which holds the rectangles
            positioned in more than one section
    """

    lu_Rect = []
    ll_Rect = []
    ru_Rect = []
    rl_Rect = []
    sus_list = []
    min_h = 0
    max_h = 0
    min_w = 0
    max_w = 0
    value_assigned = False
    for rectangle in rectangles:
        if not value_assigned:
            min_h = rectangle[1]
            max_h = rectangle[3]
            min_w = rectangle[0]
            max_w = rectangle[2]
        value_assigned = True
        if rectangle[1] < min_h:
            min_h = rectangle[1]
        if rectangle[3] > max_h:
            max_h = rectangle[3]
        if rectangle[0] < min_w:
            min_w = rectangle[0]
        if rectangle[2] > max_w:
            max_w = rectangle[2]

    for rectangle in rectangles:
        if rectangle[3] <= (max_h - min_h) / 2:
            if rectangle[2] <= (max_w - min_w) / 2:
                ll_Rect.append(rectangle)
            elif rectangle[0] >= (max_w - min_w) / 2:
                rl_Rect.append(rectangle)
            else:
                # if rectangle[0] < (max_w - min_w) / 2 and rectangle[2] > (max_w - min_w) / 2:
                ll_Rect.append(rectangle)
                rl_Rect.append(rectangle)
                sus_list.append(rectangle)
        if rectangle[1] >= (max_h - min_h) / 2:
            if rectangle[2] <= (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
            elif rectangle[0] >= (max_w - min_w) / 2:
                ru_Rect.append(rectangle)
            else:
                # if rectangle[0] < (max_w - min_w) / 2 and rectangle[2] > (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
                ru_Rect.append(rectangle)
                sus_list.append(rectangle)
        if rectangle[1] < (max_h - min_h) / 2 and rectangle[3] > (max_h - min_h) / 2:
            if rectangle[0] < (max_w - min_w) / 2 and rectangle[2] > (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
                ll_Rect.append(rectangle)
                ru_Rect.append(rectangle)
                rl_Rect.append(rectangle)
                sus_list.append(rectangle)
            elif rectangle[2] <= (max_w - min_w) / 2:
                lu_Rect.append(rectangle)
                ll_Rect.append(rectangle)
                sus_list.append(rectangle)
            else:
                # if rectangle[0] >= (max_w - min_w) / 2:
                ru_Rect.append(rectangle)
                rl_Rect.append(rectangle)
                sus_list.append(rectangle)
    return [lu_Rect, ll_Rect, ru_Rect, rl_Rect], sus_list

def find_overlap(rectangles):
    #Find all possible overlap between the list of rectangles
    """
    :param rectangles: list of rectangle grouped with respect to section
    :return:
    """
    split_Rectangles , sus_list = __splitByHeightandWidth(rectangles)
    for section in split_Rectangles:
        for rect in range(len(section)-1):
            for i in range(len(section)-1):
                if section[0] and section[i+1] in sus_list:
                    if not overlap_checked_for([section[0],section[i+1]]):
                        __isRectangleOverlap(section[0],section[i+1])
                else:
                    __isRectangleOverlap(section[0],section[i+1])
            section.pop(0)

arr =[[0,0,2,2],[0,0,2,7],[0,2,10,3],[3,0,4,1],[6,1,8,8],[0,7,2,8],[4,5,5,6],[4,6,10,7],[9,3,10,5],[5,3,6,4],[4,3,6,5],[4,3,5`enter code here`,6]]
find_overlap(arr)

- Nagaraj Rangan

Answer 10

这是我用来计算许多候选矩形（使用候选坐标[[l，t，r，b]，...]）与目标矩形（目标坐标[l，t，r，b]）重叠区域的方法：

comb_tensor = np.zeros((2, candidate_coords.shape[0], 4))

comb_tensor[0, :] = target_coords
comb_tensor[1] = candidate_coords

dx = np.amin(comb_tensor[:, :, 2].T, axis=1) - np.amax(comb_tensor[:, :, 0].T, axis=1)
dy = np.amin(comb_tensor[:, :, 3].T, axis=1) - np.amax(comb_tensor[:, :, 1].T, axis=1)

dx[dx < 0] = 0
dy[dy < 0] = 0 

overlap_areas = dx * dy

如果有许多候选矩形，这应该是相当高效的，因为所有操作都使用在ndarrays上运行的numpy函数完成。您可以通过循环计算重叠区域或者可能向comb_tensor添加一个维度来完成。

- M.Racko

---

OP明确希望避免详尽的比较，因为这将产生50000²阶的成本。 - user1196549