JavaScript Flood Fill RangeError

Question

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:

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>

Answer 1

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