I want Flood Fill without stack and without recursion.

Question

I wanted to know how to apply flood fill on array , my array is two dimensional , which contains times new roman font type letter boundry. The boundry line contains 1's and inside and outside all 0's. I want to fill all 1's instead 0 in only inside. But i need a logic which do not required more memory. So avoid recursion and stack or queue

Answer 1

I don't normally do homework for other people, but I liked the challenge:

int c = -1;
while (c < 0)
{    
    /* Store breadcrumb trail, look to carry on */
    a[x][y] = c--;
    if (!hunt(0))
    {
        /* Nowhere to go, so back-track by looking for breadcrumb */
        a[x][y] = 1;
        c += 2;
        hunt(c);
    }
}

bool_t hunt(int v)
{
    if (a[x-1][y] == v)  { x--; return TRUE; }
    if (a[x+1][y] == v)  { x++; return TRUE; }
    if (a[x][y-1] == v)  { y--; return TRUE; }
    if (a[x][y+1] == v)  { y++; return TRUE; }
    return FALSE;
}

Note that this doesn't check for hitting the edges of the array. Also, it assumes your array elements are e.g. ints, and that you're only using the values 0 and 1 in your image.

Answer 2

You basically can't. You have to store this information somewhere, because you have to know where else to start filling after you're done with your current section. Recursion lets you do it implicitly. Keeping your own stack lets you do it explicitly, with possibly some saving. Oli Charlesworth does a cute thing by keeping an array of the same size as the picture, but that uses even more memory than recursion or keeping a stack of positions.

Answer 3

Your task doesn't make much sense. If you have a typeface, you don't want to fill it with a flood fill, but rather render it directly as filled polygon instead. Determining which parts are in and out of the typeface, especially for a serif font, if not going to give good results reliably.

The typical schematic algorithm for a filled polygon goes like this (no stack or recursion required), and it can be applied to a bitmap as well under certain conditions (I'll come to that):

For each line (or column, whatever suits your data structure better), toggle the fill at each intersection of the virtual line you're following and all polygon lines (boundaries).

Assume this (could be the middle line of an O character):

00010010001001000
   ^  ^   ^  ^
   |  |   |  stop
   |  |   start
   |  stop
   start

Result:

00011110001111000

This works for bitmaps as well, but only if you actually always have two boundaries for start and stop.