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.