Find the set of largest contiguous rectangles to cover multiple areas
This question already has an answer here:
I found the paper Fast Algorithms To Partition Simple Rectilinear Polygons from San-Yuan Wu and Sartaj Sahni, which could be of interest to you. In your example the region with character 'd' forms a rectilinear polygon, also the regions with 'c' and '.'. This paper includes algorithms for hole-free simple rectilinear polygons.
If a polygon includes holes, there are algorithms running with O(n^3/2 log n) time, as JM Keil in the paper Polygon Decomposition on page 11 states.
If minimizing the total length of the line segments introduced in the partitioning process is the other optimization criterion, the problem becomes NP-complete if the polygon contains holes (page 12). For these problems approximation algorithms exist (the paper refers to papers with such algorithms). If the polygon doesn't contain holes there is an O(n^4) time algorithm.
This is not really an answer but using a naive search you can get
. 1 . 2 3 3
4 1 5 2 3 3
. 1 5 2 . 6
7 1 5 2 8 6
. 1 . 2 8 6
Basically you start from the top left corner and use it as the top left corner of your next rectangle, then you check how far you can extend it to the right and down, then find the topmost and leftmost cell of the remaining bits and so on.
This is probably very ineffective in some cases but it's quick as you don't have to recalculate anything..
您可以尝试简化http://www.montefiore.ulg.ac.be/~pierard/rectangles/上指出的算法给出的一组最大矩形
链接地址: http://www.djcxy.com/p/94606.html上一篇: 在2d块网格中查找矩形
下一篇: 找到覆盖多个区域的一组最大的连续矩形