在 Javascript 结束递归

Question

所以我尝试在 js 中实现 floodfill algorithm 并提出以下内容：

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);

}

它工作得很好，但我在填充较大区域 (10000x10000) 时遇到一些问题，该算法导致错误 "maximum call stack exceeded"。我明白这个错误的含义，但我不知道如何解决这个问题...

我愿意用更高效的算法替换这个函数，但我认为解决这个问题的方法可能是结束递归（我不知道如何在 js 中正确实现）。

编辑：像素数组包含应填充的像素。调用该函数时，它已经包含所有边框像素。

解决方案：

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});
    }
}

Answer 1

解决方案非常简单：删除递归。您还可以使用堆栈并将节点推送到堆栈而不是递归调用。伪代码：

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

在 Javascript 结束递归

End Recursion in Javascript

javascript

algorithm

recursion

graphics

rendering