c# - 在 C# 中查找闭合形状

Question

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

下图显示了我正在尝试完成的示例。该图像显示了一个封闭的形状，然后是两个可能有孔的形状。另请注意，形状不一定是简单的正方形或矩形，但不应存在直接对角线。

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

然后我的问题是 - 是否有一种算法(数学一窍不通的人可以遵循的东西!希望使用 C# 实现)可以检测此网格中的单个封闭形状(或多个形状，如果存在)，包括返回形状内的实际正方形？

到目前为止，我漫无边际的想法只涉及使用线性洪水填充，但这似乎并不合适，例如，没有单一的源点，但必须扫描整个网格以寻找可填充的形状。

Answer 1

多亏了@Groo 的评论，我意识到我的起步有点正确，那就是使用洪水填充。但是，我正在考虑扫描形状内部以找到我出错的边界。 Groo 建议，外面应该总是有一个点，然后从那里进行扫描。

我使用一个简单的二维 bool 数组(以及一个相当容易阅读的复制粘贴填充算法)编写了一个非常基本的测试程序，这似乎运行良好。我将这个简单的代码作为答案发布，以防它能帮助像我一样困惑的其他人，并且可能会阻止添加另一个措辞不佳的“问题”。

  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++;
        }
      }
    }
  }