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