在2d块网格中查找矩形

2018-07-03 23:16:48

假设我有一个7x12的网格。我们使用颜色“*”，“％”，“@”和空单元格“ - ”。

1 2 3 4 5 6 7
- - - - - - -  1
- - - - - - -  2
% % - - - - -  3
% % - - - - *  4 
% % - - - @ %  5
@ @ @ - - @ %  6
@ @ * * * - *  7
* * * % % % %  8 
% @ @ % * * %  9
% @ % % % % %  10
* * * % % @ @  11
* * @ @ @ @ *  12

我想在这个特定最小尺寸的网格中找到矩形，并找到最大的矩形，然后再缩小，直到找不到大于或等于最小尺寸的矩形。

在这个例子中，考虑最小尺寸1x4,4x1,2x2，所以1x3无效，但是2x3是有效的。如果我们想要最大的矩形，我们会发现以下内容：

（4,8）4x1

（3,10）5x1

（1,3）处2x3

（6,1）处2x2

（1,11）的2x2

（3,12）4x1

请注意，矩形不能位于其他空间中，它们不能重叠。例如（4,10）处的2x2矩形未被提及，因为它将与（3,10）处的5x1矩形重叠。

所有的矩形都是完全有效的：它们相等或更大，以至于每个矩形的最小尺寸和所有块都具有相同的颜色。

我想要的是以编程方式做到这一点。当你告诉某人在网格中找到矩形时，他立即发现它们，没有任何想法。问题是，我怎么能写一个相同的算法？

我认为bruteforcing，但我需要的算法执行尽可能快，因为它需要在一个有限的（移动）设备上很短的时间内执行很多。

我在互联网上看到很多关于矩形的问题，但我很惊讶这个问题还没有问到任何地方。我是不是觉得太难了，或者从来没有人想过这样做？

分别调用输入数组W和H的宽度和高度。

对于W * H矩阵中的每个（x，y）位置记录，运行这个聪明的O（WH）算法来确定最大的矩形，而不是仅跟踪最大的矩形，而是（一个或全部）的宽度和高度左上角为（x，y）的最大矩形，随时更新这些值。

循环遍历该矩阵，将其中每个足够大的矩形添加到按区域排序的最大堆（宽度*高度）。

从这堆中读取条目; 他们将按照面积递减的顺序进行生产。读取左上角为（x，y）并且宽度为w和高度为h的每个条目，将矩形中包含的每个wh位置标记为WH位数组中的“used”。从堆中读取矩形时，我们必须丢弃任何包含“已用”正方形的矩形，以避免产生重叠的矩形。只检查每个候选矩形的四个边对“已使用”数组就足够了，因为候选矩形可以与另一个矩形重叠的唯一方式是如果后一个矩形完全被它包含，这是不可能的，这是由于事实上，我们正在按照面积递减的顺序读取矩形。

这种方法是“贪婪的”，因为如果有多种方法将纯色区域雕刻成最大的矩形，它不能保证选择最大的矩形序列。（例如，可能有几个矩形的左上角位于（10,10），其面积为16：16x1,8x2,4x4,2x8,1x16。在这种情况下，有一种选择可能产生更大的矩形“下游“，但我的算法并不保证做出这样的选择。）如果有必要，您可以使用回溯来找到这个总体最佳的一系列矩形，尽管我怀疑在最坏的情况下这可能非常缓慢。

我提到的最大矩形算法是为单色矩形设计的，但如果您无法将其应用于多色问题，则可以在开始步骤2之前为每种颜色运行一次。

我必须为我的第一人称射击者解决一个非常类似的问题。我在输入中使用它：
[] [] [] [] [] [] [] []
[ ][ ][ ][X][ ][ ][ ][ ]
[] [X] [X] [X] [X] [X] [X] [X]
[] [] [X] [X] [X] [X] [] []
[] [X] [X] [X] [X] [] [] []
[] [X] [X] [X] [X] [] [] []
[ ][ ][X][ ][ ][ ][ ][ ]
[] [] [] [] [] [] [] []

我在输出中得到：
[] [] [] [] [] [] [] []
[ ][ ][ ][一个][ ][ ][ ][ ]
[] [B] [G] [G] [G] [F] [E] [E]
[] [] [G] [G] [G] [F] [] []
[] [D] [G] [G] [G] [] [] []
[] [D] [G] [G] [G] [] [] []
[ ][ ][C][ ][ ][ ][ ][ ]
[] [] [] [] [] [] [] []

这个模式更好。源代码（在GNU通用公共许可证版本2下）在这里，它受到很多评论。您可能需要根据j_random_hacker建议的需要调整它。

注意：这是假设您正在尝试查找最大的k矩形。

我们知道我们必须在最坏的情况下至少查看一次网格中的每个节点。这意味着我们最糟糕的最坏情况是O(len*wid) 。

你的蛮力将会是O(len*len*wid*wid)用“在一个点上检查矩形为O(len*wid) ，并且你做O(len*wid)次的幼稚方法。

这可能是因为您发现情况并非如此，因为每次找到矩形时，都有可能减少问题空间。我觉得“检查每个矩形”的蛮力方法将是最好的方法。不过，有些事情可以加快速度。

基本算法：

for(x = 1 .. wid) {
    for(y = 1 .. len) {
        Rectangle rect = biggestRectOriginatingAt(x,y);
        // process this rectangle for being added
    }
}

跟踪最大的k矩形。随着您的前进，您可以搜索符合条件的矩形可能位于的边界。

Rectangle biggestRectOriginatingAt(x,y) {
    area = areaOf(smallestEligibleRectangle); // if we want the biggest k rect's, this
                                              // returns the area of the kth biggest
                                              // known rectangle thus far

    for(i = 1 .. area) {
        tempwid = i
        templen = area / i

        tempx = x + tempwid
        tempy = y + templen

        checkForRectangle(x,y,tempx,tempy); // does x,y --> tempx,tempy form a rectangle?
    }

}

这可以让您在大型搜索结束时获得巨大的性能提升（如果这是一项小型搜索，您获益不大，但您不在乎，因为它只是一个小搜索！）

对于更多随机分配，这也不起作用。

另一个优化是使用填充算法来查找最大的连续区域。这是O(len*wid) ，这是一个小的代价。这将允许您搜索大矩形的最可能区域。

请注意，这些方法都不能减少最坏的情况。但是，它们确实减少了现实世界预期的运行时间。

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

上一篇: Finding rectangles in a 2d block grid

下一篇: Find the set of largest contiguous rectangles to cover multiple areas