如何将一个由等大小的正方形组成的网格缩小为最少的矩形集合？

Question

6

如果我有一个任意大小的等大小正方形网格（它们之间没有间隔），我需要知道一种有效的方法将它们缩小到最小数量的矩形中，例如，如果每个星号代表一个正方形，则可以将其缩小为一个大矩形：

*****
*****
*****

虽然这可以缩小为两个矩形：

  ***             ***
*****   =>  **(1) ***(2)
*****       **    ***
  ***             ***

一种显而易见的解决方案是收集每行相邻的正方形，然后收集相同的相邻行。对于我的第二个例子，这将找到三个矩形，但这并不是最优解。

  *** (1)

***** (2)
*****

  *** (3)

我想知道是否有更成功和高效的算法来完成这个任务。

- peterjwest

请尝试使用Google搜索“最小矩形覆盖”。 - Bart Kiers

@Tryer 我可以接受启发式方法，但我希望有比这更好的解决方案。 - peterjwest

@belisarius：如果这是一个分配算法的广告，那么页面的布局真的很奇怪。我仍然希望原帖作者回答。 - Yakov Galka

@ybungalobill 抱歉，我误解了之前的 OP 评论。 - Dr. belisarius

它是游戏引擎的一部分，最少的矩形意味着最少的碰撞检测。它们不应该重叠。 - peterjwest

显示剩余8条评论

2个回答

0

我不确定是否已经有这个算法，所以我自己编了一个：

找到（xmin，ymin）（xmax，ymax），即现有正方形的x和y坐标的最小值和最大值。这定义了一个包围所有正方形的单个边界矩形。

在边界矩形内查找并连接凹角直线。

回答评论：如果我们沿着网格线连接所有凹周长角，并逐渐删除（标记）外围矩形，则在上面的复杂示例中会得到以下结果：

   A
   XBB
CCCX
   XDD
   X
 EFFFG
  I J
  I J

正如所指出的那样，这是次优的。当有多种方式可以成对连接凹陷时，需要做出一些决策以确定连接顺序。选择导致新矩形数量最少的选项（请参见最低 X 下的 F）。

当分割完成后，我们现在添加另一个阶段来扩展（合并）现有的矩形。关键是只允许这样的合并，即不会减少任何现有矩形。将最上面的 X 更改为 B 就是这样一种不允许的更改，因为 X 的矩形已经被减少了。此条件保证更改只朝着最小矩形数的方向进行。继续对上述示例执行此过程，我们得到：

   X
   XBB
CCCX
   XDD
   X
 FFFFF
  I J
  I J

在这个例子中，这恰好是最优的，但通常情况下，您可能需要使用这些操作进行状态空间搜索，以找到全局最小值。

- Liberius

你能给一个简单的例子吗？我不太理解这个逻辑。 - peterjwest

这个会导致矩形分区...但不是最小的。 - Dr. belisarius

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

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

- 6502 · Accepted Answer

我有一种直觉，认为这个问题可能会很复杂......例如考虑

   *
   ***
****
   ***
   *

最优解是4。

   B
   BCC
AAAB
   BDD
   B

但我并没有找到一种简单的方法来通过本地推理预测A应该在最后一个方块之前停止。在最优解中，A、C和D都不是最大矩形，只有B是最大的。事情可能会变得更加复杂，例如：

   *
   ***
****
   ***
   *
 *****
  * *
  * *

最优解所在的位置

   B
   BCC
AAAB
   BDD
   B
 EEEEE
  F G
  F G

只有E是最大的。看起来构建任意大的问题实际上很容易，在最优解中只有一个矩形不是最大的。

当然，这并不意味着没有简单的解决方案存在...就像我说的那样，这是一种直觉，但是如果需要绝对最小值，我认为任何使用最大矩形进行推理的求解器都会遇到问题。

对于一个有些类似但又不同的问题（我正在寻找非必要不相交圆盘的最小覆盖），我使用了一种缓慢的贪心方法，总是将包含并覆盖大多数未被覆盖的正方形的圆盘添加到解决方案中。

对于你的问题，我可能会尝试每次添加最大的包含矩形...但是正如上面的例子所示，这通常不是最优解。