如何计算多个 rectangles/boxes 交集

Question

我有很多 2D 矩形（或者有很多 3D 方框）。

矩形可以用坐标描述(xD,yD,xB,yB)。

  A-----B
  |     |
  |     |
  D-----C

我想获取这些rectangles/boxes的交集邻接图。

我现在是用O(n^2)的方式来实现的

AdjacencyGraph graph(n);
for (int i=0;i<n;i++)
{
   for (int j=i+1;j<n;j++)
   {
       if (isItersection(boxes[i],box[j]))
       {
             graph.flagEdge(i,j);
             graph.flagEdge(j,i);
       }
   }
}

但是这种方式很慢。有没有什么快速算法可以加速这个过程？

Answer 1

1) 如果框大小不相等：

在 X-axis
通过仅在范围内比较（因为它是一维且已排序，您只比较范围内的框）为每个框生成一维邻接列表，如 [(1,2),(1,3),(1 ,5),....] 用于第一个框和 [(2,1),(2,6),..] 用于第二个框等（而不是从 index=0 开始，从 index=current 和往两个方向走，直到它超出盒子范围）
遍历 1D 邻接列表并删除重复项，或者只是不做最后一步向后（仅与更大的索引框进行比较以避免重复）
将每个框索引的邻接分组，如 [(1,a),(1,b),..(2,c),(2,d)...]
在每对的第二个框的 Y-axis 上对每组内的邻接进行排序
在每个组中，创建二维邻接表，如 [(1,f),(1,g),..]
删除重复项
再次按第一个框索引分组
每组中每对第二个框的排序 (Z)
创建 3D 邻接表
删除重复项
按第一个索引成对分组
result=current adjacency list（它是一个稀疏矩阵，所以不是完整的 O(N*N) 内存消耗，除非所有的框都接触到所有其他的）

所以总共有：

1 次完全排序 (O(N*logN))
2 部分排序，长度取决于碰撞次数
3 个集中对在一起（每个 O(N)）
删除重复项（或者只是不与较小的索引进行比较）：O(N)

这应该比 O(N^2) 更快。

2) 如果矩形大小相等，那么你可以这样做：

分散：将框索引值放入网格的虚拟单元格中（即将计算量划分为虚拟的静态单元格并将您的框放入包含所选框中心的单元格中。O(N )
gather：每个框只有一次，使用选定框周围的网格单元格，使用单元格内的索引列表检查碰撞。 O(N) x 碰撞范围内的平均邻居框

3) 如果矩形大小不等，那么您仍然可以通过多个较小的方框“构建”它们并应用第二种（2）方法。这通过乘以 k = 每个原始框的方框数增加了总计算时间复杂度。这只需要在每个较小的方框内添加一个额外的“父”框指针来更新原始框条件。

这个方法和 (2) 方法很容易并行化以获得更高的性能，但我猜 first(1) 方法应该在每个 axis-scanning 之后使用越来越少的内存，这样你就可以进入 4 维 5 -维度很容易，而 2-3 方法由于 cell-collisions 的数量增加而需要更多数据来扫描。如果所有框都接触到所有框，这两种算法都会变得太慢。

4) 如果存在“体育场内的茶壶”问题（网格的单个单元格中的所有框仍然没有接触或只有几个单元格彼此靠近）

从框中心（或任何嵌套结构）构建八叉树
计算八叉树遍历的碰撞，通过在树上up/down访问仅访问最近的节点

1-revisited) 如果盒子移动缓慢（所以你需要在每个新帧中再次重建邻接表），那么方法（1）会多一点棘手的。缓冲区太小，每帧需要re-computing，计算量大。由于缓冲区太大，它需要通过额外的过滤来维护更大的碰撞列表以获得真正的碰撞。

2-revisited) 如果环境是无限周期的（比如在 Matrix 中模拟被困在火车站的 Neo），那么你可以再次使用单元格网格，但是这次使用wrapped-around 边界作为碰撞的额外检查。

对于上述所有方法（第一种除外），您可以通过先进行球形碰撞检查（broad-collision-checking）来加速碰撞检查，以规避不必要的box-collision-checks。（球形碰撞不需要平方根，因为双方的计算相同，只需差的平方和就足够了）。这应该只提供线性加速。

对于方法 (2) 每个单元格的框数有上限，您可以使用矢量化 (SIMD) 进一步加速检查。同样，这应该会提供线性加速。

再次对于所有方法，您可以使用多线程来加速它们的某些步骤，对于另一个线性加速。

即使没有上述任何方法，问题中的两个 for 循环也可以修改为 tiled-computing，保留在 L1 缓存中以获得额外的线性性能，然后在寄存器中进行第二次平铺（SSE/AVX) 在蛮力时间复杂度期间具有峰值计算性能。对于较少数量的框，这可以运行比那些加速结构更快，而且它很简单：

select a group of boxes n=multiple of 8
    select another group of boxes n=multiple of 8
        iterate first group 8 by 8
            iterate second group 8 by 8
            Only rotate the vector to scan all 8 elements (64 collision checks for each 2 vectors)
        write results for 8 boxes in first group

坐标只有16位整数吗？然后，您可以使用 hash(distanceX,distanceY,distanceZ,sizeXYZ) 作为键并使用 true/false 作为值来缓存每个碰撞结果。

因此，解决方案取决于您的问题。什么是 N？盒子重叠很多吗？它们是在大环境中聚在一起还是稀疏地分布？系统有多少核？多少内存？箱子在移动吗？速度有多快？您 run-time 期望多少箱子？

编辑：我尝试用不到 500 行代码写一个 adaptive-grid（针对“体育场内的茶壶”问题优化了第二种方法）：https://github.com/tugrul512bit/FastCollisionDetectionLib

它没有针对降低 buffer-allocation 开销进行优化，不是多线程的，也不是矢量化的，但是对于均匀分布的粒子它会线性放大，并且当一些粒子聚集在一起距离质心 100 倍时接近线性。根据 20k 到 100k 之间的粒子数量，它比蛮力方法快数百到数千倍。也没有测试不等形状的盒子，只有相同的盒子。

Answer 2

对于第一个简单的解决方案，您可以将框存储为成对的三元组（Y、Xleft、Xright），并带有标志以区分顶部和底部 Y。[由于 X 重复，您可以保留一些区分的特殊值。]

然后在 Y 上排序并通过增加 Y 进行扫描，同时维护一个“活动列表”。当遇到顶部三元组时，将其插入活动列表，对于底部，将其删除。现在你有一个一维区间重叠问题。

与上面类似，您可以在活动列表中输入间隔作为两个不同的条目，Xleft 和 Xright 加上一个标志。排序 left-to-right 后，您通过辅助活动列表扫描活动列表以获取重叠间隔。您可以显式排序，或维护使用有序集排序的列表。

3D 情况类似，但多了一个阶段。你首先在Z上排序，活动列表将由二维矩形组成，你在上面使用上面的程序。

如何计算多个 rectangles/boxes 交集

how to calculate many rectangles/boxes intersection

algorithm