合并重叠的轴对齐矩形

Question

我有一组轴对齐的矩形.当两个矩形重叠(部分或完全)时,它们将合并到它们的公共边界框中.此过程以递归方式工作.

检测所有的重叠和使用工会发现,形成组,您合并,最终将无法工作,因为两个矩形的合并覆盖更大面积,可以创造新的重叠.(在下图中,合并了两个重叠的矩形后,会出现新的重叠.)

在我的情况下,矩形的数量是中等的(比如N <100),可以使用强力解决方案(尝试所有对,如果发现重叠,则从头开始合并并重新启动).无论如何,我想降低复杂性,在最坏的情况下可能是O(N³).

有什么建议如何改善这个？

Answer 1

使用平衡归一化四叉树。

标准化：收集所有 x 坐标，对它们进行排序，并将它们替换为排序数组中的索引。y 坐标也是如此。

平衡：构建四叉树时始终在中间坐标处分裂。

因此，当您获得一个矩形时，您需要使用该矩形的某个 id 来标记树中的正确节点。如果您在下面发现任何其他矩形（这意味着它们将重叠），请将它们收集在一组中。完成后，如果向量不为空（您发现了重叠的矩形），那么我们将创建一个新的矩形来表示子矩形的并集。如果计算出的矩形比您刚刚插入的矩形大，则使用新计算出的矩形再次应用该算法。重复此操作，直到它不再增长，然后移动到下一个输入矩形。

为了提高性能，四叉树中的每个节点除了将其标记为结束节点之外，还存储与该节点重叠的所有矩形。

复杂性：初始标准化为O(NlogN)。插入并检查重叠将是O(log(N)^2)。您需要对原始 N 个矩形以及重叠部分执行此操作。每次找到重叠时，您都会消除至少一个原始矩形，这样您最多可以找到 (N-1) 个重叠。所以总的来说你需要 2N 次操作。所以总体来说复杂度是O(N(log(N)^2))。

这比其他方法更好，因为您不需要检查任意矩形之间的重叠。