How can I perform flood fill with HTML Canvas?

by

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 4096×4096 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 kind of naive. 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 4096×4096 canvas though. There might be other optimizations 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 whereas 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.

Let me also add, given the answer above freezes the browser while the fill is happening and that on a larger canvas that freeze could be too long, you can easily make the algorithm span over time using ES6 async/await. You need to choose how much work to give each segment of time. Choose too small and it will take a long time to fill. Choose too large and you’ll get jank as the browser freezes.

Here’s an example. Set ticksPerUpdate to speed up or slow down the fill rate

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(100, 145);
ctx.lineTo(110, 105);
ctx.lineTo(130, 125);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();

floodFill(ctx, 40, 50, 0xFF0000FF);

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

async function floodFill(ctx, x, y, fillColor) {
  // read the pixels in the canvas
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  
  // make a Uint32Array view on the pixels so we can manipulate pixels
  // one 32bit value at a time instead of as 4 bytes per pixel
  const pixelData = {
    width: imageData.width,
    height: imageData.height,
    data: new Uint32Array(imageData.data.buffer),
  };
  
  // get the color we're filling
  const targetColor = getPixel(pixelData, x, y);
  
  // check we are actually filling a different color
  if (targetColor !== fillColor) {
  
    const ticksPerUpdate = 50;
    let tickCount = 0;
    const pixelsToCheck = [x, y];
    while (pixelsToCheck.length > 0) {
      const y = pixelsToCheck.pop();
      const x = pixelsToCheck.pop();
      
      const currentColor = getPixel(pixelData, x, y);
      if (currentColor === targetColor) {
        pixelData.data[y * pixelData.width + x] = fillColor;
        
        // put the data back
        ctx.putImageData(imageData, 0, 0);
        ++tickCount;
        if (tickCount % ticksPerUpdate === 0) {
          await wait();
        }
        
        pixelsToCheck.push(x + 1, y);
        pixelsToCheck.push(x - 1, y);
        pixelsToCheck.push(x, y + 1);
        pixelsToCheck.push(x, y - 1);
      }
    }    
  }
}

function wait(delay = 0) {
  return new Promise((resolve) => {
    setTimeout(resolve, delay);
  });
}
<canvas></canvas>

update update

Instead of setTimeout which is throttled by the browser, you can abuse postMessage which is not

function makeExposedPromise() {
  let resolve;
  let reject;
  const promise = new Promise((_resolve, _reject) => {
    resolve = _resolve;
    reject = _reject;
  });
  return { promise, resolve, reject };
}

const resolveFns = [];

window.addEventListener('message', (e) => {
  const resolve = resolveFns.shift();
  resolve();
});

function wait() {
  const {resolve, promise} = makeExposedPromise();
  resolveFns.push(resolve);
  window.postMessage('');
  return promise;
}

If you use that it there’s less need to choose a number of operations. Also note: the slowest part is calling putImageData. The reason it’s inside the loop above is only so we can see the progress. Move that to the end and it will run much faster

function makeExposedPromise() {
  let resolve;
  let reject;
  const promise = new Promise((_resolve, _reject) => {
    resolve = _resolve;
    reject = _reject;
  });
  return { promise, resolve, reject };
}

const resolveFns = [];

window.addEventListener('message', (e) => {
  const resolve = resolveFns.shift();
  resolve();
});

function wait() {
  const {resolve, promise} = makeExposedPromise();
  resolveFns.push(resolve);
  window.postMessage('');
  return promise;
}

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(100, 145);
ctx.lineTo(110, 105);
ctx.lineTo(130, 125);
ctx.lineTo(190, 80);
ctx.lineTo(100, 60);
ctx.lineTo(50, 130);
ctx.lineTo(20, 20);
ctx.stroke();

floodFill(ctx, 40, 50, 0xFF0000FF);

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

