如何使用非递归算法填充区域？

Question

我试图使用canvas创建一个基本的油漆应用程序(它引用了代码中元素的2DContext )。然而，随着当前时间的推移，所有浏览器都放弃使用Maximum call stack size exceeded。如何改进这段代码，以便能够填充更大的区域？

我以fillAround(Math.round(x), Math.round(y), colorAt(Math.round(x), Math.round(y)), fillcolor);的形式启动代码，其中x和y是单击的坐标。

    function hexToRgb(hex) {
        var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
        return result ? {
            r: parseInt(result[1], 16),
            g: parseInt(result[2], 16),
            b: parseInt(result[3], 16)
        } : null;
    }

    function colorToRgb(arr) {
        return {
            r: arr[0],
            g: arr[1],
            b: arr[2]
        }
    }

    function colorAt(xp, yp) {
        return colorToRgb(canvas.getImageData(xp, yp, 1, 1).data);
    }

    function setColorAt(xp, yp, fill) {
        var color = canvas.getImageData(xp, yp, 1, 1)
        var set = hexToRgb(fill);
        color.data[0] = set.r;
        color.data[1] = set.g;
        color.data[2] = set.b;
        canvas.putImageData(color, xp, yp);
    }

    function sameColor(a, b) {
        return a.r == b.r && a.g == b.r && a.b == b.b;
    }

    function fillAround(xp, yp, original, fill) {
        if (sameColor(colorAt(xp, yp), original)) {
            setColorAt(xp, yp, fill);
            if (sameColor(colorAt(xp + 1, yp), original)) {
                fillAround(xp + 1, yp, original, fill);
            }
            if (sameColor(colorAt(xp - 1, yp), original)) {
                fillAround(xp - 1, yp, original, fill);
            }
            if (sameColor(colorAt(xp, yp + 1), original)) {
                fillAround(xp, yp + 1, original, fill);
            }
            if (sameColor(colorAt(xp, yp - 1), original)) {
                fillAround(xp, yp - 1, original, fill);
            }
        }
    }

十六进制到rgb转换器是从RGB to Hex and Hex to RGB。

更新的代码(在@trincot的帮助下)

    var canvasData;

    function hexToRgb(hex) {
        var result = /^#?([a-f\d]{2})([a-f\d]{2})([a-f\d]{2})$/i.exec(hex);
        return result ? {
            r: parseInt(result[1], 16),
            g: parseInt(result[2], 16),
            b: parseInt(result[3], 16)
        } : null;
    }

    function colorToRgb(arr) {
        return {
            r: arr[0],
            g: arr[1],
            b: arr[2]
        }
    }

    function colorAt(xp, yp) {
        return colorToRgb(canvasData.data.slice(4 * canvasTag.width * (yp - 1) + 4 * (xp + 1), 4 * canvasTag.widthwidth * (yp - 1) + 4 * xp + 8));
    }

    function setColorAt(xp, yp, fill) {
        var set = hexToRgb(fill);
        var o = 4 * canvasTag.width * (yp - 1) + 4 * (xp + 1);
        canvasData.data[o] = set.r;
        canvasData.data[o + 1] = set.g;
        canvasData.data[o + 2] = set.b;
    }

    function sameColor(a, b) {
        return a.r == b.r && a.g == b.r && a.b == b.b;
    }

    function fillAround(xp, yp, original, fill) {
        const stack = [[xp, yp]];
        while (stack.length) {
            const [xp, yp] = stack.pop();
            if (!sameColor(colorAt(xp, yp), original)) continue;
            setColorAt(xp, yp, fill);
            stack.push([xp + 1, yp], [xp - 1, yp], [xp, yp + 1], [xp, yp - 1]); 
        }
    }

并被召唤通过

canvasData = canvas.getImageData(0, 0, canvasTag.width, canvasTag.height);
fillAround(Math.round(x), Math.round(y), colorAt(Math.round(x), Math.round(y)), fillcolor);
canvas.putImageData(canvasData, 0, 0);

Answer 1

实际上，堆栈内存是有限的。您的代码进入了非常深层次的fillAround嵌套调用，这些调用完全占用了可用的堆栈内存。

在不更改其他逻辑中的任何内容的情况下，我建议将递归调用替换为您管理自己堆栈的循环：

function fillAround(xp, yp, original, fill) {
    const stack = [[xp, yp]]; // Initially the stack has one pair of coordinates
    while (stack.length) { // Keep iterating while there is work to do...
        const [xp, yp] = stack.pop(); // Get one pair of coordinates from the stack
        if (!sameColor(colorAt(xp, yp), original)) continue; // Skip it
        setColorAt(xp, yp, fill);
        // Push the neighbors onto the stack for later processing:
        stack.push([xp + 1, yp], [xp - 1, yp], [xp, yp + 1], [xp, yp - 1]); 
    }
}

这本身不会提高速度，它只会避免堆栈内存异常。

为了获得更好的性能，您不应该单独使用以下调用来读取/写入每个像素：

canvas.getImageData(xp, yp, 1, 1)
canvas.putImageData(color, xp, yp)

..。但是使用getImageData最后两个参数的强大功能:将整个画布区域读入内存中，立即在内存中进行更改，然后只使用一个setImageData调用将其写回。