Finding closed shapes in C#

Question

Assuming you have a grid of squares, where each grid item is either "filled" or "not-filled", is there a nice algorithm that can detect any "solid" shapes in the grid?

The image below shows an example of what I'm trying to accomplish. The image shows one enclosed shape, and then two potential shapes which have holes in them. Also note that shapes aren't necessarily simple squares or rectangles, although direct diagonals should not be present.

• Red squares denote "filled" squares.
• Blue squares represent the inner area of an enclosed shape
• White squares are unfilled

My question then is - is there an algorithm (something that can be followed by someone utterly useless at maths! and hopefully with a C# implementation) that can detect the single enclosed shape in this grid (or multiple shapes if present), including returning the actual squares inside the shape?

My rambling thoughts so far only cover using a linear flood fill, but that doesn't really seem suitable, for example there is no single source point, but the entire grid must be scanned for fillable shapes.

Answer 1

Thanks to a comment by @Groo, I realized that I had started off on somewhat the right foot, which is to use a flood fill. However, I was thinking of scanning inside the shapes to find the boundaries which is where I was going wrong. Groo suggested that there should always be a point outside, and perform the scanning from there.

I wrote a very basic test program using a simple 2D bool array (and a copy-and-pasted floodfill algorithm that was fairly easy to read) and this seems to work nicely. I'm posting this simple code as an answer in case it helps anyone else as muddled as I, and perhaps prevent another poorly phrased "question" being added.

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