javascript - 在 Javascript 中结束递归

Question

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

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) 时遇到了一些问题，其中此算法导致错误“超出最大调用堆栈”。我了解此错误的含义，但我不知道如何解决此问题...

我愿意用更高效的算法替换这个函数，但我认为解决这个问题的方法可能是结束递归(我不知道如何在 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