How do I fill an area using a non-recursive algorithm?

Question

I am trying to create a basic paint application using canvas (which refers to the 2DContext of the element in the code). However, with the current time, all browsers give up and say that Maximum call stack size exceeded. How can I improve on this code, to be able to fill larger regions?

I start the code as fillAround(Math.round(x), Math.round(y), colorAt(Math.round(x), Math.round(y)), fillcolor); where x and y are the coordinates of the click.

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

The hex to rgb converter is from RGB to Hex and Hex to RGB .

The updated code (with the help of @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]); 
        }
    }

and is called through

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

Indeed, stack memory is limited. Your code gets into very deeply nested calls of fillAround, which consume the available stack memory completely.

Without changing anything in the other logic, I would suggest replacing the recursive calls with a loop in which you manage your own stack:

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

This alone will not improve the speed, it will only avoid the stack memory exception.

To get better performance, you should not read/write each pixel individually with calls like:

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

... but use the power of the last two arguments of getImageData: read the whole canvas area into memory, at once, make the changes in memory, and then write that back with only one call of setImageData.