End Recursion in Javascript

Question

So I've tried to implement the floodfill algorithm in js and came up with the following:

function floodAreaFromPoint(x,y) {

    if(typeof pixel[x] == "undefined") pixel[x] = [];
    pixel[x][y] = 1; // 1 for alpha

    if(!coordsInPixelArray(x + 1,y)) floodAreaFromPoint(x + 1,y);
    if(!coordsInPixelArray(x,y + 1)) floodAreaFromPoint(x,y + 1);
    if(!coordsInPixelArray(x - 1,y)) floodAreaFromPoint(x - 1,y);
    if(!coordsInPixelArray(x,y - 1)) floodAreaFromPoint(x,y - 1);

}

It works kinda fine but I have some issues with filling larger areas (10000x10000) where this alogrithm results in the error "maximum call stack exceeded". I understand the meaning of this error but I have no idea how i could possibly fix this...

I am willing to replace this function with a more efficient algorithm but I think the solution to this problem could be end recursion (which I have no idea how to correctly implement in js).

Edit: The pixel array contains the pixels that should be filled. When the function is called it already holds all border pixels.

Solution:

function flood(x,y) {
    var nodes = [];
    nodes.push({"x":x,"y":y});

    while(nodes.length > 0) {
        var p = nodes[nodes.length - 1];
        if(coordsInPixelArray(p.x, p.y)) {
            nodes.pop();
            continue;
        }

        if(typeof pixel[p.x] == "undefined") pixel[p.x] = [];
        pixel[p.x][p.y] = 1; // 1 for alpha

        if(!coordsInPixelArray(p.x + 1, p.y)) nodes.push({"x": p.x + 1,"y": p.y});
        if(!coordsInPixelArray(p.x - 1, p.y)) nodes.push({"x": p.x - 1,"y": p.y});
        if(!coordsInPixelArray(p.x, p.y + 1)) nodes.push({"x": p.x,"y": p.y + 1});
        if(!coordsInPixelArray(p.x, p.y - 1)) nodes.push({"x": p.x,"y": p.y - 1});
    }
}

This fills the whole matrix unconditionally. You should not only check that the coords are valied, but also that you don't hit a pixel that shouldn't be flooded. At the very least, you should check that the current pixel isn't already 1 before recursing. Otherwise you will visit the pixels over and over again, even if you have already visited them. — M Oehm
– M Oehm, Commented Apr 23, 2015 at 10:52
Also: if(typeof pixel[x] == "undefined") pixel[x] = []; Are you creating the matrix as you go? — M Oehm
– M Oehm, Commented Apr 23, 2015 at 10:53
Forgot to point out that I fill the pixel array before with the border pixels. So if I hit an already set pixel I know that it would be filled and I can stop there. — user3421907
– user3421907, Commented Apr 23, 2015 at 10:54
But what is the boder pixel? Your code is missing a condition to check it. — M Oehm
– M Oehm, Commented Apr 23, 2015 at 10:56
the function coordsInPixelArray checks if a pixel is already set in the matrix. If so it does not matter if it is an border pixel or an fill pixel because I dont need to fill it or operate further in its direction. — user3421907
– user3421907, Commented Apr 23, 2015 at 11:00

score 2 · Accepted Answer · 2015-04-23 11:21:58Z

2

The solution is pretty simple: remove the recursion. You can aswell use a stack and push the nodes to the stack instead of a recursive call. pseudocode:

stack nodes//create a new stack
add(nodes , startNode)//initialize the stack with the first node

while ! isEmpty(nodes)//still nodes available that haven't been processed
    node p = peek(nodes)

    if ! nodeInArray(p) OR getColor(p) == 1
        //this node has already been visited or is not in the array
        //continue with the next node in the stack
        pop(nodes)
        continue

    color(p , 1)//mark the node as visited
    push(nodes , node(x(p) - 1 , y(p))//add node to be processed in the future
    ...//push all other neighbours to the stack

edited Apr 23, 2015 at 11:21

answered Apr 23, 2015 at 10:58

user4668606

Sign up to request clarification or add additional context in comments.

3 Comments

user3421907 Over a year ago

okay give me a second. I cant fully grasp your concept in my head but I will try to implement it and come back to you :)

user4668606 Over a year ago

sry, should've added some comments to explain. give me a sec, i'll fix that

user3421907 Over a year ago

Thanks! It works but its very slow :( Edit: Mybad! Works like a charm! :)

Collectives™ on Stack Overflow

End Recursion in Javascript

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related