find一组最大的连续矩形来覆盖多个区域
我正在为“ 矮人堡垒”（Dwarf Fortress）这款游戏开发一款名叫“ Quickfort ”的工具。 Quickfort将csv / xls格式的电子表格转换为一系列矮人要塞的命令，以便在游戏中绘制“蓝图”。
我目前正在尝试优化解决这个工具的2.0版本的面积绘图问题。
考虑下面的“蓝图”，它定义了二维网格的绘图命令。 网格中的每个单元格应该挖出（“d”），通道（“c”）或不保留（“。”）。 实际使用中可能会出现任意数量的不同绘图命令。
. d . dcc ddddcc . ddd . c dddddc . d . ddc 为了尽量减less需要发送给矮人堡垒的指令数量，我想find一组最大的连续矩形，它们可以形成为完全覆盖或“绘制”所有绘图单元格。 为了有效，给定矩形的所有单元必须包含相同的命令。
这是比Quickfort 1.0更快的方法：将每个单元分别绘制为1×1的矩形。 这个video显示了两个版本之间的性能差异。
对于上面的蓝图，解决scheme如下所示：
. 9 . 0 3 2 8 1 1 1 3 2 . 1 1 1 . 2 7 1 1 1 4 2 . 6 . 5 4 2
上面的每个相同数字的矩形表示一个连续的矩形。 最大的矩形优先于也可以在其区域中形成的较小的矩形。 编号/矩形的顺序并不重要。
我目前的做法是迭代的。 在每一次迭代中，我都会build立一个最大的矩形列表，这个矩形可以从每个网格的可绘制单元格中通过从单元格的所有4个方向延伸而形成。 在sorting最大的列表之后，我首先find最大的矩形，将其底层单元标记为“绘图”，并将该矩形logging在列表中。 绘制每个矩形之前，检查其底层单元以确保它们尚未绘制（与上一个绘图重叠）。 然后，我们再次开始，find剩余的最大矩形，然后绘制它们，直到所有的单元格都被绘制为某个矩形的一部分。
我认为这种方法稍微比一个愚蠢的蛮力search优化，但我浪费了很多周期（重新）计算单元格最大的矩形和检查底层细胞的状态。
目前，这个矩形发现例程占据了工具总运行时间的大部分，特别是对于大型蓝图。 为了速度，我牺牲了一些准确性，只考虑来自单元格的矩形，这些单元看起来形成了一个矩形的angular落（使用一些邻居单元启发式来确定，这并不总是正确的）。 作为这个“优化”的结果，我目前的代码实际上并没有正确地产生上面的解决scheme，但它足够接近。
更广泛地说，我认为最大的矩形的目标 – 首先是对这个应用程序“足够好”的方法。 但是我观察到，如果目标是find矩形的最小集合 （最less数量）来完全覆盖多个区域，那么解决scheme将如下所示：
. 3 . 5 6 8 1 3 4 5 6 8 . 3 4 5 . 8 2 3 4 5 7 8 . 3 . 5 7 8
这个第二个目标实际上代表了一个更优化的问题解决scheme，因为更less的矩形通常意味着更less的命令发送到矮人堡垒。 然而，根据我有限的math知识，这种方法让我更接近NP-Hard。
如果您想更好地理解整体战略，请观看video ; 我没有提到Quickfort过程的其他方面，例如find绘制所有矩形的最短光标path。 这个问题可能有一个解决scheme来连贯地结合这些多种策略。
任何forms的帮助将不胜感激。
我find了一些快速algorithm来分割来自三元吴和Sartaj Sahni的简单直线多边形 ，这可能是你感兴趣的。 在你的例子中，带有字符“d”的区域形成了一个直线多边形，也是带有“c”和“。”的区域。 本文包括无孔简单直线多边形的algorithm。
如果一个多边形包含有孔，那么运行O（n ^ 3/2 log n）时间的algorithm，正如第11页的纸张多边形分解中的JM Keil所述。
如果最小化在分区过程中引入的线段的总长度是另一个优化标准 ，则如果多边形包含孔（第12页），则问题变为NP完全。 对于这些问题，存在近似algorithm（本文是指具有这种algorithm的论文）。 如果多边形不包含孔，则有一个O（n ^ 4）时间algorithm。
这不是一个真正的答案，但使用一个天真的search，你可以得到
. 1 . 2 3 3 4 1 5 2 3 3 . 1 5 2 . 6 7 1 5 2 8 6 . 1 . 2 8 6
基本上，你从左上angular开始，用它作为下一个矩形的左上angular，然后检查你可以向右和向下扩展多less，然后find剩余位的最上面和最左边的单元格，等等。
这在某些情况下可能是非常无效的，但速度很快，因为您不必重新计算任何东西。
在我看来，所有find覆盖原始区域的矩形的解决scheme都是正确的。 find更小的一组矩形更好，因为它压缩/执行更好。
所以我不build议试图find最佳的解决scheme。 （我想这也是NP难）。
对于更快的运行解决scheme，您可以将matrix初始化为4个单元组，并尝试合并它们（如果它们相同）。 之后，如果它们相同，则可以合并4个组的组。 如果你完成了recursion的话。
这不会find最佳的解决scheme，但会非常快。 如果你的matrix很大，有很大的连续区域，那么与最优化的差别就不会那么大。
