Non-Recursive Floodfill In Worker

by Gregg Tavares

HTML

<canvas></canvas>

JavaScript

const workerScript = `
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(imageData, x, y, fillColor) {
  // 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);
      }
    }
  }
}

self.onmessage = (e) => {
   const {x, y, fillColor, imageData} = e.data;
   floodFill(imageData, x, y, fillColor);  
   self.postMessage(imageData);
};
`;

// setup worker.
const blob = new Blob([workerScript], {type: 'application/javascript'});
const url = URL.createObjectURL(blob);
const worker = new Worker(url);

// when the worker finished filling it will pass us
// back an imagedata.
worker.onmessage = (e) => {
  const imageData = e.data;
  // put the data back
  ctx.putImageData(imageData, 0, 0);
};

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

ctx.beginPath();
ctx.moveTo(20,...