c++ - 查找二维数组中的最大矩形

Question

我需要一种可以解析二维数组并返回最大的连续矩形的算法。作为引用，请查看我制作的演示我的问题的图片。

Answer 1

通常，您使用所谓的扫描线算法 来解决这类问题。他们一次检查一行(或扫描线)的数据，以建立您正在寻找的答案，在您的情况下为候选矩形。

这是它如何工作的粗略概述。

从 0..6 开始对图像中的所有行进行编号，我将从下到上进行处理。

检查第 0 行，您有两个矩形的开头(我假设您只对黑色方 block 感兴趣)。我将使用 (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)

以这种方式继续，直到用完扫描线。

棘手的部分是编写沿扫描线运行更新事件列表的例程。如果操作正确，您将只考虑每个像素一次。

希望这对您有所帮助。描述起来有点棘手。