高效组重叠矩形

Question

组合重叠矩形的最佳方法是什么？我试过使用OpenCV，但grouprectangles方法不能按预期工作。

我想过做这样的事情：

L = [every rectangle] 
L_next = [] 
while not L.empty(): 
    for rectangle in L: 
     L.remove(rectangle) 
     for other_rectangle in L: 
      if rectangle overlaps with other_rectangle: 
       L_next += rectangle + other_rectangle 
    L = L_next 
    L_next = [] 

由于每个未合并将从下一个列表被丢弃，在最坏的情况下矩形，我有n/2迭代外部循环。这两个内部循环应该执行n和n - 1次，以便在最坏的情况下算法应该大致为O(n^3)，假设我没有遗漏任何内容并且每个步骤仅需要O(1)。

问题：

1）需要用等价类或东西的程度，以正确合并矩形的群体。 Boost有这样的吗？

2）这似乎是必须经常进行的操作，所以我很惊讶没有找到更多的材料。那是怎么回事？ 3）假设真的没有已经实现的东西来做到这一点，有没有人有一些建议，以改善我的方法？

4）查看两个矩形重叠的最佳方法是什么？

Answer 1

我会看看pygame.Rect.collide方法来回应你的问题。由于矩形重叠检测在游戏中非常普遍，我猜他们的实现在计算复杂性方面非常好。