javascript - 如何在 JavaScript 中对 HTML Canvas 进行洪水填充？

标签 javascript canvas html5-canvas flood-fill

<分区>

下面链接中附有我的 Canvas 截图(外框就是 Canvas )。内框是灰色框，线条是在 Canvas 中绘制的线条。如何创建用特定颜色填充整个 Canvas (内部灰色框和线条除外)的泛光填充函数？

该函数应该只接受三个变量，x y 和颜色，如下所示，但我不确定如何继续:

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);
}

Canvas Image

最佳答案

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

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>

虽然这段代码至少有 2 个问题。

  1. 它是深度递归的。

    所以你可能会用完堆栈空间

  2. 它很慢。

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

堆栈空间不足的解决方案是实现我们自己的堆栈。例如，不是递归调用 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>

它太慢的解决方案是 make it run a little at a time或将其移交给 worker 。我认为在同一个答案中显示的内容太多了 here's an example .我在 4096x4096 Canvas 上测试了上面的代码，在我的机器上填充空白 Canvas 需要 16 秒，所以是的，它可以说太慢了，但是把它放在一个 worker 中会带来新的问题，即结果将是异步的，所以即使浏览器不会卡住您可能希望阻止用户在完成之前执行某些操作。

另一个问题是你会看到线条是抗锯齿的，所以用纯色填充会关闭线条，但不会一直到它。要解决这个问题，您可以更改 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>

请注意，此版本的 colorsMatch 使用有点幼稚。转换为 HSV 或其他东西可能会更好，或者您可能想按 alpha 加权。我不知道匹配颜色的好的指标是什么。

更新

另一种加快速度的方法当然是优化代码。 Kaiido 指出了一个明显的加速方法，即在像素上使用 Uint32Array View 。这样查找一个像素并设置一个像素时，只有一个 32 位值可供读取或写入。 Just that change makes it about 4x faster .填满 4096x4096 的 Canvas 仍然需要 4 秒。可能还有其他优化，例如不调用 getPixels 进行内联，但不要在我们的像素列表上推送新像素以检查它们是否超出范围。它可能会加速 10%(不知道)，但不会快到足以成为交互速度。

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

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

更新:

在 this answer 结束时算法更快

关于javascript - 如何在 JavaScript 中对 HTML Canvas 进行洪水填充？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53077955/

上一篇：javascript - 如何在 AJAX 函数中从 HTML 获取值字段？

下一篇：javascript - 生成多个具有不同条件的数组

相关文章：

javascript - ES6 中的解构赋值与对象属性访问

canvas - Go 中的 move_uploaded_file 等价物

php - HTML5 在 Canvas 中加载较小的图像并保存实际尺寸的图像

javascript - 提高visjs性能

javascript - 根据线条( Canvas )的位置添加文本标签

javascript - 使用javascript创建闪烁效果

javascript - 如何获取html元素的子元素

javascript - 覆盖在 html 上不会全屏显示

javascript - 短父元素中 float 图像上不需要的底部边距

javascript - 淡出文本并淡入下一个 Canvas

©2024 IT工具网  联系我们