开发者问题收集

JavaScript 洪水填充范围错误

2023-02-25
79
javascript html css canvas

我正在用 JavaScript 开发一个绘画应用程序，我还需要添加一个油漆桶工具。为此，我在互联网上进行了研究，并在我的代码中实现了我找到的一个算法，但这个算法在我的代码中发现了一个错误。当要绘制的区域很大时，我得到了 Uncaught RangeError: Maximum call stack size reached 。

屏幕截图：

Screenshot

我的测试代码： 

const canvas = document.querySelector('.canvas')
const ctx = canvas.getContext('2d', {
    willReadFrequently: true
})
canvas.width = 400
canvas.height = 400

ctx.fillStyle = '#fff'
ctx.fillRect(0, 0, canvas.width, canvas.height)

ctx.strokeStyle = '#000'
ctx.lineWidth = 2
ctx.strokeRect(8, 8, canvas.width - 16, canvas.height - 16)

const setColor = (imageData, pixelPos) => {
    imageData.data[pixelPos] = 0
    imageData.data[pixelPos + 1] = 255
    imageData.data[pixelPos + 2] = 0
    imageData.data[pixelPos + 3] = 255
    ctx.putImageData(imageData, 0, 0)
}

const floodFill = (pixelPos, imageData, oldColor, newColor) => {
    const top = pixelPos - canvas.width * 4
    const bottom = pixelPos + canvas.width * 4
    const left = pixelPos - 4
    const right = pixelPos + 4

    if (
        imageData.data[pixelPos] === oldColor.r &&
        imageData.data[pixelPos + 1] === oldColor.g &&
        imageData.data[pixelPos + 2] === oldColor.b &&
        imageData.data[pixelPos + 3] === oldColor.a
    ) {
        setColor(imageData, pixelPos)
        floodFill(top, imageData, oldColor, newColor)
        floodFill(bottom, imageData, oldColor, newColor)
        floodFill(left, imageData, oldColor, newColor)
        floodFill(right, imageData, oldColor, newColor)
    }
}

addEventListener('mousedown', e => {
    const rect = canvas.getBoundingClientRect(),
        x = Math.floor(e.x - rect.x),
        y = Math.floor(e.y - rect.y)

    if (x < 0 || y < 0 || x > canvas.width || y > canvas.height) return

    let imageData = ctx.getImageData(0, 0, canvas.width, canvas.height)
    const pixelPos = (y * canvas.width + x) * 4
    const oldColor = {
        r: imageData.data[pixelPos],
        g: imageData.data[pixelPos + 1],
        b: imageData.data[pixelPos + 2],
        a: imageData.data[pixelPos + 3],
    }
    const newColor = {
        r: 0,
        g: 255,
        b: 0,
        a: 255,
    }

    floodFill(pixelPos, imageData, oldColor, newColor)
})
body {
    background-color: #000;
    height: 100vh;
    display: flex;
    justify-content: center;
    align-items: center;
}
<canvas class="canvas"></canvas>
2个回答

您的“洪水填充”算法在原则上是正确的，但在实践中却毫无希望

它的工作原理是：

  • 对像素进行着色
  • 然后转到 4 个相邻像素中的每一个，并再次调用相同的函数

这种方法的问题在于，需要进行大量的调用才能完成洪水填充。

尝试一些其他洪水填充方法：

哪种洪水填充算法性能更好？

最好的桶填充算法是什么？

并回顾讨论在这里：

https://en.wikipedia.org/wiki/Flood_fill

ProfDFrancis
2023-02-26

浏览器有限制，其中之一就是堆栈大小，这不仅仅是画布上的问题，任何像您这样的使用递归函数的应用程序都有达到该限制的风险。

一种解决方法是使用 setTimeout ，请参阅以下示例： 

const canvas = document.querySelector('.canvas')
const ctx = canvas.getContext('2d')
canvas.width = canvas.height = 400
ctx.strokeRect(8, 8, 100, 100)
ctx.strokeRect(80, 80, 240, 240)

const setColor = (imageData, pixelPos) => {
  imageData.data[pixelPos] = 0
  imageData.data[pixelPos + 1] = 255
  imageData.data[pixelPos + 2] = 0
  imageData.data[pixelPos + 3] = 255
  ctx.putImageData(imageData, 0, 0)
}

const checkNear = (pixelPos, imageData, oldColor, newColor) => {
  floodFill(pixelPos - canvas.width * 4, imageData, oldColor, newColor)
  floodFill(pixelPos + canvas.width * 4, imageData, oldColor, newColor)
  floodFill(pixelPos - 4, imageData, oldColor, newColor)
  floodFill(pixelPos + 4, imageData, oldColor, newColor)
}

const floodFill = (pixelPos, imageData, oldColor, newColor) => {
  if (
    imageData.data[pixelPos] === oldColor.r &&
    imageData.data[pixelPos + 1] === oldColor.g &&
    imageData.data[pixelPos + 2] === oldColor.b &&
    imageData.data[pixelPos + 3] === oldColor.a
  ) {
    setColor(imageData, pixelPos)
    setTimeout(() => checkNear(pixelPos, imageData, oldColor, newColor), 1)
  }
}

addEventListener('mousedown', e => {
  const rect = canvas.getBoundingClientRect(),
    x = Math.floor(e.x - rect.x),
    y = Math.floor(e.y - rect.y)

  if (x < 0 || y < 0 || x > canvas.width || y > canvas.height) return

  let imageData = ctx.getImageData(0, 0, canvas.width, canvas.height)
  const pixelPos = (y * canvas.width + x) * 4
  const oldColor = {
    r: imageData.data[pixelPos],
    g: imageData.data[pixelPos + 1],
    b: imageData.data[pixelPos + 2],
    a: imageData.data[pixelPos + 3],
  }
  const newColor = {
    r: 0,
    g: 255,
    b: 0,
    a: 255,
  }

  floodFill(pixelPos, imageData, oldColor, newColor)
})
<canvas class="canvas"></canvas>

另一种选择是使用后台工作者：
https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers

但来自 @Eureka 的答案是正确的，你的算法效率不高，你也应该解决这个问题以提高整体性能

Helder Sepulveda
2023-02-26