algorithm - 查找覆盖多个区域的最大连续矩形集

Question

This question already has an answer here:

Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
（1个答案）
我正在为游戏开发一个叫做 Quickfort的工具。quickfort将csv/xls格式的电子表格转换为矮人堡垒执行的一系列命令，以便在游戏中绘制“蓝图”。
我目前正试图以最佳方式解决此工具2.0版的面积绘制问题。
考虑下面的“蓝图”，它定义了二维网格的打印命令。网格中的每个单元格要么被挖出（“d”），要么被引导（“c”），要么被保留为未被标记（“0”）。实际使用中可能会出现任意数量的不同打印命令。

. d . d c c
d d d d c c
. d d d . c
d d d d d c
. d . d d c

为了尽量减少需要发送到dwarf forces的指令数量，我想找到一组最大的连续矩形，这些矩形可以完全覆盖或“绘制”所有可绘制单元。为了有效，给定矩形的所有单元格都必须包含相同的命令。
这是一种比QuickFort1.0更快的方法：将每个单元格单独绘制为1x1矩形。 Dwarf Fortress显示了两个版本之间的性能差异。
对于上述蓝图，解决方案如下：

. 9 . 0 3 2
8 1 1 1 3 2
. 1 1 1 . 2
7 1 1 1 4 2
. 6 . 5 4 2

上面每个编号相同的矩形表示一个连续的矩形。最大的矩形优先于在其区域中也可以形成的较小的矩形。编号/矩形的顺序并不重要。
my This video是迭代的。在每次迭代中，我都会通过从网格的可绘制单元格向所有4个方向扩展来生成一个最大矩形列表。首先对列表进行最大排序后，我从找到的最大矩形开始，将其基础单元格标记为“打印”，并将矩形记录在列表中。在打印每个矩形之前，将检查其基础单元格以确保它们尚未打印（重叠上一个打印）。然后我们再次开始，找到可以形成的最大剩余矩形，并绘制它们，直到所有单元格都被绘制为某个矩形的一部分。
我认为这种方法比愚蠢的蛮力搜索稍微优化一些，但是我浪费了很多周期（重新）计算单元格的最大矩形并检查底层单元格的状态。
目前，这个矩形发现例程占据了该工具总运行时间的大部分，特别是对于大型蓝图。为了提高速度，我牺牲了一些精度，只考虑了来自看起来形成矩形角的单元格的矩形（使用一些相邻的单元格启发式方法确定，这些方法并不总是正确的）。作为这种“优化”的结果，我当前的代码实际上并不能正确地生成上面的解决方案，但它已经足够接近了。
更广泛地说，我认为最大矩形的目标首先是为这个应用程序提供“足够好”的方法。但是，我观察到，如果目标是找到完全覆盖多个区域的最小矩形集（最少数量），则解决方案如下：

. 3 . 5 6 8
1 3 4 5 6 8
. 3 4 5 . 8
2 3 4 5 7 8
. 3 . 5 7 8

第二个目标实际上代表了问题的一个更优化的解决方案，因为更少的矩形通常意味着发送到矮人堡垒的命令更少。然而，基于我有限的数学知识，这种方法让我觉得更接近np-hard。
如果你想更好地理解整体策略，请注意；我还没有讨论quickfort过程的其他方面，比如寻找绘制所有矩形的最短光标路径。可能有一个解决这个问题的办法，把这些多重策略连贯地结合起来。
任何形式的帮助都将不胜感激。

最佳答案

我找到了吴三元和萨尔泰的论文，你可能会感兴趣。在您的示例中，字符为“d”的区域形成一个直线多边形，也形成了字符为“c”和“.”的区域。本文包括无孔简单直线多边形的算法。
如果一个多边形包含孔，则存在运行时间为o（n^3/2 logn）的算法，正如jm keil在论文Fast Algorithms To Partition Simple Rectilinear Polygons第11页所述。
如果将分割过程中引入的线段的总长度最小化作为另一个优化准则，则如果多边形包含孔，则问题将成为np完全问题（第12页）。对于这些问题，存在近似算法（本文引用具有这种算法的论文）。如果多边形不包含孔，则有一个o（n^4）时间算法。

关于algorithm - 查找覆盖多个区域的最大连续矩形集，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4701887/

上一篇：javascript - JavaScript 中颜色量化/减少图像调色板的算法？

下一篇：algorithm - 使用 A* 解决旅行商问题

Answer 1

我找到了吴三元和萨尔泰的论文，你可能会感兴趣。在您的示例中，字符为“d”的区域形成一个直线多边形，也形成了字符为“c”和“.”的区域。本文包括无孔简单直线多边形的算法。
如果一个多边形包含孔，则存在运行时间为o（n^3/2 logn）的算法，正如jm keil在论文Fast Algorithms To Partition Simple Rectilinear Polygons第11页所述。
如果将分割过程中引入的线段的总长度最小化作为另一个优化准则，则如果多边形包含孔，则问题将成为np完全问题（第12页）。对于这些问题，存在近似算法（本文引用具有这种算法的论文）。如果多边形不包含孔，则有一个o（n^4）时间算法。