CODEWITHSUNDEEP
algorithmsearchgridshapesflood-fill
eonu
eonu

Reputation: 71

Algorithm to find and fill enclosed shapes on a grid

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

Answers (2)

Saeed Amiri
Saeed Amiri

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

MBo
MBo

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

Related Questions