在查找二维数组最大的矩形 [英] Finding largest rectangle in 2D array

问题描述

我需要一个算法，它可以分析一个二维数组，并返回最大的连续矩形。作为参考，看看我做了演示我的问题的形象。

I need an algorithm which can parse a 2D array and return the largest continuous rectangle. For reference, look at the image I made demonstrating my question.

推荐答案

通常你解决使用什么是所谓的这些各种各样的问题的扫描线算法的。他们研究同时建立你正在寻找的答案一行数据（或扫描线的），你的情况候选矩形。

Generally you solve these sorts of problems using what are called scan line algorithms. They examine the data one row (or scan line) at a time building up the answer you are looking for, in your case candidate rectangles.

下面是它如何工作的一个大致的轮廓。

Here's a rough outline of how it would work.

所有号码从0..6图像行，我会从下往上工作。

Number all the rows in your image from 0..6, I'll work from the bottom up.

检查行0你有两个长方形的开始（我假设你只在黑色的方形兴趣）。我指的是使用（X，Y，宽，高）的矩形。两种活性矩形是（1,0,2,1）和（4,0,6,1）。添加这些到活动矩形列表。这个名单是通过增加x坐标排序。

Examining row 0 you have the beginnings of two rectangles (I am assuming you are only interested in the black square). I'll refer to rectangles using (x, y, width, height). The two active rectangles are (1,0,2,1) and (4,0,6,1). You add these to a list of active rectangles. This list is sorted by increasing x coordinate.

您现在有扫描线0完成的，所以你增加你的扫描线。

You are now done with scan line 0, so you increment your scan line.

检查第1行你沿着行看到的工作，如果您有任何以下内容：

Examining row 1 you work along the row seeing if you have any of the following:

• 新的活动矩形


• 为现有的矩形成长空间


• 其中拆分现有的矩形障碍


• 这需要你的障碍从活动列表中删除一个矩形

当你沿着该行工作，你会发现你有一个新的活动矩形（0,1,8,1），我们可以拓展现有活跃的之一（1,0,2,2），我们需要用两条窄的人清除活性（4,0,6,1）替换它。我们需要记住这一点。这是我们目前所看到的迄今为止最大的。它被替换为两个新的积极的：（4,0,4,2）和（9,0,1,2）

As you work along the row you will see that you have a new active rect (0,1,8,1), we can grow one of existing active ones to (1,0,2,2) and we need to remove the active (4,0,6,1) replacing it with two narrower ones. We need to remember this one. It is the largest we have seen to far. It is replaced with two new active ones: (4,0,4,2) and (9,0,1,2)

因此​​，在扫描线1的发送，我们有：

So at the send of scan line 1 we have:

• 活动列表：（0,1,8,1），（1,0,2,2），（4,0,4,2），（9,0，1,2）


• 最大迄今：（4,0,6,1）

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

You continue in this manner until you run out of scan lines.

棘手的部分是编码了沿扫描线更新活动列表运行程序。如果你这样做正确，您会考虑每个像素只有一次。

The tricky part is coding up the routine that runs along the scan line updating the active list. If you do it correctly you will consider each pixel only once.

希望这有助于。这是一个有点棘手来形容。

Hope this helps. It is a little tricky to describe.

这篇关于在查找二维数组最大的矩形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！