algorithm - 最小化随机矩形中的重叠

Question

我有许多可能重叠的矩形，它们在固定平面内具有随机大小和位置。由于这些矩形是随机的，有些可能不会重叠:

|-----|    |    |----||----|    |    |          |----|

有些可能只重叠一个角:

|-----||  |--|--||--|--|  |   |-----|

有些可能包含在另一个矩形内:

|----------------||                ||   |-----|      ||   |     |      ||   |-----|      ||----------------|

有些可能会穿过另一个矩形:

   |----------------|   |                ||--|-------------------||  |                |  ||--|-------------------|   |----------------|

等等

我正在尝试找到一种算法，该算法可为我提供一组代表与输入集相同但不重叠的区域的矩形。有些情况是显而易见的——包含在一个较大矩形内的矩形可以被丢弃，并且在一个角上重叠的矩形可以被分成三个矩形，就像穿过另一个矩形的矩形一样。我正在寻找的是一种处理所有这些情况的通用算法。我不在乎它是否高效——输入集相当小(最多 25 个矩形)

找到重叠的矩形很容易，但很快就会变得更难，尤其是当您认为一个矩形可能与多个其他矩形重叠时。

这让我很头疼。有什么建议吗？

更新:

我刚刚意识到一件事:

我可以在将矩形逐个添加到他的集合时运行此算法，也可以在添加所有矩形之后运行此算法。随着矩形的添加，这样做可能会更容易，因为您只需要考虑一个矩形，但您仍然需要考虑单个矩形与多个其他矩形重叠的情况。

Answer 1

矩形是否平行于 x&y 轴？我想他们是。

您可以尝试使用 KD-Trees .

或者，如果您想要自己开发的东西但不一定高效，您可以“矩形化”，然后在需要时将矩形合并回来。

“矩形”是指您首先找到一个更大的矩形，所有矩形都适合(基本上是由最小左边缘、最大右边缘、最小底部边缘、最大顶部边缘形成的矩形)。

现在延伸出矩形的所有边以切割大矩形。你现在有一个“矩形”。基本上所有这些意味着您对垂直边缘和水平边缘进行排序并选择相邻的对以形成一个小矩形。对于每个小矩形，您现在可以检查它是否是感兴趣区域的一部分，如果不是则拒绝它(它要么完全位于内部，要么完全位于外部)。

现在您有一个小矩形列表(可能是 O(n^2)，在您的情况下可能是 ~2500)，它们构成了您感兴趣的区域。如果这个数字对于您 future 的处理来说足够小，您可以只使用这些，或者您可以将它们合并在一起以减少矩形的数量。

要合并，您可以考虑一个矩形并考虑合并的 4 种可能性(右侧或左侧高度相同的相邻矩形，或顶部或底部宽度相同的相邻矩形)。

您可以通过维护排序的边列表(水平和平行)和一些哈希表来加快某些处理(不仅仅是在合并期间)。