找到覆盖多个区域的一组最大的连续矩形

2018-07-03 23:15:45

这个问题在这里已经有了答案：

用于找到最少矩形的算法，以覆盖一组没有重叠2个答案的矩形

我找到了一篇快速算法来分割来自San-Yuan Wu和Sartaj Sahni的简单直线多边形，这些内容可能会对您有所帮助。在你的例子中，带有字符'd'的区域形成了一个直线多边形，也是带有'c'和'。'的区域。本文包括无孔简单直线多边形的算法。

如果一个多边形包含孔，那么运行O（n ^ 3/2 log n）时间的算法，正如第11页纸张多边形分解中的JM Keil所述。

如果最小化分区过程中引入的线段的总长度是另一个优化标准，那么如果多边形包含孔（第12页），问题将变为NP完全。对于这些问题，存在近似算法（本文引用具有这种算法的论文）。如果多边形不包含孔，则有一个O（n ^ 4）时间算法。

这不是一个真正的答案，但使用一个天真的搜索，你可以得到

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

基本上你从左上角开始，将它用作下一个矩形的左上角，然后检查你可以将它向右和向下扩展多少，然后找到其余位的最上面和最左边的单元格，等等。

这在某些情况下可能非常无效，但它很快，因为您不必重新计算任何内容。

您可以尝试简化http://www.montefiore.ulg.ac.be/~pierard/rectangles/上指出的算法给出的一组最大矩形

链接地址: http://www.djcxy.com/p/94605.html