How to Implement the Paint Fill

Emulating paint fill is easy and can be done either iteratively or thru stacks. This demonstration is done using plain text, but the same idea could be implemented using your favorite graphics framework.

First, we're given a two-dimensional array of canvass of type char with size [N][M], where N is the number of rows and M is the number of columns.

Let's suppose N = 11 and M = 15, but of course, the values of these two may vary.

Assuming canvass is initialized properly and that the character '*' defines our boundary. We may have arbitrary values of the canvass as follows:

'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*',
'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', ' ', ' ', ' ', ' ', ' ', '*', '*', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', ' ', ' ', ' ', ' ', ' ', '*', ' ', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', ' ', ' ', ' ', ' ', '*', '*', ' ', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', '*', '*', '*', '*', '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*',
'*', ' ', '*', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', ' ', '*',
'*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*',
 

I've recolored the values of the canvass array to give emphasis on the boundary. 

Recursive Implementation

Let's start with recursion, the easiest way to implement the fill. The idea is simple:

1. Start on a specified coordinate of the canvass (x, y) and mark it as filled. 
2. If left is space, recurse canvass(x-1, y)
3. If the right is space, recurse canvass(x+1, y)
4. If the bottom is space, recurse canvass(x, y+1)
5. If the top is space, recurse canvass(x, y-1)

You'll end up filling-up the entire region bounded by '*' specified in the first (x, y) coordinate. The full implementation of the function is as follows:

void fill(char (*canvass)[M], int n, int m)
{
    canvass[n][m] = '.';
    if (canvass[n - 1][m] == ' ') fill(canvass, n - 1, m);
    if (canvass[n + 1][m] == ' ') fill(canvass, n + 1, m);
    if (canvass[n][m - 1] == ' ') fill(canvass, n, m - 1);
    if (canvass[n][m + 1] == ' ') fill(canvass, n, m + 1);
}

Take note that the boundary is not checked as the function assumes that the boundary is properly initialized. It is better to do it this way and have a separate boundary checker outside the function to optimize the program for speed.

Stacks Implementation

Another approach in solving the problem is through stacks.

For stacks, we'll be pushing the values of the last coordinate and pop it for later use. You can imagine the stack piles up as the main loop traverses the canvass coordinates. The good thing is that it frees up the memory as it finishes up the processing. The maximum stack that will be required is (N - 2) x (M - 2) + 1. Assuming proper boundaries are set. For this demonstration, we'll pre-allocate the maximum values the stack may reach and implement it using arrays.

To implement the fill using stacks, one has to:

1. Start on a specified coordinate of the canvass (x, y) and push it onto the stack
2. While there are items in stack:
   • Pop the last coordinate and mark it as filled
   • If left of canvass is space, push (x-1, y) to stack
   • If right of canvass is space, push (x+1, y) to stack
   • If bottom of canvass is pace, push (x, y+1) to stack
   • If top of canvass is space, push (x, y-1) to stack

You'll end up filling-up the entire region bounded by '*' specified in the first (x, y) coordinate. The full implementation of the function is as follows:

void fillStacks(char(*canvass)[M], int n, int m)
{
    int s = 0; Coord c;

    stacks[s++] = { n, m };
    
    do
    {
        c = stacks[--s];
        canvass[c.n][c.m] = ':';

        if (canvass[c.n - 1][c.m] == ' ') 
            stacks[s++] = { c.n - 1, c.m };

        if (canvass[c.n + 1][c.m] == ' ') 
            stacks[s++] = { c.n + 1, c.m };

        if (canvass[c.n][c.m - 1] == ' ') 
            stacks[s++] = { c.n, c.m - 1 };

        if (canvass[c.n][c.m + 1] == ' ') 
            stacks[s++] = { c.n, c.m + 1 };

    } while (s > 0);
}
 

The Output

On the left region is the recursive implementation and on the right is the stack. But the question here is which is better? Well from looks of it, the stack is the better implementation of paint fill because system stack call is not invoked in the process of filling up the canvass.