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.

Solution 1

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

Solution 2

Computers process XY loops and 2D arrays very efficiently.

check this video to see what happens if put the standard recursive routine in a loop: https://www.youtube.com/watch?v=LvacRISl99Y

Instead of using complex logic to track previously verified neighbor spaces, you can have a 2D array that records all the verified spaces. Reading from the verified array is 2-3 instructions: IF pixel[23,23] is verified, THEN fill it and check it's neighbors.

Comments

[LifeInTheTrees]

I know for a fact that is wrong advice. Recursion is the fastest. ALOT. and simplest(50 lines) if you write your own memory array into the recursion loop. Its the lightest. Recursions can be stored in grids not trees. Grids are 1x picture memory size, trees are 100 gygabytes. Its also bitwise fast. I wrote a post about box. I tried to document my research here unity3dmc.blogspot.com/2017/02/… because it thrashes scanline codes and its ze smaller zimpler programming. Je te le guarantie emphatiquement.

[LifeInTheTrees]

The non-recursive is slower because it has many if conditions. Use 2-3 array duplicates of your canvas to store the steps of your recursion. It turns memory adressing into raw processing ASM speed.

[Gangnus]

I have realized this algorithm on the computer with the speed 340 operations/second. And it worked. Please, explain, how do you want to use border/colored/free areas marking and recursion? I can't imagine this. If you mean totally another way, that you mentioned in your answer, try to explain it to people that read it. Existing test is unreadable. I was not one of downvoters of your post. Now I am, too. Effectiveness of an unreadable post is 0.

[LifeInTheTrees]

I achieved 2million pixels per second. The recursive loop is about 40 ASM instructions, and a PC can run 80million flops. Where do you get 340 flops from? Please start a post "how do I order memory arrays within a recursion for flood fill" and I promise I will explain you its simple logic. The recursion is very easy: compare neighbor colors with "If-val instruction", mark results in arrays, recurse again, reading from arrays. What dont you understand? Start a query please.

[Gangnus]

@com.prehensible 1. Talking about the practical speed of algorithm without mentioning the speed of comp is senseless. 2. Explain your method in your answer, please. 3. Recursion is not an Assembler command. It is always based on more primitive operations. And it can be more simple only in the sense of the volume of written code and/or readability. In other aspects it always lower the effectiveness of the algorithm. 4. 340 op/sec? There were times when the speed of comps was lower. Probably, I am a bit longer than you in programming :-)

[Gangnus]

@com.prehensible Trying to explain better my algorithm, I have noticed that in one aspect you are right. Here we can use the recursion without noticeable losses. And the code will be more simple in understanding. But we will have to create more complex structures of data. And, of course, recursion will never be more effective, even a little bit. It simply can't.

[LifeInTheTrees]

You are very kind, You claim 340 operations per second. I am managing 4,000,000 operations per second, 1000x faster than your version. In one aspect, that's probably end of story for your generic implementation. Sorry I downvoted you though, Because I had 2 anonymous downvotes for a proven answer from lame coders, I was a bit annoyed and I subsequently downvoted all the answers which are 1000 times slower than my version of the code: youtube.com/watch?v=4hQ1wA4Sl4c&feature=youtu.be You have 340 operations per second, single I7 core can do 15 GigaFlops?!

[Gangnus]

@com.prehensible 340flops was the speed of COMPUTER, not of version or algorithm. And sorry, your logic or understanding are so damaged, I can't continue the discussion, it is waste of time. And my minus was not anonymous.