8

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

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

有些可能只重叠一个角：

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

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

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

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

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

等等

我正在尝试找到一种算法，它可以为我提供一组矩形，这些矩形代表与输入集相同的区域，但没有重叠。有些情况很明显 - 包含在较大矩形中的矩形可以被丢弃，重叠在一个角上的矩形可以分成三个矩形，穿过另一个矩形的矩形也可以。我正在寻找的是一种处理所有这些情况的通用算法。我不在乎它是否效率不高 - 输入集相当小（最多 25 个矩形）

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

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

更新：

我又意识到了一件事：

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

4

5 回答 5

3

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

您可以尝试使用KD-Trees。

或者，如果您想要本土的东西并且不一定高效，您可以“矩形化”，然后如果需要合并矩形。

通过“矩形”，我的意思是您首先找到一个更大的矩形，其中所有矩形都适合（基本上由最小左边缘、最大右边缘、最小底部边缘、最大顶部边缘形成的矩形）。

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

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

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

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

于 2010-02-11T19:39:25.513 回答
1

首先在合成中创建所有“原子”矩形的集合，即由矩形交叉点形成的区域，并且它们本身没有被细分。每个实际矩形覆盖 1 个或多个原子矩形。然后运行组合优化算法，例如SETCOVER 来计算您需要覆盖所有矩形的最小数量。

这里是该方法的说明。你有三个矩形（A，B，C）。它们创建 5 个原子区域 (1-5)：

 +---------+A
 |       1 |
 |    +----+-----+B
 |    |  2 | 3   |
 |    |  +-+---+C|
 |    |  |4|   | |
 +----+--+-+ 5 | |
      |  +-----+ |
      +--+-------+

根据下表，矩形覆盖原子区域：

 A  {1,2,4}
 B  {2,3,4,5}
 C  {4,5}

SETCOVER 问题现在是选择矩形 {A,B,C} 的最小子集，以便在将矩形覆盖的原子区域放在一起时覆盖所有原子区域。最小的解决方案是（显然）

 A {1,2,4} + B {2,3,4,5} = {1,2,3,4,5}

请注意，这里的区域是非矩形的，例如区域 3 具有复杂的形状。您可以通过以下方法摆脱这个问题：获取原始矩形角点的所有不同 X 坐标，并将它们视为网格的 X 坐标，并对 Y 坐标执行相同的操作；那么每个矩形都覆盖了一组从不细分的网格正方形，即：

 +---------+A       -
 |       1 |
 |    +----+-----+B -
 |    |  2 | 3   |
 |    |  +-+---+C|  -
 |    |  |4|   | | 
 +----+--+-+ 5 | |  -
      |  +-----+ |  -
      +--+-------+  -

 |    |  | |   | |

这为您提供了以下 5x5 网格：

 AAA      A = rectangle A only
 A**BB    B = rectangle B only
 A*#CB    * = A and B
  BCCB    C = rectangles C and B
  BBBB    # = All

从中您可以轻松提取 5 个区域；事实上，它们已经被标记了:) (A,B,C,*,#)

于 2010-02-11T17:12:23.163 回答
1

如果您对算法应该生成的矩形数量没有任何限制，那么您的治疗肯定会轻率！

1. 最简单的解决方案

创建一组由输入集的矩形覆盖的所有正方形（区域 1）。一个正方形就是一个长方形……你来了！

2. 极简主义的解决方案？

好的，这很草率，但是我认为您不必担心输入集。你的问题实际上是不同的：

选择一个具有复杂形状的连续区域，并尝试用矩形准确地覆盖它，尽量减少它们的数量，这样它们就不会重叠。

当然，您的区域可能不是连续的，但这只是意味着您有几个可以独立工作的连续区域。

现在，我坦率地承认我不知道这个问题的最佳解决方案，我可以设想各种方法，但我不知道它们的性能或结果。KD-Tree应该会产生一个解决方案，但不知道它是否是极简主义的！

于 2010-02-12T12:05:08.050 回答
1

非常有趣的问题 - 我认为最好一次解决一对矩形而不是一次查看 3 个或更多。首先丢弃其他矩形内的那些。现在你只有 3 种交叉点 - 角重叠和通过重叠和部分重叠（矩形没有一直通过）。这些都创建了一组新的矩形，对吧？

从 1 到 N 将起始矩形编号。从矩形 1 开始循环，直到找到相交的矩形。创建新的矩形。删除两个相交的矩形并将 3 个或更多新创建的矩形添加到您的集合中并重新开始。

结果将是一大堆不重叠的矩形。这会创建最少的矩形吗？可能不是，但您没有指定最小化矩形数量很重要。它会占用 o(n^2) 时间吗？大概。

于 2010-02-11T19:48:32.747 回答
0

如果您还没有一组矩形，您可以从另一种方式处理它 - 从一个大矩形开始并细分它，直到您有一个可以使用的集合 - 这将确保您没有重叠。

从整个矩形开始

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

在随机点拆分并存储两个矩形。

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

在随机点分割一个随机矩形

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

重复 。. .

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

当您拥有所需数量的矩形时停止。

您可以通过更仔细地选择每次要拆分的矩形等来使这产生您想要的那种“随机性”

于 2010-02-11T17:22:51.080 回答