在随机矩形中最小化重叠

Question

在随机矩形中最小化重叠

8

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

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

有些可能只有一个角落重叠：

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

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

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

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

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

等等。

我正在尝试找到一种算法，可以给我一组代表输入集合相同区域的矩形，但没有重叠。有些情况很明显-包含在较大矩形中的矩形可以被丢弃，并且在一个角落上重叠的矩形可以分成三个矩形，与穿过另一个矩形的矩形一样。我要找的是一种通用算法，可以处理所有这些情况。如果效率不是特别高也无所谓，输入集合很小（最多25个矩形）。

查找重叠的矩形很容易，但是从那里开始就变得越来越困难，特别是考虑到一个矩形可能与多个其他矩形重叠。

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

更新：

我刚才意识到另一件事：

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

- Thomi

5个回答

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,*,#)

- Antti Huima

非常感谢，你的回答太棒了。我特别喜欢第二个解决方案，它似乎与Moron的解决方案相同。 - Thomi

1

非常有趣的问题 - 我认为最好一次解决一对矩形的问题，而不是同时考虑3个或更多个。首先丢弃那些在其他矩形内部的矩形。现在你只有三种交叉情况 - 角落重叠、穿过重叠和部分重叠（矩形没有完全穿过）。这些每个都会创建一个新的矩形集，对吧？

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

结果将是一堆不重叠的矩形。这是否会创建最少的矩形？可能不是，但您没有指定最小化矩形数量很重要。它是否需要超过o（n ^ 2）的时间？可能。

- Grembo

1

如果您的算法对矩形数量没有任何限制，那么您可以在处理时放心大胆！

1. 最简单的解决方案

创建一个集合，其中包含由输入集合中的矩形覆盖的所有面积为1的正方形。正方形就是矩形...就这样！

2. 极简主义解决方案？

好吧，那很鲁莽，但我认为您不应该担心输入集合。实际上，您的问题是不同的：

选择一个具有复杂形状的连续区域，并尝试使用矩形完全覆盖它，最小化它们的数量并使它们不重叠。

当然，您的区域可能不是连续的，但这意味着您可以独立地处理几个连续的区域。

现在，我自由承认我不知道这个问题的最佳解决方案，我可以想象出各种方法，但我不知道它们的性能或结果。KD-Tree应该能够得出解决方案，但我不知道它是否是极简主义的！

- Matthieu M.

是的，矩形数量没有明确的限制，但我需要合理一些。1x1的矩形不是一个好主意！ - Thomi

我猜你会这么做，特别是如果你打算之后继续处理它们。这只是第二个提示的开场而已 :) - Matthieu M.

0

如果您还没有一组矩形，可以从另一个角度来考虑——从一个大矩形开始，逐步细分，直到得到一组可用的矩形，这将确保没有重叠。

从一个完整的矩形开始。

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

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

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

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

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

重复执行……

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

当达到所需的矩形数量时，请停止。

通过更仔细地选择每次要拆分的矩形等方法，您可以使其产生所需的“随机性”等效果。

- deanWombourne

不，我已经有一组矩形了 - 矩形的生成不在我的控制范围内。 - Thomi

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aryabhatta · Accepted Answer

这些矩形是否平行于x和y轴？我想是的。

你可以尝试使用KD-Tree。

或者，如果你想要一些自制的东西，并且不一定高效，你可以进行“矩形化”，然后如果需要，再合并矩形。

所谓“矩形化”就是先找到一个更大的矩形，使所有矩形都适合其中（基本上是最左边缘、最右边缘、最底边缘和最高边缘组成的矩形）。

现在将所有矩形的边缘延伸到大矩形中。你现在有了一个“矩形化”。基本上，这意味着你按垂直边缘和水平边缘排序，并选择相邻对来形成一个小矩形。对于每个小矩形，你现在可以检查它是否属于感兴趣的区域，并在不属于该区域时拒绝它（它要么完全在内部，要么完全在外部）。

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

要进行合并，你可以考虑一个矩形，并考虑四种可能的合并方式（相邻的高度相同的矩形向右或向左，或者相邻的宽度相同的矩形向上或向下）。

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