在C#中寻找封闭形状

Question

假设您有一个正方形网格，其中每个网格项都是“填充”或“未填充”的，是否有一种好的算法可以检测出网格中的任何“实心”形状？

下面的图像显示了我要完成的示例。该图像显示了一个封闭形状，以及两个具有空洞的潜在形状。还请注意，形状不一定是简单的正方形或矩形，虽然直接对角线不应存在。

• 红色方块表示“填充”方块。
• 蓝色方块代表封闭形状的内部区域。
• 白色方块为未填充。

我的问题是 - 是否有一种算法（可以由完全不懂数学的人遵循！并希望有C＃实现），可以检测此网格中的单个封闭形状（如果存在多个形状），包括返回形状内部的实际方块？

我迄今为止的思考仅涉及使用线性泛洪，但那似乎并不适合，例如没有单个源点，而必须扫描整个网格以查找可填充的形状。

- Richard Moss

---

我相信你需要确定至少一个在形状之外的像素，否则在某些情况下会有两个可能的解决方案（例如，如果你在图画中间画一条垂直线会发生什么？）。但是一旦你有了这个肯定在外面的像素，那么你就可以填充图画外部，剩下未填充的部分就是封闭的形状。 - vgru

为了避免过于宽泛的问题，需要您提供一些关于您已经尝试过什么以及遇到了什么问题的信息。不允许简单地在表格中发布“区域X是否有教程”的问题。 - sara

你也可以查看这个主题，它使用opencv，但你可能可以使用一个C#封装器或opencv端口。 - vgru

@Groo 在我发布这个问题之前，我扫描了一下 Stack Overflow，并阅读了一些类似的问题，其中包括 Python 的一个。虽然我考虑了 opencv 这个选项，但最终放弃了，因为它使用了其他库，而我最好是用原生的库。不过还是谢谢你！ - Richard Moss

@Groo，我使用了一个简单的泛洪填充算法编写了一个快速控制台应用程序，但是遵循了您的建议，从外部点扫描（并假设该点永远不可能在内部，这并不是我最初开始的假设，可能是导致发布此问题的错误！）初始测试看起来很有前途。如果您希望将您的评论转换为答案，我会很高兴对其进行标记。 - Richard Moss

Answer 1

感谢@Groo的评论，我意识到我已经有了正确的思路，那就是使用泛洪填充。但是，我一直在考虑如何扫描形状内部以找到边界，这就是我错了的地方。Groo建议始终应该有一个外部点，并从那里开始扫描。

我使用一个简单的二维布尔数组编写了一个非常基本的测试程序（并复制粘贴了一个相当容易阅读的泛洪算法），这似乎很好地工作。我将这个简单的代码发布为答案，以便帮助像我一样困惑的人，并防止添加另一个措辞不清的“问题”。

  class Program
  {
    static void Main(string[] args)
    {
      bool[,] grid;
      int width;
      int height;

      Console.Title = "Floodfill Shape Test";

      /*
       * This is a simple test program to detect filled shapes by performing a flood fill
       * to convert all empty space to solid - unless the empty space is already surrounded
       * by solid cells
       *
       * In order to this to work, the assumption is made that the boundaries of the grid
       * can never be solid before the flood fill is executed
       */

      width = 12;
      height = 10;
      grid = new bool[width, height];

      // add a sample enclosed shape
      grid[1, 1] = true;
      grid[2, 1] = true;
      grid[3, 1] = true;
      grid[1, 2] = true;
      grid[3, 2] = true;
      grid[1, 3] = true;
      grid[2, 3] = true;
      grid[3, 3] = true;

      // another enclosed shape
      grid[7, 1] = true;
      grid[8, 1] = true;
      grid[9, 1] = true;
      grid[10, 1] = true;
      grid[7, 2] = true;
      grid[10, 2] = true;
      grid[7, 3] = true;
      grid[8, 3] = true;
      grid[10, 3] = true;
      grid[8, 4] = true;
      grid[10, 4] = true;
      grid[8, 5] = true;
      grid[9, 5] = true;
      grid[10, 5] = true;

      // this shape has a hole in it
      grid[1, 5] = true;
      grid[2, 5] = true;
      grid[3, 5] = true;
      grid[1, 6] = true;
      grid[3, 6] = true;
      grid[1, 7] = true;
      grid[3, 7] = true;

      // a line right down the middle for the edge case
      // Remember that the boundaries can never be filled
      // or this house of cards will fall
      for (int i = 1; i < height - 1; i++)
      {
        grid[5, i] = true;
      }

      // display the original grid
      PrintGrid(grid, width, height);

      // run a basic flood-fill algorithm to mark as "solid" anything not already surrounded by solid borders
      FloodFill(grid, width, height);

      // display the modified grid
      PrintGrid(grid, width, height);

      if (Debugger.IsAttached)
      {
        Console.WriteLine("(Press any key to exit)");
        Console.ReadKey(true);
      }
    }

    private static void PrintGrid(bool[,] grid, int width, int height)
    {
      // print out the results
      // # - solid
      // . - empty
      // X - disallowed
      for (int row = 0; row < height; row++)
      {
        for (int col = 0; col < width; col++)
        {
          char c;

          if (row == 0 || row == height - 1 || col == 0 || col == width - 1)
          {
            c = 'X';
          }
          else {
            c = grid[col, row] ? '#' : '.';
          }

          Console.Write(c);
        }

        Console.WriteLine();
      }

      Console.WriteLine();
    }

    static void FloodFill(bool[,] grid, int width, int height)
    {
      // Taken from http://rosettacode.org/wiki/Bitmap/Flood_fill#C.23
      Queue<Point> q = new Queue<Point>();
      q.Enqueue(Point.Empty);
      while (q.Count > 0)
      {
        Point n = q.Dequeue();
        if (grid[n.X, n.Y])
          continue;
        Point w = n, e = new Point(n.X + 1, n.Y);
        while ((w.X >= 0) && !grid[w.X, w.Y])
        {
          grid[w.X, w.Y] = true;

          if ((w.Y > 0) && !grid[w.X, w.Y - 1])
            q.Enqueue(new Point(w.X, w.Y - 1));
          if ((w.Y < height - 1) && !grid[w.X, w.Y + 1])
            q.Enqueue(new Point(w.X, w.Y + 1));
          w.X--;
        }
        while ((e.X <= width - 1) && !grid[e.X, e.Y])
        {
          grid[e.X, e.Y] = true;

          if ((e.Y > 0) && !grid[e.X, e.Y - 1])
            q.Enqueue(new Point(e.X, e.Y - 1));
          if ((e.Y < height - 1) && !grid[e.X, e.Y + 1])
            q.Enqueue(new Point(e.X, e.Y + 1));
          e.X++;
        }
      }
    }
  }

- Richard Moss

Answer 2

有一种简单、美丽（而且通用）的方法，基于计算欧拉特征。

基本上，它就是关于计数2*2的正方形（在任何语言中都可以轻松实现）。

闭合曲线（带有1个“孔”）对应于欧拉特征等于零（在表示方面，“蓝色”和“红色”正方形数量相等）。

- Alleo

Answer 3

请看一下这个链接： 嵌入式视觉设计套件 这是荷兰阿纳姆-尼梅亨大学的一位教师制作的项目。

该项目用于嵌入式设计，但operators.cpp中的函数是用于逐像素处理图像的运算符。

编辑： 我并没有编写这段代码，我只是将其公开了。

- Junky