which flood-fill algorithm is better for performance?

Question

i'm trying to implement an algorithm which is flood-fill alike. the problem is that i'm not sure in what way i should implement it e.g recursive - non-recursive.
i know that each has its defects but one of them must be faster than the other one. the recursive opens new function on the stack when the non-recursive allocates 4 new points each time.
example for the non-iterative :

Stack<Point> stack = new Stack<Point>();
    stack.Push(q);
    while (stack.Count > 0)
    {
        Point p = stack.Pop();
        int x = p.X;
        int y = p.Y;
        if (y < 0 || y > h - 1 || x < 0 || x > w - 1)
                continue;
        byte val = vals[y, x];
        if (val == SEED_COLOR)
        {
                vals[y, x] = COLOR;
                stack.Push(new Point(x + 1, y));
                stack.Push(new Point(x - 1, y));
                stack.Push(new Point(x, y + 1));
                stack.Push(new Point(x, y - 1));
        }
    }

edit : im going to apply the following algorithm on a 600X600 pixels map. though the floodfill isn't going to be applied on the entire map, it should cover about 30% - 80% of the map each iteration. my point is to discover edges in a height map and mark those edges for a further use.

you should say what language you are using. in c or java, you would want the iterative solution. — andrew cooke
Don't use a stack, because the computer can do 20 copes of any pixel in the stack list, and re-do the instructions 20 times on it. write your own 2D array to record verified spaces, and onother array wich records the complete filled image, and read and write to them using this loop system: youtube.com/watch?v=LvacRISl99Y — LifeInTheTrees

Gangnus Gangnus · Accepted Answer · 2012-02-16T20:39:07

Make a mask - a parallel 2-dim array of bytes. Unchecked areas bytes has 0, for the fresh border of flooded area it will have value 1. For the inside of the flooded area - value 2. And keep the list of current border points, too.

At any end of the outer cycle you have the mask with marked current border, inside and outside area, and the array of the border points. So you will check for the new points only on the border. And while checking the first arraylist of border points, you are creating the second border arraylist and second mask. At the next step you recreate the first border array and mask. Going this way, we can use simple while cycle instead of recursion, for the data structure you check at any step is very simple.

BTW, you have forgotten to check coordinates of the new points for being on the drawn border or on the border of the whole rectangle.

As for cycling through all neighbouring points, look at my algorithm here

which flood-fill algorithm is better for performance?

3 Answers