我需要一个算法,它可以解析2D数组并返回最大的连续矩形.作为参考,请看我演示我的问题的图像.
解决方法
通常,您使用所谓的扫描线算法来解决这些问题.在您的案例候选矩形中,他们一次检查一行(或扫描线)的数据,构建您正在寻找的答案.
这是一个如何工作的大致轮廓.
将图像中的所有行编号为0..6,我将从下往上工作.
检查第0行,你有两个矩形的开头(我假设你只对黑色方块感兴趣).我将使用(x,y,width,height)来引用矩形.两个活动矩形是(1,2,1)和(4,6,1).您将这些添加到活动矩形列表中.此列表按增加x坐标排序.
您现在已完成扫描线0,因此您可以增加扫描线.
检查第1行,您将看到行是否有以下任何一项：
>新的活动矩形
>现有矩形生长的空间
>分裂现有矩形的障碍物
>障碍物,要求您从活动列表中删除矩形
当您沿着该行工作时,您将看到您有一个新的活动矩形(0,1,8,1),我们可以将现有的一个活动矩阵增长到(1,2),我们需要删除有效(4,1)用两个较窄的替换它.我们需要记住这个.这是我们迄今为止看到的最大规模.它被两个新的活动替换：(4,4,2)和(9,2)
因此,在发送扫描线1时,我们有：
>活动清单：(0,(1,(4,(9,2)
>目前为止最大：(4,1)
您将继续这种方式,直到扫描线用完为止.
棘手的部分是编写沿扫描线运行的例程来更新活动列表.如果你做得正确,你只会考虑每个像素一次.
希望这可以帮助.描述有点棘手.
