给定一个1000 x 1000的数组，其中包含各式各样的矩形。在<图1>中，以黄色单元格显示的序列“1”是矩形的模式。在<图1>中，矩形的最小尺寸为3x3，显示为绿色单元格。
矩形中应至少有一个“0”。
但是，在此数组中，还存在未闭合的形状或直线模式。
(数组的初始值为‘0’，形状用一系列‘1’表示。它们不重叠或相互包含。）
如何高效地找到除未闭合的形状或直线外的完整矩形的算法？例如，在上图中，完整矩形的数量为3。
寻找完整包含0的矩形
29
- Shruti Singh
5
我在那张图片上什么都看不到（尝试在IE和Opera中）。 - Damien_The_Unbeliever
其他非矩形封闭图形可能发生吗？ - Michał Górny
7其他形状可以存在吗？（例如任意连接点，T形等）有效矩形的内部必须全为零吗？可以在矩形内部放置其他矩形吗？ - Oliver Charlesworth
3输入数据中是否可能包含您不想找到的填充矩形（所有数字都是1）？部分矩形是否可以与有效矩形共用同一些单元格？ - Nate Kohl
有效矩形内部是否可以包含任何1？一个有效矩形是否可以位于另一个有效矩形内部？ - Muhd
5个回答
21
这很简单。如果你有n个正方形，你可以在O(n)时间内计算出矩形的数量。
假设：
- 每个有效矩形的边界不与非有效路径共享任何单元格。 - 如果一个矩形在另一个矩形内部，你将会找到它们。
你需要额外的内存，大小和输入一样大。让我们称之为visited，并初始化为0。
现在，我们先构建一个帮助函数：
这个函数基本上在右下左上的方向上追踪1，并检查是否满足条件（长度至少为3且到达起始位置）。它还标记了访问过的方块。
需要注意的重要事情是，该函数仅在初始方块为左上角时才能正确工作。
现在，问题的解决方案很容易：
这是算法的执行过程：
1. 失败（并标记）了一个糟糕的矩形部分。
2. 找到（并标记）了一个矩形。
3. 在单个正方形上失败（垂直线的一部分）。
4. 在单个正方形上失败（垂直线的一部分）。
5. 在单个正方形上失败（垂直线的一部分）。
6. 经过许多类似的步骤，找到了下一个矩形。
7. 然后是下一个矩形。
假设：
- 每个有效矩形的边界不与非有效路径共享任何单元格。 - 如果一个矩形在另一个矩形内部，你将会找到它们。
你需要额外的内存，大小和输入一样大。让我们称之为visited，并初始化为0。
现在，我们先构建一个帮助函数：
is_rectangle(square s)
from s, go right while you see 1s and visited is 0
mark them as 1 in visited
if less than 3 steps
return 0
then, go down while you see 1s and visited is 0
mark them as 1 in visited
if less than 3 steps
return 0
then, go left while you see 1s and visited is 0
mark them as 1 in visited
if less than 3 steps
return 0
then, go up while you see 1s and visited is 0
mark them as 1 in visited
if then one above is not s
return 0
return 1
这个函数基本上在右下左上的方向上追踪1，并检查是否满足条件（长度至少为3且到达起始位置）。它还标记了访问过的方块。
需要注意的重要事情是，该函数仅在初始方块为左上角时才能正确工作。
现在，问题的解决方案很容易：
num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
for c in columns
if visitied[r][c] or image[r][c] == 0
continue
num_rectangles += is_rectangle(<r,c>)
return num_rectangles
这是算法的执行过程：
1. 失败（并标记）了一个糟糕的矩形部分。
2. 找到（并标记）了一个矩形。
3. 在单个正方形上失败（垂直线的一部分）。
4. 在单个正方形上失败（垂直线的一部分）。
5. 在单个正方形上失败（垂直线的一部分）。
6. 经过许多类似的步骤，找到了下一个矩形。
7. 然后是下一个矩形。
8. 算法结束
- Shahbaz
8
我喜欢这个，但是根据输入的糟糕程度，当你意识到一个矩形只是部分完成时，你可能需要回去从已访问数组中删除它的单元。 - Nate Kohl
@NateKohl，恰恰相反！鉴于问题的条件，将它们保持为已访问状态有助于跳过未来的非矩形。 - Shahbaz
@NateKohl，好的，我明白你的意思了。我添加了一个假设，即您对问题的评论不会发生（因此矩形不与非矩形共享边界）。 - Shahbaz
如果矩形的顶部边界“超出”右侧边缘，那么这个算法将失败，尽管这是一个有效的输入，因为它相当于具有开始于紧靠矩形顶部边缘右侧的正方形的水平线段。可以设计O(n)算法来避免这种情况。 - j_random_hacker
@j_random_hacker，由于原贴作者对于我们是否存在这样的情况的问题没有回应，我在帖子最前面做了一个假设（我的首个假设）认为这种情况是不存在的。 - Shahbaz
显示剩余3条评论
4
下面这个O(n)算法适用于任何由0/1值组成的2D矩阵（即允许相交/重叠的矩形，以及任意非矩形的开放/封闭形状）。这里使用的矩形定义是“内部完全由0单元格组成”（因此，例如如果一个矩形完全包含另一个，则只会找到内部的矩形；如果应该考虑包含矩形，则可以删除每个找到的矩形并重新启动算法）。它基于以下观察结果：每个0单元格最多可以在一个1矩形的内部。
我使用的惯例是x = 0为最左侧位置，y = 0为最顶部位置。
我使用的惯例是x = 0为最左侧位置，y = 0为最顶部位置。
- 找到左上角。从左上角开始，按从左到右、从上到下的顺序查找下一个未访问的单元格，该单元格可能是实心0矩形的左上角：具体而言，它必须是一个0单元格，其在SW、W、NW、N和NE位置具有1个单元格邻居，在其余3个相邻位置具有0单元格。
- 找到右上角。扫描其右侧的邻居，同时这些单元格为0并且具有1个单元格N邻居。
- 这可以是实心0矩形的顶部行吗？如果上述循环结束前找到的最后一个单元格是实心0矩形中可能是右上角的单元格（具体而言，是一个0单元格，其在NW、N、NE、E和SE单元格中具有1个单元格邻居，在其余3个位置中具有0单元格），则我们已经确定了使用这些单元格中的任何一个的唯一可能的实心0矩形的顶部y坐标和确切宽度。如果最后一个单元格不符合这些右上角条件，则这些单元格都不能成为实心0矩形的一部分：将它们标记为已访问并转到1。
- 将0单元格条带的起始和结束x坐标称为x1和x2；将垂直位置y1称为垂直位置。
- 向下一行一行地扫描。设置y2 = y1，并在竖直位置y2处的x1和x2之间的线可能是实心0矩形的一部分时逐渐增加y2。具体而言，每个垂直位置y2的测试是：（x1-1，y2）和（x2 + 1，y2）处的单元格都必须为1，并且介于它们之间的所有单元格都必须为0。
- 这可以是实心0矩形的底部行吗？如果上一个循环找到的最后一行是实心0矩形的底部行（具体而言，从（x1-1，y2 + 1）到（x2 + 1，y2 + 1）有1个单元格），则我们已经找到了被1单元格包围的完整实心0矩形：如果其大小大于迄今为止发现的最大矩形，则记录为新的最大矩形。否则（如果下一行没有实心1单元格），则检查的所有0单元格都不能成为任何实心0矩形的一部分：将它们全部标记为已访问并转到1。
- j_random_hacker
3
如果你的数组只能包含矩形形状，那么它等价于在二进制图像上进行计算的经典问题：只需应用标准的连通组件算法。您只标记 0 的连通组件并对它们进行计数。
例如，请参见http://en.wikipedia.org/wiki/Connected-component_labeling。这种类型的算法在图像上很简单，但需要一定量的内存（与输入数组相同大小，类型为 short 或 int）。要注意连接性：如果选择 4 连通性，则将计算缺少某些角落的封闭矩形。但是该算法比 8 连通性更简单。
如果您的数组中包含更复杂的封闭形状，则只需添加后处理：对于每个连通组件，请计算组件边界框内部的像素数（如果两个数字相等，则表示您有一个矩形）。
例如，请参见http://en.wikipedia.org/wiki/Connected-component_labeling。这种类型的算法在图像上很简单，但需要一定量的内存（与输入数组相同大小，类型为 short 或 int）。要注意连接性：如果选择 4 连通性，则将计算缺少某些角落的封闭矩形。但是该算法比 8 连通性更简单。
如果您的数组中包含更复杂的封闭形状，则只需添加后处理：对于每个连通组件，请计算组件边界框内部的像素数（如果两个数字相等，则表示您有一个矩形）。
- Bentoy13
2
1+1，这个可以。但是“connexity”？发抖 请说“connectivity”（以及“label”而不是“labellize”）。 - j_random_hacker
当我阅读问题描述时，立刻想到了连通分量算法。 - Daniel Pryden
2
我思考了一段时间，想出了这种方法：
1）消除边缘周围的所有零 - 将它们的值更改为2
2）在2周围填充矩阵
这样只留下了零的岛屿，现在可以测试其凸性。 因此，对于每个岛屿：
3）查找X和Y中0值的范围 - 给您一个潜在的内部矩形
4）如果内部矩形包含1或外部矩形包含0，则将该岛屿填充为2，因为它不是凸形（因此不是矩形）
假设您可以找到一个好的洪水填充算法（不像我的），这应该可以快速地缩小搜索空间。
现在来看代码（抱歉它是C#）：
using System;
using System.Collections.Generic;
namespace Test
{
class MainClass
{
static private int [,] matrix = new int[,] {
{0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
{0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,1,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
{0,1,0,0,0,0,1,0,1,0,0,0,0,1,0},
{0,1,1,1,1,1,1,0,1,0,0,1,0,1,0},
{0,0,0,0,0,0,0,0,1,1,1,1,0,0,0},
{0,0,1,1,1,1,0,0,0,0,0,0,0,0,0},
{0,0,1,0,0,1,0,0,1,1,1,0,1,1,0},
{0,0,1,1,1,1,0,0,1,0,1,0,0,0,0},
{0,0,0,0,0,0,0,0,1,1,1,0,0,0,0}
};
static private int width = matrix.GetLength(0);
static private int height = matrix.GetLength(1);
private const int DEAD = 2;
private const int RECT = 3;
public static void Main (string[] args)
{
//width = matrix.GetLength(0);
//height = matrix.GetLength(1);
PrintMatrix ();
EliminateFromEdges (DEAD);
PrintMatrix ();
FloodFill (DEAD); // very inefficient - find a better floodfill algorithm
PrintMatrix ();
// test each island of zeros for convexness
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
if (matrix[i,j] == 0)
{
if (TestIsland(i,j) == false)
{
// eliminate this island as it is not convex
matrix[i,j] = DEAD;
FloodFill(DEAD);
PrintMatrix ();
}
else
{
// flag this rectangle as such
matrix[i,j] = RECT;
FloodFill(RECT);
PrintMatrix ();
}
}
}
}
// We're done, anything flagged as RECT can be expanded to yield the rectangles
PrintMatrix ();
}
// flag any zero at edge of matrix as 'dead'
static private void EliminateFromEdges(int value)
{
for (int i = 0; i < width; i++)
{
if (matrix [i, 0] == 0)
{
matrix [i, 0] = value;
}
if (matrix [i, height - 1] == 0)
{
matrix [i, height - 1] = value;
}
}
for (int j = 1; j < height - 1; j++)
{
if (matrix [0, j] == 0)
{
matrix [0, j] = value;
}
if (matrix [width - 1, j] == 0)
{
matrix [width - 1, j] = value;
}
}
}
// propagte a value to neighbouring cells
static private void FloodFill (int value)
{
bool change_made = true; // set to true to start things off
while (change_made) {
change_made = false;
for (int i = 1; i < width - 1; i++) {
for (int j = 1; j < height - 1; j++) {
if ((matrix [i, j] == 0) &&
((matrix [i - 1, j] == value) ||
(matrix [i + 1, j] == value) ||
(matrix [i, j - 1] == value) ||
(matrix [i, j + 1] == value))) {
matrix [i, j] = value;
change_made = true;
}
}
}
}
}
static private bool TestIsland (int x, int y)
{
// find convex extend of island
int x2 = x;
int y2 = y;
while (matrix[++x2, y] == 0);
x2--;
while (matrix[x,++y2] == 0);
y2--;
// check inner cells (want all zeroes)
for (int i = x; i <= x2; i++)
{
for (int j = y; j <= y2; j++)
{
if (matrix[i,y] != 0)
{
return false;
}
}
}
// check surrounding cells (want all ones)
x--; y--;
x2++; y2++;
for (int i = x; i <= x2; i++)
{
if ((matrix[i,y] != 1) || (matrix[i,y2] != 1))
{
return false;
}
}
for (int j = y + 1; j <= y2 - 1; j++)
{
if ((matrix[x,j] != 1) || (matrix[x2,j] != 1))
{
return false;
}
}
return true;
}
// for debug purposes
static private void PrintMatrix ()
{
for (int i = 0; i < width; i++) {
for (int j = 0; j < height; j++) {
switch(matrix[i,j])
{
case DEAD:
Console.Write("-");
break;
case RECT:
Console.Write("+");
break;
default:
Console.Write(matrix[i,j]);
break;
}
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
这段代码的输出结果是：
000000001111000
011111101001010
010000101001010
010000101001010
010000101000010
010000101000010
011111101001010
000000001111000
001111000000000
001001001110110
001111001010000
000000001110000
--------1111---
-1111110100101-
-1000010100101-
-1000010100101-
-1000010100001-
-1000010100001-
-1111110100101-
-0000000111100-
-0111100000000-
-0100100111011-
-0111100101000-
--------111----
--------1111---
-111111-1--1-1-
-100001-1--1-1-
-100001-1--1-1-
-100001-1----1-
-100001-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1001--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--101----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----
--------1111---
-111111-1--1-1-
-1++++1-1--1-1-
-1++++1-1--1-1-
-1++++1-1----1-
-1++++1-1----1-
-111111-1--1-1-
--------1111---
--1111---------
--1++1--111-11-
--1111--1+1----
--------111----
- zeFrenchy
3
“在X和Y方向上至少相隔2个单元格内找到另一个1”？它可以是任何单元格，而高效地找到正确的单元格才是问题的关键！ - j_random_hacker
我并没有说随机选择另一个1！你需要按行、列的顺序寻找候选项。由于你知道矩形内不可能有1，因此可以显著减少搜索空间。每个失败的候选项1都允许你跳过该行的其余部分。此外，如果S2>0，则可以在主循环中继续移动到下一个单元格。 - zeFrenchy
我认为这可能会更简单。您可以使用“1”填充数组。这样，剩余的“0”就标记了所需的区域。在后处理中，您只需将边框增加1即可获得原始形状。 - jnovacho
0
这是我认为的，可能会非常资源浪费。不太确定。
- 沿着一行遍历，除非找到至少3个
1。 - 向下遍历并与下面的行进行
boolean& 操作-->如果它是一个有效的矩形，则应该以100..001的格式呈现。(假设您可以执行所有的boolean操作) - 当您在步骤2中找到至少一行，并最终找到所有的
1时，您已经找到了一个矩形。 - 重复使用下一行的元素！
- gaganbm
4
为什么要使用布尔AND？为什么不只是将每一行与“100..001”进行比较？另外，如果有一个水平线段延伸到矩形顶部边缘的左侧，会怎样？ - j_random_hacker
@j_random_hacker 是的，也可以进行比较。反正都是同样的事情。而且我之前还假设没有“扩展”这种东西。 - gaganbm
“扩展”相当于一个水平线段，从矩形顶部边缘的右侧开始，根据我所知，这是符合OP的限制条件的。 - j_random_hacker
@j_random_hacker 嗯。明白你的意思。在这种情况下，我们需要更多的检查点和约束条件。 - gaganbm
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接