How to fill all the empty space in a canvas in javascript ? (recursive function)

Question

I try to create a recursive function to fill all the empty space of a canvas until the edges or when there is already an other color filled.

function createFillingPoint() {
  let x = points[0][0],
    y = points[0][1];
  var pattern = ctx.getImageData(x, y, 1, 1).data;
  var colorToChange = rgbToHex(pattern);
  ctx.fillRect(x, y, 1, 1);
  colorFillRec(x + 1, y, width.value, height.value, colorToChange);
  colorFillRec(x - 1, y, width.value, height.value, colorToChange);
  colorFillRec(x, y + 1, width.value, height.value, colorToChange);
  colorFillRec(x, y - 1, width.value, height.value, colorToChange);
}

Basically, this function creates the first point and gives the original color that the function has to change.

function colorFillRec(x, y, w, h, colorToChange) {
  if (
    x > w ||
    x < 0 ||
    y > h ||
    y < 0 ||
    rgbToHex(ctx.getImageData(x, y, 1, 1).data) != colorToChange
  )
    return;
  ctx.fillRect(x, y, 1, 1);
  colorFillRec(x + 1, y, w, h, colorToChange);
  colorFillRec(x - 1, y, w, h, colorToChange);
  colorFillRec(x, y + 1, w, h, colorToChange);
  colorFillRec(x, y - 1, w, h, colorToChange);
}

This function is the recursive one. Both functions check the pixel's color, if it is different as the original color the function stops.

I tried to run the function but I got the "Maximum call stack size exceeded" error... I tried to find a new way to get the right result (with another recursive or not recursive function) but I couldn't.

Answer 1

You could use an explicit stack instead of the call stack. Also, it will be more efficient to call getImageData only once for the whole canvas area, and manipulate the image data and finally call putImageData to update the canvas in one operation.

Here is a demo:

function setup(ctx) { // Make some drawing to use for this demo
    function rect(x, y, w, h, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.rect(x, y, w, h);
        ctx.fill();
    }

    function circle(x, y, r, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.arc(x, y, r, 0, Math.PI * 2);
        ctx.fill();    
    }

    rect(0, 0, 600, 180, "pink");
    rect(100, 20, 200, 40, "red");
    rect(50, 40, 100, 30, "blue");
    circle(160, 95, 30, "green");
    rect(170, 30, 5, 80, "pink");
    rect(190, 25, 100, 10, "white");
    circle(150, 110, 10, "white");
}

// The main algorithm
function floodFill(ctx, x, y, r, g, b, a=255) {

    function match(i, source) {
        for (let j = 0; j < 4; j++) {
            if (img.data[i + j] !== source[j]) return false;
        }
        return true;
    }
    
    function set(i, target) {
        for (let j = 0; j < 4; j++) {
            img.data[i + j] = target[j];
        }
    }
    
    const {width, height} = ctx.canvas;
    const img = ctx.getImageData(0, 0, width, height);
    const start = (y * width + x) * 4;
    const line = width * 4;
    const max = line * height;
    
    const source = [...img.data.slice(start, start+4)];
    const target = [r, g, b, a];
    
    // Don't do anything if the start pixel already has the target color
    if (source.every((val, i) => val === target[i])) return;
    
    // Use an explicit stack
    const stack = [start];
    while (stack.length) {
        const i = stack.pop();
        if (!match(i, source)) continue;
        set(i, target);
        if (i < max - line)      stack.push(i + line);
        if (i >= line)           stack.push(i - line);
        if (i % line < line - 4) stack.push(i + 4);
        if (i % line >= 4)       stack.push(i - 4);
    }
    ctx.putImageData(img, 0, 0);
}

const ctx = document.querySelector("canvas").getContext("2d");
setup(ctx);
// After 2 seconds, perform the flood-fill
setTimeout(function () {
    floodFill(ctx, 0, 0, 120, 80, 0, 255); // (0, 0) -> brown
}, 2000);

<canvas width="600" height="180"></canvas>

This demo makes an example drawing, and then initiates a flood-fill from point (0, 0), meaning that it will find the connected pixels that have the same color as (0, 0) has, and make them brown.

It is important to note that the default color of a canvas is black, but with complete transparency, i.e. with alpha equal to 0. So you could get the wrong idea it is solid white (when on a white background). Starting a flood-fill on a pixel that has the default value (rgba = 0,0,0,0), will only fill pixels with that same rgba code, not pixels that were set to white (255,255,255,255).