c - 查找包含 0 的完整矩形

Question

在给定的 1000 x 1000 阵列中有不同的矩形。中<Figure 1>，显示为黄色单元格的序列“1”为矩形图案。矩形的最小尺寸<Figure 1>为 3 x 3，显示为绿色单元格。

矩形内应该至少有一个“0”。

但是，在这个阵列中，也存在不封闭的形状或直线图案。

（数组的初始值为'0'，模式由一系列'1'表示。它们不重叠或相互包含。）

除了未闭合的形状或直线之外，找到数组中完整矩形的有效算法是什么？例如上图中完整矩形的数量为 3

Answer 1

这很简单。如果你有n正方形，你可以计算O(n).

假设：

• 每个有效矩形的边框不与无效路径共享任何单元格。
• 如果一个矩形在另一个矩形内，您会很高兴找到它们

您将需要与输入一样大的额外内存。让我们调用它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.算法结束

Answer 2

以下 O(n) 算法适用于任何 0/1 值的 2D 矩阵（即，允许相交/重叠的矩形，任意非矩形开放/闭合形状也是如此）。我在这里使用的矩形的定义是“内部完全由 0 个单元组成”（例如，如果一个矩形完全包含另一个矩形，则只会找到内部矩形；如果还应考虑包含矩形，则可以删除每个找到的矩形并重新启动算法）。这是基于观察到每个 0-cell 最多可以在一个 1-rectangle的内部。

我使用约定 x = 0 是最左边的位置，y = 0 是最上面的位置。

1. 找到左上角。 从左上角的单元格开始，从左到右和从上到下，找到下一个未访问的单元格，它可能是一个实心 0 矩形的左上角：特别是它必须是一个 0 单元格在 SW、W、NW、N 和 NE 位置有 1 个单元格邻居，在其余 3 个相邻位置有 0 个单元格。
2. 找到右上角。 当这些单元格为 0 并且有一个单元格为 N 的邻居时，扫描其右侧的邻居。
3. 这可能是实心 0 矩形的顶行吗？ 如果上述循环在结束之前找到的最后一个单元格是一个单元格，该单元格可能是一个实心 0 矩形中的右上角单元格（特别是在 NW、N、NE、E 中具有 1 个单元格邻居的 0 单元格）和 SE 单元格，以及其余 3 个位置的 0 单元格），那么我们已经建立了顶部 y 坐标和使用这些单元格中的任何一个的唯一可能的实心 0 矩形的确切宽度。如果最后一个单元格不满足这些右上角的条件，则这些单元格都不能成为实心 0 矩形的一部分：将它们标记为已访问并转到 1。
4. 调用 0 单元格 x1 和 x2 条带的起点和终点 x 坐标；调用垂直位置 y1。
5. 向下扫描，一次一行。 设置 y2 = y1，虽然 x1 和 x2 之间在垂直位置 y2 处的线可能是实心 0 矩形的一部分，但增加 y2。具体来说，在每个垂直位置 y2 的测试是：(x1 - 1, y2) 和 (x2 + 1, y2) 处的单元格必须都为 1，并且其间的所有单元格必须为 0。
6. 这可能是实心 0 矩形的底行吗？ 如果上一个循环在它结束之前找到的最后一行是可能是实心 0-矩形的底行的行（具体来说，从 (x1 - 1, y2 + 1) 到 (x2) 一直有 1 个单元格+ 1, y2 + 1))，则我们找到了一个完整的实心 0 矩形，被 1 格包围：如果它的大小大于目前发现的最大矩形，则将其记录为新的最大矩形。否则（如果在下一行中没有实心行 1 单元格），则检查的 0 单元格都不能成为任何实心 0 矩形的一部分：将它们全部标记为已访问并转到 1。

Answer 3

如果你的数组中只能有矩形，这相当于一个经典的二进制图像计算问题：只需对连通分量应用标准算法。您只标记 0 的连通分量，并计算它们。

例如，参见http://en.wikipedia.org/wiki/Connected-component_labeling 。这种类型的算法在图像上非常简单，但会占用一些内存（与输入数组大小相同，类型为 short 或 int）。注意连通性：如果您选择 4 连通性，即使缺少某些角，您也会计算封闭的矩形。但该算法比 8 连接更简单。

如果你可以有更复杂的封闭形状，只需添加一个后处理：对于每个连接的组件，计算组件边界框内的像素数（如果两个数字相等，你就有一个矩形）

Answer 4

想了一会儿。我想出了这个方法：

1）消除边缘周围的所有零 - 将它们的值更改为2

2）在2s左右填充矩阵

这只剩下零岛，现在可以测试凸度。所以对于每个岛屿：

3) 在 X 和 Y 中寻找 0 值的范围 - 给你一个潜在的内部矩形

4) 如果内部矩形包含 1 或外部矩形包含 0，则用 2s 填充这个岛，因为它不是凸的（因此不是矩形）

假设您可以找到一个好的洪水填充算法（不像我的那样），这应该可以有效地快速切割搜索空间。

现在是代码（对不起，它是升 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----

Answer 5

这就是我的想法，可能资源效率很低。不知道那件事。

1. 沿着一行遍历，除非你找到至少 31秒。
2. 向下遍历并使用下面的行执行& 操作 -->如果它是一个有效的矩形boolean，它们的格式应该是这样的。100..001（假设你可以做所有的boolean操作）
3. 当您在步骤 2 中找到至少一行时，您已经找到了一个矩形，最后是所有1s。
4. 对行的下一个元素重复！