How do I do flood fill on the HTML canvas in JavaScript? [duplicate]

Question

As attached in the link below is a screenshot of my canvas (outer box is the canvas). The inner box is a grey box and the line is a line drawn in the canvas. How do I create a flood fill function that fills the entire canvas (except the inner grey box as well as the line) with a specific color?

The function should accept three variables only, x y and color, as seen below, but I'm not sure how to continue:

floodFill(x, y, color) {
    this.canvasColor[x][y] = color;

    this.floodFill(x-1, y, color);
    this.floodFill(x+1, y, color);
    this.floodFill(x, y-1, color);
    this.floodFill(x, y+1, color);
}

Answer 1

To create a flood fill you need to be able to look at the pixels that are there already and check they aren't the color you started with so something like this.

const ctx = document.querySelector("canvas").getContext("2d");

ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();

floodFill(ctx, 40, 50, [255, 0, 0, 255]);

function getPixel(imageData, x, y) {
  if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
    return [-1, -1, -1, -1];  // impossible color
  } else {
    const offset = (y * imageData.width + x) * 4;
    return imageData.data.slice(offset, offset + 4);
  }
}

function setPixel(imageData, x, y, color) {
  const offset = (y * imageData.width + x) * 4;
  imageData.data[offset + 0] = color[0];
  imageData.data[offset + 1] = color[1];
  imageData.data[offset + 2] = color[2];
  imageData.data[offset + 3] = color[0];
}

function colorsMatch(a, b) {
  return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
}

function floodFill(ctx, x, y, fillColor) {
  // read the pixels in the canvas
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  
  // get the color we're filling
  const targetColor = getPixel(imageData, x, y);
  
  // check we are actually filling a different color
  if (!colorsMatch(targetColor, fillColor)) {
  
    fillPixel(imageData, x, y, targetColor, fillColor);
    
    // put the data back
    ctx.putImageData(imageData, 0, 0);
  }
}

function fillPixel(imageData, x, y, targetColor, fillColor) {
  const currentColor = getPixel(imageData, x, y);
  if (colorsMatch(currentColor, targetColor)) {
    setPixel(imageData, x, y, fillColor);
    fillPixel(imageData, x + 1, y, targetColor, fillColor);
    fillPixel(imageData, x - 1, y, targetColor, fillColor);
    fillPixel(imageData, x, y + 1, targetColor, fillColor);
    fillPixel(imageData, x, y - 1, targetColor, fillColor);
  }
}

<canvas></canvas>

There's at least 2 problems with this code though.

1. It's deeply recursive.

   So you might run out of stack space

2. It's slow.

   No idea if it's too slow but JavaScript in the browser is mostly single threaded so while this code is running the browser is frozen. For a large canvas that frozen time might make the page really slow and if it's frozen too long the browser will ask if the user wants to kill the page.

The solution to running out of stack space is to implement our own stack. For example instead of recursively calling fillPixel we could keep an array of positions we want to look at. We'd add the 4 positions to that array and then pop things off the array until it's empty

const ctx = document.querySelector("canvas").getContext("2d");

ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();

floodFill(ctx, 40, 50, [255, 0, 0, 255]);

function getPixel(imageData, x, y) {
  if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
    return [-1, -1, -1, -1];  // impossible color
  } else {
    const offset = (y * imageData.width + x) * 4;
    return imageData.data.slice(offset, offset + 4);
  }
}

function setPixel(imageData, x, y, color) {
  const offset = (y * imageData.width + x) * 4;
  imageData.data[offset + 0] = color[0];
  imageData.data[offset + 1] = color[1];
  imageData.data[offset + 2] = color[2];
  imageData.data[offset + 3] = color[0];
}

function colorsMatch(a, b) {
  return a[0] === b[0] && a[1] === b[1] && a[2] === b[2] && a[3] === b[3];
}

function floodFill(ctx, x, y, fillColor) {
  // read the pixels in the canvas
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  
  // get the color we're filling
  const targetColor = getPixel(imageData, x, y);
  
  // check we are actually filling a different color
  if (!colorsMatch(targetColor, fillColor)) {
  
    const pixelsToCheck = [x, y];
    while (pixelsToCheck.length > 0) {
      const y = pixelsToCheck.pop();
      const x = pixelsToCheck.pop();
      
      const currentColor = getPixel(imageData, x, y);
      if (colorsMatch(currentColor, targetColor)) {
        setPixel(imageData, x, y, fillColor);
        pixelsToCheck.push(x + 1, y);
        pixelsToCheck.push(x - 1, y);
        pixelsToCheck.push(x, y + 1);
        pixelsToCheck.push(x, y - 1);
      }
    }
    
    // put the data back
    ctx.putImageData(imageData, 0, 0);
  }
}

