在二维数组中寻找最大矩形

Question

在二维数组中寻找最大矩形

c++arraysparsing

6

我需要一个算法，可以解析2D数组并返回最大连续矩形。请参考我制作的演示图像。

- Johnathan

需要是正方形吗？还是只需要矩形？ - Jon Egeland

我的错，我想说的是矩形。谢谢你告诉我，我已经修复了它。我只是不确定如何实现这样的算法。 - Johnathan

1

C++与这个问题无关。这更是一个关于算法的问题。另外，你能发一下你已经想出来的东西吗？ - Merlyn Morgan-Graham

我现在没有什么。我只是在想而已。我想知道这个特定的算法是否有一个名称或其他什么东西。 - Johnathan

1

解析一个二维数组，它的数据结构是什么？ - ildjarn

4个回答

5

我认为一种区域生长的方法是很好的选择。

对于数组中的每个开放点
向东扩展，直到不能再扩展为止
向西扩展，直到不能再扩展为止
通过添加行向北扩展，直到不能再扩展为止
通过添加行向南扩展，直到不能再扩展为止
保存使用的种子像素的结果区域
循环遍历数组中的每个点之后，选择具有最大面积结果的种子像素

这可能是一种彻底但不是最有效的方法。

我想你需要回答哲学问题“一串点是一个细长的矩形吗？”如果一条线==一个瘦矩形，你可以进一步优化：

创建一个名为LINES的整数数组，其尺寸与ARRAY相同
循环遍历数组中的每个点
确定从每个点开始向东的最长有效线，并将其长度保存在LINES的相应单元格中。
对于ARRAY中的每个点都执行此操作后，循环遍历LINES
对于LINES中的每个点，确定有多少个南方邻居具有相同的长度值或更小的长度值。
如果这样做可以增加矩形的面积，则接受一个长度较小的南邻居。
使用该种子点的最大矩形为（可接受的南邻居数*最长接受线的长度）
计算每个种子的最大矩形面积时，请检查是否有新的最大值，并在确实存在时保存结果。
你也可以不分配LINES数组来完成此操作，但我认为在我的解释中使用它会使描述更简单。
而且...我认为您需要使用VERTICAL_LINES和EASTERN_NEIGHBORS执行相同类型的操作，否则某些情况可能会错过高而瘦的大矩形。因此，也许这个第二个算法并没有那么优化。

使用第一种方法检查你的工作。我想Knuth说过“过早地优化是万恶之源。”

希望对你有所帮助，

Perry

附言：经过几次编辑，我认为这个答案值得一起投票。

- Perry Horwich

很高兴为您效劳。我喜欢这种事情。我已经编辑了我的答案，包括我认为可能更有效的“第二步”。 - Perry Horwich

@Maxpm，我认为同时向两个方向增长正方形可能并不总能找到最大的矩形。 - Perry Horwich

1

你第二个算法的问题在于你需要一个 <= 检查，而不是一个 == 检查。否则，你将会错过很多可能的矩形，包括可能是最大的矩形。此外，你仍然会重复做一些上下移动的工作。如果你删除组合后的元素，就可以避免这种情况（尽管使用 <= 检查，这会破坏一些情况）。一旦你开始尝试优化它，这个问题可能会变得非常复杂 :) - Merlyn Morgan-Graham

1

这个算法是次优的。例如：在给定的样本图像中，取最靠近右下角的正方形并将其全部移动到左侧。现在，最优矩形不会向东西方向延伸到任何成员行中最大的线条那么远。 - Ben Voigt

1

@Perry：这是我指的图片。最优矩形是7x3。我认为你的算法只能找到一个4x5。 - Ben Voigt

显示剩余5条评论

2

一种直接的方法是遍历网格中所有可能的矩形，计算它们的面积，如果面积大于当前最大面积，则选择它作为最高面积：

var biggestFound
for each potential rectangle:
    if area(this potential rectangle) > area(biggestFound)
        biggestFound = this potential rectangle

然后你只需要找到可能的矩形。

for each square in grid:
    recursive loop 1:
        if not occupied:
            grow right until occupied, and return a rectangle
            grow down one and recurse (call loop 1)

这将会重复很多工作（例如，您将重新评估许多子矩形），但它应该会给您一个答案。编辑另一种方法可能是从一个大小为网格的单一正方形开始，“减去”占用的正方形，最终得到一组潜在的矩形。在此过程中，使用四叉树（quadtrees）进行优化，确保保持分割的矩形“有序”，从上到下，从左到右，以防需要在算法中进一步重新组合矩形。

