找到 N 个矩形重叠的有效方法
Efficient way to find overlapping of N rectangles
我正在尝试找到一种有效的解决方案来查找 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]
这是从 class 创建的：
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):
有什么更有效的方法来处理这个问题吗？
您遇到的异常来自您显示的代码的最后一行。表达式 list[rect] 无效，因为 list 是一个 class，并且该上下文中的 [] 语法正在尝试对其进行索引。您可能只需要 [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
首先：与 computational geometry, specifying the parameters for order-of-growth analysis needs care: calling the lengths of the lists m and n, the worst case in just those parameters is Ω(m×n), as all areas might overlap (in this regard, the algorithm from the question is asymptotically optimal). It is usual to include the size of the output: t = f(m, n, o) (Output-sensitive algorithm 中的许多问题一样）。
平凡地，f ∈ Ω(m+n+o) 对于所提出的问题。
Line Sweep 是一种将几何问题减少一维的范例 - 以其原始形式，从二维到一维，从平面到线。
想象一下平面中的所有矩形，列表的颜色不同。
现在在这个平面上扫一条线 - 按照惯例从左到右，无限 进一步向右“对于低 y 坐标”（处理坐标 x-order，递增 y-order 等于 x).
对于所有这些 sweep（或 scan），每种颜色保留一组代表当前 x- 处所有矩形的“y 间隔”坐标，开始为空。 （在支持插入、删除和枚举与 查询区间 重叠的所有区间的数据结构中：见下文。）
遇到矩形的左侧，将段添加到其颜色的数据结构中。报告任何其他颜色的重叠 intervals/rectangles。
在右侧，删除线段。
根据“重叠”的定义，先处理左侧再处理右侧 - 或者反过来。
有许多数据结构支持区间的插入和删除，并找到与查询区间重叠的所有区间。目前，我认为 Augmented Search-Trees 可能是最容易理解、实施、测试、分析的……
使用这个，从 listA 和 listB 枚举所有 o 相交的轴对齐矩形对 (a, b)应该可以在 O((m+n)log(m+n)+o) 时间和 O(m+n) space。对于相当大的问题实例，避免需要超过线性 space 的数据结构（（原始）Segment Trees，例如与间隔重叠有关的示例）。
算法设计的另一种范式是Divide&Conquer：对于一个计算几何问题，选择一个可以将问题划分为独立部分的维度，以及一个坐标使得子问题的“坐标如下" 和 "上面的坐标" 在预期的 运行 时间内接近。很可能需要解决另一个（不同的）子问题“包括坐标”。当 a) 解决子问题的 运行 时间是“超对数线性”时，这往往是有益的，并且 b) 有一种廉价的（线性）方法可以从以下解决方案构建整体解决方案子问题。
这有助于同时解决问题，并且可以与任何其他方法一起用于子问题，包括线扫描。
可以通过多种方式调整每种方法，首先是忽略可能对输出没有贡献的输入项。为了“公平地”比较类似增长顺序的算法的实现，不要以公平的“调整程度”为目标：尝试投入公平的时间进行调整。
我认为您必须设置一个额外的数据结构（空间索引），以便快速访问可能重叠的附近矩形，从而将时间复杂度从二次方降低到线性。
另请参阅：
- https://en.wikipedia.org/wiki/Spatial_database
- Spatial Index for Rectangles With Fast Insert
- find overlapping rectangles algorithm
几个潜在的小效率改进。首先，修复您的 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
其次，计算其中一个列表的包含矩形并用它来筛选另一个列表——任何不与容器重叠的矩形都不需要针对 all[ 进行测试=27=] 对它有贡献的矩形：
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%，甚至包括容器矩形比较。上面的矩形批处理是任意的，您可能会做得更好。
根据我做的测试，这个使用 numpy 的实现大约快 35-40 倍。对于 2 个列表，每个列表都有 10000 个随机矩形，此方法耗时 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
显然，如果您的列表（至少是 listB）按 r2.xmin 排序，您可以在 listB 中搜索 r1.xmax 并停止测试此 listB 中 r1 的重叠（其余的将是正确的）。这将是 O(n·log(n))。
已排序的向量比已排序的列表具有更快的访问速度。
我假设矩形边的方向与轴相同。
同时按照 cdlane 的说明修复您的 overlap() 函数。
如果您知道坐标的上限和下限，则可以通过将坐标 space 划分为正方形来缩小搜索范围，例如100x100。
- 每个坐标方格制作一个"set"。
- 遍历所有方块，将它们放在它们重叠的任何方块的 "set" 中。
另请参阅 Tiled Rendering，它使用分区来加速图形操作。
// 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 ***
}
这是我用来计算许多候选矩形（candidate_coords [[l, t, r, b], ...]）与目标矩形（target_coords [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.
添加一个维度
我正在尝试找到一种有效的解决方案来查找 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]
这是从 class 创建的：
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):
有什么更有效的方法来处理这个问题吗？
您遇到的异常来自您显示的代码的最后一行。表达式 list[rect] 无效，因为 list 是一个 class，并且该上下文中的 [] 语法正在尝试对其进行索引。您可能只需要 [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
首先：与 computational geometry, specifying the parameters for order-of-growth analysis needs care: calling the lengths of the lists m and n, the worst case in just those parameters is Ω(m×n), as all areas might overlap (in this regard, the algorithm from the question is asymptotically optimal). It is usual to include the size of the output: t = f(m, n, o) (Output-sensitive algorithm 中的许多问题一样）。
平凡地，f ∈ Ω(m+n+o) 对于所提出的问题。
Line Sweep 是一种将几何问题减少一维的范例 - 以其原始形式，从二维到一维，从平面到线。
想象一下平面中的所有矩形，列表的颜色不同。
现在在这个平面上扫一条线 - 按照惯例从左到右，无限 进一步向右“对于低 y 坐标”（处理坐标 x-order，递增 y-order 等于 x).
对于所有这些 sweep（或 scan），每种颜色保留一组代表当前 x- 处所有矩形的“y 间隔”坐标，开始为空。 （在支持插入、删除和枚举与 查询区间 重叠的所有区间的数据结构中：见下文。）
遇到矩形的左侧，将段添加到其颜色的数据结构中。报告任何其他颜色的重叠 intervals/rectangles。
在右侧，删除线段。
根据“重叠”的定义，先处理左侧再处理右侧 - 或者反过来。
有许多数据结构支持区间的插入和删除，并找到与查询区间重叠的所有区间。目前，我认为 Augmented Search-Trees 可能是最容易理解、实施、测试、分析的……
使用这个，从 listA 和 listB 枚举所有 o 相交的轴对齐矩形对 (a, b)应该可以在 O((m+n)log(m+n)+o) 时间和 O(m+n) space。对于相当大的问题实例，避免需要超过线性 space 的数据结构（（原始）Segment Trees，例如与间隔重叠有关的示例）。
算法设计的另一种范式是Divide&Conquer：对于一个计算几何问题，选择一个可以将问题划分为独立部分的维度，以及一个坐标使得子问题的“坐标如下" 和 "上面的坐标" 在预期的 运行 时间内接近。很可能需要解决另一个（不同的）子问题“包括坐标”。当 a) 解决子问题的 运行 时间是“超对数线性”时，这往往是有益的，并且 b) 有一种廉价的（线性）方法可以从以下解决方案构建整体解决方案子问题。
这有助于同时解决问题，并且可以与任何其他方法一起用于子问题，包括线扫描。
可以通过多种方式调整每种方法，首先是忽略可能对输出没有贡献的输入项。为了“公平地”比较类似增长顺序的算法的实现，不要以公平的“调整程度”为目标：尝试投入公平的时间进行调整。
我认为您必须设置一个额外的数据结构（空间索引），以便快速访问可能重叠的附近矩形，从而将时间复杂度从二次方降低到线性。
另请参阅：
- https://en.wikipedia.org/wiki/Spatial_database
- Spatial Index for Rectangles With Fast Insert
- find overlapping rectangles algorithm
几个潜在的小效率改进。首先，修复您的 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
其次，计算其中一个列表的包含矩形并用它来筛选另一个列表——任何不与容器重叠的矩形都不需要针对 all[ 进行测试=27=] 对它有贡献的矩形：
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%，甚至包括容器矩形比较。上面的矩形批处理是任意的，您可能会做得更好。
根据我做的测试，这个使用 numpy 的实现大约快 35-40 倍。对于 2 个列表，每个列表都有 10000 个随机矩形，此方法耗时 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
显然，如果您的列表（至少是 listB）按 r2.xmin 排序，您可以在 listB 中搜索 r1.xmax 并停止测试此 listB 中 r1 的重叠（其余的将是正确的）。这将是 O(n·log(n))。
已排序的向量比已排序的列表具有更快的访问速度。
我假设矩形边的方向与轴相同。
同时按照 cdlane 的说明修复您的 overlap() 函数。
如果您知道坐标的上限和下限，则可以通过将坐标 space 划分为正方形来缩小搜索范围，例如100x100。
- 每个坐标方格制作一个"set"。
- 遍历所有方块，将它们放在它们重叠的任何方块的 "set" 中。
另请参阅 Tiled Rendering，它使用分区来加速图形操作。
// 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 ***
}
这是我用来计算许多候选矩形（candidate_coords [[l, t, r, b], ...]）与目标矩形（target_coords [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.
添加一个维度