async function floodFill(ctx, x, y, fillColor) {
  // read the pixels in the canvas
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);
  
  // make a Uint32Array view on the pixels so we can manipulate pixels
  // one 32bit value at a time instead of as 4 bytes per pixel
  const pixelData = {
    width: imageData.width,
    height: imageData.height,
    data: new Uint32Array(imageData.data.buffer),
  };
  
  // get the color we're filling
  const targetColor = getPixel(pixelData, x, y);
  
  // check we are actually filling a different color
  if (targetColor !== fillColor) {
  
    const pixelsToCheck = [x, y];
    while (pixelsToCheck.length > 0) {
      const y = pixelsToCheck.pop();
      const x = pixelsToCheck.pop();
      
      const currentColor = getPixel(pixelData, x, y);
      if (currentColor === targetColor) {
        pixelData.data[y * pixelData.width + x] = fillColor;
        
        await wait();
        
        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>

It’s still better to choose a number of operations per call to wait

There are also faster algorithms. The issue with the one above is there is for every pixel that matches, 4 are added to the stack of things to pixels to check. That’s lots of allocations and multiple checking. A faster way is to it by span.

For a given span, check as far left as you can, then as far right as you can, now fill that span. Then, check the pixels above and/or below the span you just found and add the spans you find to your stack. Pop the top span off, and try to expand it left and right. There’s no need to check the pixels in the middle since you already checked them. Further, if this span was generated from one below then you don’t need to check the pixels below the starting sub-span of this span since you know that area was already filled. Similarly if this pan was generated from one above then you don’t need to check the pixels above the starting sub-span of this span for the same reason.

function main() {
  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(100, 145);
  ctx.lineTo(110, 105);
  ctx.lineTo(130, 125);
  ctx.lineTo(190, 80);
  ctx.lineTo(100, 60);
  ctx.lineTo(50, 130);
  ctx.lineTo(20, 20);
  
  ctx.stroke();

  floodFill(ctx, 40, 50, 0xFF0000FF);
}
main();

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

function floodFill(ctx, x, y, fillColor) {
  // read the pixels in the canvas
  const imageData = ctx.getImageData(0, 0, ctx.canvas.width, ctx.canvas.height);

  // make a Uint32Array view on the pixels so we can manipulate pixels
  // one 32bit value at a time instead of as 4 bytes per pixel
  const pixelData = {
    width: imageData.width,
    height: imageData.height,
    data: new Uint32Array(imageData.data.buffer),
  };

  // get the color we're filling
  const targetColor = getPixel(pixelData, x, y);
  
  // check we are actually filling a different color
  if (targetColor !== fillColor) {
    const spansToCheck = [];
    
    function addSpan(left, right, y, direction) {
      spansToCheck.push({left, right, y, direction});
    }
    
    function checkSpan(left, right, y, direction) {
      let inSpan = false;
      let start;
      let x;
      for (x = left; x < right; ++x) {
        const color = getPixel(pixelData, x, y);
        if (color === targetColor) {
          if (!inSpan) {
            inSpan = true;
            start = x;
          }
        } else {
          if (inSpan) {
            inSpan = false;
            addSpan(start, x - 1, y, direction);
          }
        }
      }
      if (inSpan) {
        inSpan = false;
        addSpan(start, x - 1, y, direction);
      }
    }
    
    addSpan(x, x, y, 0);
    
    while (spansToCheck.length > 0) {
      const {left, right, y, direction} = spansToCheck.pop();
      
      // do left until we hit something, while we do this check above and below and add
      let l = left;
      for (;;) {
        --l;
        const color = getPixel(pixelData, l, y);
        if (color !== targetColor) {
          break;
        }
      }
      ++l
      
      let r = right;
      for (;;) {
        ++r;
        const color = getPixel(pixelData, r, y);
        if (color !== targetColor) {
          break;
        }
      }

      const lineOffset = y * pixelData.width;
      pixelData.data.fill(fillColor, lineOffset + l, lineOffset + r);
      
      if (direction <= 0) {
        checkSpan(l, r, y - 1, -1);
      } else {
        checkSpan(l, left, y - 1, -1);
        checkSpan(right, r, y - 1, -1);
      }
      
      if (direction >= 0) {
        checkSpan(l, r, y + 1, +1);
      } else {
        checkSpan(l, left, y + 1, +1);
        checkSpan(right, r, y + 1, +1);
      }     
    }
    // put the data back
    ctx.putImageData(imageData, 0, 0);
  }
}
<canvas></canvas>

Note: I didn’t test this well, there might be an off by 1 error or other issue. I’m 99% sure I wrote the span method in 1993 for My Paint but don’t remember if I have the source. But in any case, it’s fast enough there’s no need for wait

More Related Contents:

  1. How do I get the coordinates of a mouse click on a canvas element? [duplicate]
  2. Can I turn off antialiasing on an HTML element?
  3. Resize image with javascript canvas (smoothly)
  4. How to draw an inline svg (in DOM) to a canvas?
  5. MediaStream Capture Canvas and Audio Simultaneously
  6. Convert SVG to PNG with applied images as background to svg elements
  7. Any way to clone HTML5 canvas element with its content?
  8. Text wrap in a element
  9. How do I rotate a single object on an html 5 canvas?
  10. Use Javascript to get Maximum font size in canvas
  11. How can I animate a progressive drawing of svg path?
  12. How to determine the intended frame-rate on an html video element
  13. Drawing a rectangle using click, mouse move, and click
  14. How to pixelate an image with canvas and javascript
  15. getting mouse position with javascript within canvas
  16. Draw HTML5/Javascript Canvas Path in Time
  17. Saving canvas to image via canvas.toDataURL results in black rectangle
  18. Canvas Draw Image issue on firefox, works well in chrome
  19. Downloading Canvas element to an image
  20. clearRect not working
  21. HTML5 Canvas Performance and Optimization Tips, Tricks and Coding Best Practices [closed]
  22. canvas getContext(“2d”) returns null
  23. draw 10,000 objects on canvas javascript
  24. Why does my canvas go blank after converting to image?
  25. Body animation isn’t smooth
  26. How to implement SVG’s preserveAspectRatio=”xMinYMin slice” for canvas drawImage method.
  27. Converting Chart.js canvas chart to image using .toDataUrl() results in blank image
  28. Update HTML5 canvas rectangle on hover?
  29. how to animate drawing lines on canvas
  30. True Isometric Projection with HTML5 Canvas

Leave a Comment