Reputation: 71
So say we have an empty grid of 0s:
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
And you can draw shapes on it. 1 represents a filled cell.
1 1 1 1 0 0 0 0
1 0 0 1 0 0 0 0
1 0 0 1 0 0 0 0
1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 1
1 0 0 1 0 1 0 0
0 1 1 0 0 1 0 0
A shape is considered closed if a four-directional flood-fill algorithm would not leak and fill any cells outside of the shape. A shape can not use the boundary of the grid as one of its sides. So if we filled in all of the closed shapes in this grid with 2s, we would have:
1 1 1 1 0 0 0 0
1 2 2 1 0 0 0 0
1 2 2 1 0 0 0 0
1 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0
0 1 1 0 0 1 1 1
1 2 2 1 0 1 0 0
0 1 1 0 0 1 0 0
Implementing the flood-fill algorithm is easy, but I can't figure out a way to (programatically) fill in all enclosed arbitrary shapes in a grid. Are there any type of algorithms or searches I could use for this?
Upvotes: 1
Views: 2806
Reputation: 22565
You can first find zero's which have a path to boundary:
Take arbitrary 0 cell in the boundary, mark it as -1, do this for all of its neighbouring cells recursively (neighbours of neighbours and so on all set to -1). Once none of the boundary cells is zero, turn all zero cells to 2. It means that they are surrounded by only 1's. After all turn all -1's to 0. This is O(n) which n is the number of cells in the grid.
Here is a (lazy) pseudo code, assuming we have n_1xn_2 grid:
function fill()
{
for int i=1..n_1
{
recursivecolor(i,1);
recursivecolor(i,n_2);
}
for int j=1..n_2
{
recursivecolor(1,j);
recursivecolor(n_1,j);
}
for i=1..n_1
for j=1 .. n_2
if (a[i][j] == 0)
a[i][j] = 2;
for i=1..n_1
for j=1 .. n_2
if (a[i][j] == -1)
a[i][j] = 0;
}
function recursivecolor(i,j)
{
if (a[i][j]!=0) return;
a[i][j] = -1;
if (a[i-1][j] == 0)
{
a[i-1][j] = -1;
recursivecolor(i-1,j);
}
// do this for all neighbours of i,j cell
// it also needs check for boundaries, e.g. i-1 should not be zero ...
}
Upvotes: 1
Reputation: 80325
What's wrong with flood-fill algorithm? It is simple end effective with complexity O(N).
At first scan edges for zero values and flood empty regions with mark value 3. Then walk through inner place. If you find zero cell, flood-fill from this cell with value 2.
(Perhaps you are seeking something like connected-component labeling algorithm. It is intended to mark every connected region by unique mark value)
Upvotes: 1