如何在 JavaScript 中对 HTML 画布进行洪水填充？

Question

下面的链接中附加的是我的画布的屏幕截图（外框是画布）。内框是灰色框，线条是在画布上绘制的线条。如何创建一个洪水填充函数，用特定颜色填充整个画布（内部灰色框和线条除外）？

该函数应该只接受三个变量，xy 和颜色，如下所示，但我不知道如何继续：

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

要创建洪水填充，您需要能够查看已经存在的像素并检查它们是否不是您开始使用的颜色，就像这样。

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>

不过这段代码至少有两个问题。

1. 它是深度递归的。

   所以你可能会耗尽堆栈空间

2. 很慢。

   不知道它是否太慢，但浏览器中的 JavaScript 大多是单线程的，因此当这段代码运行时，浏览器会被冻结。对于大画布，冻结时间可能会使页面非常慢，如果冻结时间太长，浏览器会询问用户是否要终止页面。

堆栈空间不足的解决方案是实现我们自己的堆栈。例如，fillPixel我们可以保留我们想要查看的位置数组，而不是递归调用。我们将 4 个位置添加到该数组中，然后从数组中弹出内容，直到它为空

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>

解决它太慢的方法是要么让它一次运行一点点，要么将它移交给工人。我认为尽管这是一个例子，但在同一个答案中显示有点太多了。我在 4096x4096 画布上测试了上面的代码，在我的机器上填充空白画布花了 16 秒，所以是的，它可以说太慢了，但是将它放入工作线程中会带来新的问题，即结果将是异步的，所以即使浏览器不会冻结，您可能希望阻止用户执行某些操作，直到它完成为止。

另一个问题是，您会看到线条是抗锯齿的，因此用纯色填充会关闭线条，但不会一直到线条为止。要解决这个问题，您可以更改colorsMatch为检查是否足够接近，但随后您会遇到一个新问题，如果targetColor和fillColor也足够接近，它将继续尝试填充自身。您可以通过创建另一个数组（每个像素一个字节或一位）来跟踪您已准备好检查的位置来解决这个问题。

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>

请注意，这个版本的colorsMatchis using 有点幼稚。转换为 HSV 或其他格式可能会更好，或者您可能想按 alpha 进行权重。我不知道匹配颜色的好指标是什么。

更新

加快速度的另一种方法当然是优化代码。Kaiido 指出了一个明显的加速方法，那就是使用Uint32Array像素视图。这样，查找像素并设置像素时，只需读取或写入一个 32 位值。仅仅这一改变就使其速度提高了约 4 倍。不过，填充 4096x4096 画布仍然需要 4 秒。可能还有其他优化，例如不调用getPixelsmake that inline，但不要在我们的像素列表上推送新像素来检查它们是否超出范围。它可能会加快 10%（不知道），但不足以达到交互速度。

还有其他加速方法，例如一次检查一行，因为行是缓存友好的，您可以计算一次行的偏移量，然后在检查整个行时使用它，而现在对于每个像素，我们必须多次计算偏移量。

这些会使算法变得复杂，因此最好留给您自己解决。

更新：

更快的算法在这个答案的末尾