如何计算多个矩形/盒子的交集

Question

如何计算多个矩形/盒子的交集

4

我有许多二维矩形（或者许多三维盒子）。

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

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

我希望获得这些矩形/盒子的交集邻接图。

我现在正在使用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);
       }
   }
}

但是这种方法非常缓慢。是否有任何快速的算法可以加速这个过程？

- Xu Hui

3

你可以使用线性扫描算法进行计算，这个例子可以作为参考：https://dev59.com/eLLma4cB1Zd3GeqPXjuc#54972068 - Aldert

有多少个矩形？是稀疏的还是密集的，有许多重叠？ - user1196549

@YvesDaoust。大约有20,000个盒子，每个盒子的坐标都用双精度描述。邻接图应该是稀疏的。 - Xu Hui

2个回答

2

为了一个简单的解决方案，您可以将盒子存储为三元组对（Y，Xleft，Xright），并使用标志来区分顶部和底部的Y。[由于X是重复的，您可以保留一些特殊值以进行区分。]

然后按Y排序，并按递增Y扫描，同时维护“活动列表”。当您遇到顶部三元组时，请将其插入活动列表中，对于底部，请删除它。现在您有一个1D区间重叠问题。

与上述类似，您可以将区间作为两个不同的条目（Xleft和Xright）输入到活动列表中，并加上标志。从左到右排序后，通过次要活动列表获取重叠的区间。您可以显式排序，也可以使用有序集合维护已排序的列表。

3D情况类似，但多了一个阶段。您首先按Z排序，活动列表将由2D矩形组成，并在其上使用上述过程。

- user1196549

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- huseyin tugrul buyukisik · Accepted Answer

1) 如果盒子的大小不相等：

在X轴上对盒子进行排序
通过仅在范围内比较（因为它是1D且已排序，所以只需比较范围内的盒子），为每个盒子生成1D邻接列表，例如第一个盒子为[(1,2),(1,3),(1,5),....]，第二个盒子为[(2,1),(2,6),..]等(从当前索引开始而非从索引0开始，向两个方向迭代直到超出盒子范围)
遍历1D邻接列表并删除重复项或仅在向后处理时不执行最后一步（仅与大于索引的盒子进行比较以避免重复）
将邻接点按盒子索引分组，例如[(1,a),(1,b),..(2,c),(2,d)...]
在每个组内按Y轴对第二个盒子的邻接点进行排序
在每个组内，创建2D邻接列表，例如[(1,f),(1,g),..]
删除重复项
再次按第一个盒子索引分组
对每个组中第二个盒子的Z值进行排序
创建3D邻接列表
删除重复项
按对中的第一个索引进行分组
结果为当前邻接列表（它是稀疏矩阵，因此除非所有盒子都与其他盒子相接触，否则不会占用完整的O(N * N)内存消耗）

因此，总共需要：

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

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

2) 如果矩形大小相等，则可以执行以下操作：

scatter：将盒子索引值放入网格的虚拟单元格中（即将计算体积划分为想象的静态单元格，并将盒子放入包含所选盒子中心的单元格中。 O（N）
gather：每个盒子仅执行一次，使用周围的网格单元格，在碰撞范围内检查碰撞，使用单元格内的索引列表。 O(N) x 平均相邻盒子数量

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

这个方法和第二个方法可以轻松并行化，以获得更高的性能。但我认为第一个方法应该在每次扫描轴后使用越来越少的内存，因此您可以轻松地进行4维、5维等操作，而第二种和第三种方法需要处理更多数据，因为碰撞单元格数量增加了。如果所有框都接触所有框，则两种算法都可能变得太慢。

4) 如果有“体育场中的茶壶”问题（所有框在网格的单个单元格中，仍然不接触或仅相距几个单元格），

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

1-revisited) 如果框移动缓慢（因此您需要在每个新帧中重新构建邻接列表），则方法（1）会变得有些棘手。缓冲区域太小，需要在每个帧上重新计算，计算量很大。缓冲区域太大，则需要维护更大的碰撞列表，并进行额外的过滤以获取真正的碰撞。

2-revisited) 如果环境是无限周期的（例如在模拟《黑客帝国》中被困在火车站中的Neo），则可以再次使用单元格网格，但这次要使用包裹边界作为额外的碰撞检查。

对于上述所有方法（除第一个方法外），您可以通过先进行球形碰撞检查（广泛碰撞检查）来加速碰撞检查，以避免不必要的框碰撞检查。（球形碰撞不需要平方根，因为两侧具有相同的计算，只需平方差之和即可）。这应该只会线性加速。

对于每个单元格具有限定数量的框的方法（2），您可以使用向量化（SIMD）来进一步加速检查。同样，这应该会给出线性加速。

对于所有方法，您可以使用多个线程来加速其中一些步骤，从而实现另一个线性加速。

即使没有上述任何方法，问题中的两个for循环也可以修改为进行瓷砖计算，以保持在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位整数吗？那么您可以使用哈希(distanceX，distanceY，distanceZ，sizeXYZ)作为键和true/false作为值来缓存每个碰撞结果。

因此，解决方案取决于您的问题。N是多少？箱子重叠很多吗？它们堆积在一个大环境中还是散布开来？系统中有多少个核心? 有多少内存？盒子是否移动以及移动速度如何？您对多少个盒子的运行时期望是什么？

编辑：我尝试编写了一个自适应网格（对“体育场里的茶壶”问题进行了优化），代码不到500行：https://github.com/tugrul512bit/FastCollisionDetectionLib

它没有优化以降低缓冲区分配开销，也不是多线程和向量化的，但对于均匀分布的粒子和离质心100倍远的一些距离结合在一起的粒子，它可以线性扩展。它比暴力方法快数百到数千倍，取决于粒子数量在20k到100k之间。但还没有针对不同形状的盒子进行测试，只针对相同的盒子。