高效地分组重叠矩形

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的方法，可能会对你的问题有帮助。因为在游戏中，检测矩形是否重叠是非常常见的事情，所以我觉得他们的实现应该在计算效率上做得不错。