如果您实际上是从矩形数据（对于您的“填充网格”集）开始的，而不是从松散的像素网格开始，则可以轻松地通过矩形/区域减法算法获得更好的性能。

我不会为此发布伪代码，因为这个想法完全是实验性的，我不知道对于松散像素网格，性能是否会更好 ;)

Windows系统的“区域”和“脏矩形”，以及一般的“时间缓存”，可能会为提高效率提供良好的灵感。如果这是用于图形算法，还有很多z缓冲技巧...

- Merlyn Morgan-Graham

有没有比循环遍历每个可能性更有效的计算方法，还是这是唯一的方法？ - Johnathan

我相信有更有效的方法来计算潜在的矩形。我只是试图给你一个能够工作的解决方案，因为你没有规定性能要求或你已经完成了什么。此外，在你担心更聪明的解决方案中的错误之前，编写一个显然正确的解决方案通常是很有用的。 - Merlyn Morgan-Graham

谢谢你的帮助，我很感激。抱歉我没有表达清楚。 - Johnathan

@user422382：没问题。现在有很多学生发布作业问题，但是没有展示他们的工作，基本上是在请求别人替他们完成作业 :) 我想一个高层次的通用答案已经足够提示了，如果这恰好是情况的话。 - Merlyn Morgan-Graham

幸运的是，这只是我正在进行的一个业余项目。再次感谢您让我知道，我会更加小心知道这一点;-) - Johnathan

哦，最终我只会编写出能够工作的代码，并将其保留，直到发现它占用了过多的CPU时间/内存为止 :) 这样可以让您更快地进入程序的其他部分，并使其更加有趣。 - Merlyn Morgan-Graham

1

使用动态规划方法。考虑一个函数S(x,y)，它表示(x,y)为矩形的最低右下角单元格时，最大矩形的面积；x是矩形的行坐标，y是列坐标。

例如，在您的图中，S(1,1)=1，S(1,2)=2，S(2,1)=2，S(2,2)=4。但是，S(3,1)=0，因为此单元格已被填充。S(8,5)=40，这意味着以(8,5)为最低右下角单元格的最大矩形的面积为40，这恰好是此示例中的最优解。

您可以从S(x-1,y)，S(x,y-1)和S(x-1,y-1)的值轻松编写动态规划方程式S(x,y)。使用此方法，您可以在O(mn)时间内获得所有S(x,y)的值，其中m和n是给定表格的行和列维度。一旦对于所有1≤x≤m和所有1≤y≤n都已知S(x,y)，我们只需找到使S(x,y)最大的x和y; 这一步也需要O(mn)时间。通过保留其他数据，您还可以找到最大矩形的边长。

总体复杂度为O(mn)。要了解更多信息，请阅读第15章或Cormen算法书的第15.4节。

- Hasan

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- idz · Accepted Answer

通常使用所谓的扫描线算法来解决这类问题。它们逐行（或扫描线）检查数据，以构建您要查找的答案，例如候选矩形。

以下是其大致工作原理：

将图像中的所有行从0..6编号，我将从下往上处理。

检查第0行，您有两个矩形的开头（假设您只关心黑色正方形）。我会使用(x、y、width、height)表示矩形。这两个活动矩形分别为(1,0,2,1)和(4,0,6,1)。将它们添加到活动矩形列表中。该列表按递增的x坐标排序。

现在已完成扫描线0，因此您要增加扫描线计数。

检查第1行，沿着该行工作，看看是否有以下情况：

新的活动矩形
现有矩形可以增长的空间
分割现有矩形的障碍物
需要从活动列表中移除一个矩形的障碍物

沿着该行工作时，您会发现有一个新的活动矩形(0,1,8,1)，我们可以将现有的一个活动矩形扩展为(1,0,2,2)，并且需要用两个更窄的矩形代替活动矩形(4,0,6,1)。我们需要记住这个矩形，因为它是迄今为止最大的矩形。它被替换为两个新的活动矩形：(4,0,4,2)和(9,0,1,2)。

因此在第1次扫描结束后，我们有：

活动列表：(0,1,8,1)、(1,0,2,2)、(4,0,4,2)、(9,0,1,2)
迄今为止最大的矩形：(4,0,6,1)

你需要按照扫描线的方式继续处理，直到扫描线全部完成。

关键在于编写沿着扫描线运行并更新活动列表的程序。如果正确编写，则每个像素只会被考虑一次。

希望这可以帮助你，但描述有些棘手。