Question 44873 in Html Question posted in
Some basic documentation can be found here.

JavaScript Flood Fill RangeError – Html

I’m developing a painting application with JavaScript and I need to add a paint bucket tool as well. For this, I did research on the internet and implemented an algorithm I found in my code, but this algorithm revealed an error in my code. When the area to be painted is large, I get Uncaught RangeError: Maximum call stack size exceeded.

Screenshot:

Screenshot

My test code:

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>
Tags:

2

Answers


  1. 0

    Your "flood fill" algorithm is correct in principle, but hopeless in practice

    It works on the basis of:

    • colour in a pixel
    • then go to each of the 4 neighbouring pixels, and call the same function again

    The problem with this approach is that an astronomical number of calls are required to complete the flood fill.

    Try some other approaches to flood fill:

    which flood-fill algorithm is better for performance?

    What's the best bucket filling algorithm?

    And review the discussion here:

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

    Login or Signup to reply.
  2. 0

    Browsers have limits, one of them is the stack size, and this is not just an issue on the canvas, any application like yours that uses recursive functions runs the risk of hitting that limit.

    One way around is to use setTimeout, see sample below:

    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>

    Another option could be using background workers:
    https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers

    But the answer from @Eureka is spot on, your algorithm is not very efficient, you should also address that issue to improve overall performance

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search