Flood fill recursive algorithm

Question

I'm trying to make an algorithm that could fill an int array in c#. Basically, as the fill tool in MS Paint, I have a color and if I choose (x,y) coordinates in the array, it replaces all the neighbours with the same initial color with the new color.

Ex :

[0,0,0]
[0,1,0]
[1,1,0]

If I put 3 in (0,0), the array becomes :

[3,3,3]
[3,1,3]
[1,1,3]

So I tried it in recursive and it does work, but not all the time. Actually, I have sometimes a "Stack Overflow" error (seems appropriate). Here's my code, it would be great if you could tell me what's wrong :)

public int[,] fill(int[,] array, int x, int y, int initialInt, int newInt)
{
    if (array[x, y] == initialInt)
    {
        array[x, y] = newInt;

        if (x < array.GetLength(0) - 1)
            array = fill(array, (x + 1), y, initialInt, newInt);
        if (x > 0)
            array = fill(array, (x - 1), y, initialInt, newInt);

        if (y < array.GetLength(1) - 1)
            array = fill(array, x, (y + 1), initialInt, newInt);
        if (y > 0)
            array = fill(array, x, (y - 1), initialInt, newInt);
    }

    return array;
}

Thanks !

Answer 1

How about using a stack/queue to manage the remaining work?

public void Fill(int[,] array, int x, int y, int newInt)
{
    int initial = array[x,y];

    Queue<Tuple<int,int>> queue = new Queue<Tuple<int,int>>();
    queue.Push(new Tuple<int, int>(x, y));

    while (queue.Any())
    {
        Tuple<int, int> point = queue.Dequeue();

        if (array[point.Value1, point.Value2] != initial)
            continue;

        array[point.Value1, point.Value2] = newInt;

        EnqueueIfMatches(array, queue, point.Value1 - 1, point.Value2, initial);
        EnqueueIfMatches(array, queue, point.Value1 + 1, point.Value2, initial);
        EnqueueIfMatches(array, queue, point.Value1, point.Value2 - 1, initial);
        EnqueueIfMatches(array, queue, point.Value1, point.Value2 + 1, initial);        
    }
}

private void EnqueueIfMatches(int[,] array, Queue<Tuple<int, int>> queue, int x, int y, int initial)
{
    if (x < 0 || x >= array.GetLength(0) || y < 0 || y >= array.GetLength(1))
        return;

    if (array[x, y] == initial)
       queue.Enqueue(new Tuple<int, int>(x, y));
}

Answer 2

This is a textbook example of why using recursion is not always appropriate. Recursion is great for going through data structures that are inherently recursive (e.g. trees), but your array of pixel data is not.

I suggest to add a counter to your code to print how often the fill() function is called. On every function call, your machine has to create a new frame on the stack in memory (so it knows to which memory position it has to return after the function is over). The recursive image fill algorithm calls the fill() function a huge number of times, hence the stack will grow very quickly. It has a limited size, so it will overflow for larger pictures.

The solution is to implement an iterative fill algorithm, using loops instead of recursion to iterate over the pixels.

See Wikipedia on recursion and stack overflows, or “Computer Graphics, Principles and Practice” by Foley et al. for a more detailed introduction to basic computer graphics algorithms.

Answer 3

As it was suggested already, the issue is with the number of recursive calls. On a 32bit machine you have 4bytes for the pointers, so if you have a 512*512 image and you want to fill the whole thing, the function pointers alone will occupy 512*512*4bytes = 1MB memory on your stack. And that is the default size of the stack. Regardless of the function pointers, you have another 5 references you pass (array, x, y, initialInt, newInt) which all are copied with every call as temporary objects, and are on the stack until the function call terminates. On the same sized image, those are another 512*512*5*4bytes = 5MB of memory.

To solve your issue you can modify (same link as above) the size of the stack.

Also, to save some stack space, you might consider wrapping the parameters inside a single object, in this case you will have only 4bits of temporary memory per call, instead of 20.

Still, as it was as well pointed out, the best solution is to rewrite your algorithm iteratively.