<canvas></canvas>

The solution to it being too slow is either to make it run a little at a time OR to move it to a worker. I think that's a little too much to show in the same answer though here's an example. I tested the code above on a 4096x4096 canvas and it took 16 seconds to fill a blank canvas on my machine so yes it's arguably too slow but putting it in a worker brings new problems which is that the result will be asynchronous so even though the browser wouldn't freeze you'd probably want to prevent the user from doing something until it finishes.

Another issue is you'll see the lines are antialiased and so filling with a solid color fills close the the line but not all the way up to it. To fix that you can change colorsMatch to check for close enough but then you have a new problem that if targetColor and fillColor are also close enough it will keep trying to fill itself. You could solve that by making another array, one byte or one bit per pixel to track places you've ready checked.

const ctx = document.querySelector("canvas").getContext("2d");

ctx.beginPath();
ctx.moveTo(20, 20);
ctx.lineTo(250, 70);
ctx.lineTo(270, 120);
ctx.lineTo(170, 140);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();

floodFill(ctx, 40, 50, [255, 0, 0, 255], 128);

function getPixel(imageData, x, y) {
  if (x < 0 || y < 0 || x >= imageData.width || y >= imageData.height) {
    return [-1, -1, -1, -1];  // impossible color
  } else {
    const offset = (y * imageData.width + x) * 4;
    return imageData.data.slice(offset, offset + 4);
  }
}

function setPixel(imageData, x, y, color) {
  const offset = (y * imageData.width + x) * 4;
  imageData.data[offset + 0] = color[0];
  imageData.data[offset + 1] = color[1];
  imageData.data[offset + 2] = color[2];
  imageData.data[offset + 3] = color[0];
}

function colorsMatch(a, b, rangeSq) {
  const dr = a[0] - b[0];
  const dg = a[1] - b[1];
  const db = a[2] - b[2];
  const da = a[3] - b[3];
  return dr * dr + dg * dg + db * db + da * da < rangeSq;
}

function floodFill(ctx, x, y, fillColor, range = 1) {
  // read the pixels in the canvas
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  
  // flags for if we visited a pixel already
  const visited = new Uint8Array(imageData.width, imageData.height);
  
  // get the color we're filling
  const targetColor = getPixel(imageData, x, y);
  
  // check we are actually filling a different color
  if (!colorsMatch(targetColor, fillColor)) {

    const rangeSq = range * range;
    const pixelsToCheck = [x, y];
    while (pixelsToCheck.length > 0) {
      const y = pixelsToCheck.pop();
      const x = pixelsToCheck.pop();
      
      const currentColor = getPixel(imageData, x, y);
      if (!visited[y * imageData.width + x] &&
           colorsMatch(currentColor, targetColor, rangeSq)) {
        setPixel(imageData, x, y, fillColor);
        visited[y * imageData.width + x] = 1;  // mark we were here already
        pixelsToCheck.push(x + 1, y);
        pixelsToCheck.push(x - 1, y);
        pixelsToCheck.push(x, y + 1);
        pixelsToCheck.push(x, y - 1);
      }
    }
    
    // put the data back
    ctx.putImageData(imageData, 0, 0);
  }
}

<canvas></canvas>

Note that this version of colorsMatch is using is kind of naieve. It might be better to convert to HSV or something or maybe you want to weight by alpha. I don't know what a good metric is for matching colors.

Update

Another way to speed things up is of course to just optimize the code. Kaiido pointed out an obvious speedup which is to use a Uint32Array view on the pixels. That way looking up a pixel and setting a pixel there's just one 32bit value to read or write. Just that change makes it about 4x faster. It still takes 4 seconds to fill a 4096x4096 canvas though. There might be other optimization like instead of calling getPixels make that inline but don't push a new pixel on our list of pixels to check if they are out of range. It might be 10% speed up (no idea) but won't make it fast enough to be an interactive speed.

There are other speedups like checking across a row at a time since rows are cache friendly and you can compute the offset to a row once and use that while checking the entire row where as now for every pixel we have to compute the offset multiple times.

Those will complicate the algorithm so they are best left for you to figure out.

update:

faster algo at the end of this answer