A recursive approach to filling empty space on a canvas using Javascript

Question

A recursive approach to filling empty space on a canvas using Javascript

My goal was to develop a recursive function that would continue filling the empty spaces of a canvas until reaching the edges or encountering a different colored space.

function createFillingPoint() {
  let x = points[0][0],
    y = points[0][1];
  var pattern = ctx.getImageData(x, y, 1, 1).data;
  var colorToChange = rgbToHex(pattern);
  ctx.fillRect(x, y, 1, 1);
  colorFillRec(x + 1, y, width.value, height.value, colorToChange);
  colorFillRec(x - 1, y, width.value, height.value, colorToChange);
  colorFillRec(x, y + 1, width.value, height.value, colorToChange);
  colorFillRec(x, y - 1, width.value, height.value, colorToChange);
}

This particular function initializes the starting point and identifies the original color to be changed throughout the recursion.

function colorFillRec(x, y, w, h, colorToChange) {
  if (
    x > w ||
    x < 0 ||
    y > h ||
    y < 0 ||
    rgbToHex(ctx.getImageData(x, y, 1, 1).data) != colorToChange
  )
    return;
  ctx.fillRect(x, y, 1, 1);
  colorFillRec(x + 1, y, w, h, colorToChange);
  colorFillRec(x - 1, y, w, h, colorToChange);
  colorFillRec(x, y + 1, w, h, colorToChange);
  colorFillRec(x, y - 1, w, h, colorToChange);
}

This is the core recursive function. Both functions compare colors and halt execution if they differ from the original color.

Despite my attempts to run the function, I encountered the "Maximum call stack size exceeded" error... I struggled to come up with an alternative solution for achieving the desired outcome (whether through another recursive approach or not) but couldn't find one.

javascript vue.js recursion canvas html5-canvas

Answer 1

Answer №1

To optimize your code, consider using an explicit stack instead of relying on the call stack. Additionally, it will be more efficient to call getImageData just once for the entire canvas area, manipulate the image data, and then update the canvas with putImageData in a single operation.

Check out this demonstration:

function drawShapes(ctx) { // Create some shapes for demonstration purposes
    function rectangle(x, y, width, height, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.rect(x, y, width, height);
        ctx.fill();
    }

    function circle(x, y, radius, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.arc(x, y, radius, 0, Math.PI * 2);
        ctx.fill();    
    }

    rectangle(0, 0, 600, 180, "pink");
    rectangle(100, 20, 200, 40, "red");
    rectangle(50, 40, 100, 30, "blue");
    circle(160, 95, 30, "green");
    rectangle(170, 30, 5, 80, "pink");
    rectangle(190, 25, 100, 10, "white");
    circle(150, 110, 10, "white");
}

// The main flood-fill algorithm
function executeFloodFill(ctx, x, y, r, g, b, a=255) {

    function matchColor(index, source) {
        for (let j = 0; j < 4; j++) {
            if (imageData.data[index + j] !== source[j]) return false;
        }
        return true;
    }
    
    function setColor(index, target) {
        for (let j = 0; j < 4; j++) {
            imageData.data[index + j] = target[j];
        }
    }
    
    const {width, height} = ctx.canvas;
    const imageData = ctx.getImageData(0, 0, width, height);
    const startIndex = (y * width + x) * 4;
    const lineSize = width * 4;
    const maxIndex = lineSize * height;
    
    const sourceColor = [...imageData.data.slice(startIndex, startIndex+4)];
    const targetColor = [r, g, b, a];
    
    // Exit early if the starting pixel already has the target color
    if (sourceColor.every((value, idx) => value === targetColor[idx])) return;
    
    // Utilize an explicit stack
    const pixelStack = [startIndex];
    while (pixelStack.length) {
        const currentIndex = pixelStack.pop();
        if (!matchColor(currentIndex, sourceColor)) continue;
        setColor(currentIndex, targetColor);
        if (currentIndex < maxIndex - lineSize)      pixelStack.push(currentIndex + lineSize);
        if (currentIndex >= lineSize)                 pixelStack.push(currentIndex - lineSize);
        if (currentIndex % lineSize < lineSize - 4)   pixelStack.push(currentIndex + 4);
        if (currentIndex % lineSize >= 4)              pixelStack.push(currentIndex - 4);
    }
    ctx.putImageData(imageData, 0, 0);
}

const context = document.querySelector("canvas").getContext("2d");
drawShapes(context);
// Start the flood-fill after a 2-second delay
setTimeout(function () {
    executeFloodFill(context, 0, 0, 120, 80, 0, 255); // Fill from point (0, 0) with brown color
}, 2000);

<canvas width="600" height="180"></canvas>

This demonstration creates a sample drawing and initiates a flood-fill operation from the coordinates (0, 0). This means that it will identify connected pixels matching the color at (0, 0) and change them to brown.

Note that the default canvas color is black with full transparency (alpha = 0). Therefore, initiating a flood-fill from a pixel with the default value (rgba = 0,0,0,0) will only affect pixels with that exact rgba code, not ones set to white (255,255,255,255).

Answer 2

To optimize your code, consider using an explicit stack instead of relying on the call stack. Additionally, it will be more efficient to call getImageData just once for the entire canvas area, manipulate the image data, and then update the canvas with putImageData in a single operation.

Check out this demonstration:

function drawShapes(ctx) { // Create some shapes for demonstration purposes
    function rectangle(x, y, width, height, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.rect(x, y, width, height);
        ctx.fill();
    }

    function circle(x, y, radius, color) {
        ctx.fillStyle = color;
        ctx.beginPath()
        ctx.arc(x, y, radius, 0, Math.PI * 2);
        ctx.fill();    
    }

    rectangle(0, 0, 600, 180, "pink");
    rectangle(100, 20, 200, 40, "red");
    rectangle(50, 40, 100, 30, "blue");
    circle(160, 95, 30, "green");
    rectangle(170, 30, 5, 80, "pink");
    rectangle(190, 25, 100, 10, "white");
    circle(150, 110, 10, "white");
}

// The main flood-fill algorithm
function executeFloodFill(ctx, x, y, r, g, b, a=255) {

    function matchColor(index, source) {
        for (let j = 0; j < 4; j++) {
            if (imageData.data[index + j] !== source[j]) return false;
        }
        return true;
    }
    
    function setColor(index, target) {
        for (let j = 0; j < 4; j++) {
            imageData.data[index + j] = target[j];
        }
    }
    
    const {width, height} = ctx.canvas;
    const imageData = ctx.getImageData(0, 0, width, height);
    const startIndex = (y * width + x) * 4;
    const lineSize = width * 4;
    const maxIndex = lineSize * height;
    
    const sourceColor = [...imageData.data.slice(startIndex, startIndex+4)];
    const targetColor = [r, g, b, a];
    
    // Exit early if the starting pixel already has the target color
    if (sourceColor.every((value, idx) => value === targetColor[idx])) return;
    
    // Utilize an explicit stack
    const pixelStack = [startIndex];
    while (pixelStack.length) {
        const currentIndex = pixelStack.pop();
        if (!matchColor(currentIndex, sourceColor)) continue;
        setColor(currentIndex, targetColor);
        if (currentIndex < maxIndex - lineSize)      pixelStack.push(currentIndex + lineSize);
        if (currentIndex >= lineSize)                 pixelStack.push(currentIndex - lineSize);
        if (currentIndex % lineSize < lineSize - 4)   pixelStack.push(currentIndex + 4);
        if (currentIndex % lineSize >= 4)              pixelStack.push(currentIndex - 4);
    }
    ctx.putImageData(imageData, 0, 0);
}

const context = document.querySelector("canvas").getContext("2d");
drawShapes(context);
// Start the flood-fill after a 2-second delay
setTimeout(function () {
    executeFloodFill(context, 0, 0, 120, 80, 0, 255); // Fill from point (0, 0) with brown color
}, 2000);

<canvas width="600" height="180"></canvas>

This demonstration creates a sample drawing and initiates a flood-fill operation from the coordinates (0, 0). This means that it will identify connected pixels matching the color at (0, 0) and change them to brown.

Note that the default canvas color is black with full transparency (alpha = 0). Therefore, initiating a flood-fill from a pixel with the default value (rgba = 0,0,0,0) will only affect pixels with that exact rgba code, not ones set to white (255,255,255,255).

A recursive approach to filling empty space on a canvas using Javascript

Answer №1

Similar questions

Develop an Angular resolver that can be utilized across various scenarios

Exploring the concept of global objects within the expressjs framework

Having trouble setting a background image for a specific DIV element in HTML

Implementing a pop-up notification at the center of the display for empty fields

click event to activate delayed function in dropdown

What is the best way to locate the nearest marker using the Google Maps Direction Service?

Enhancing data management with Vuex and Firebase database integration

Using CSS nth-of-type on the same level of the DOM allows for specific

How about checking the memory usage in Javascript?

Creating an expand and collapse animation in a `flex` accordion can be achieved even when the container size is fixed using

Achieving the functionality of making only one list item in the navbar bolded upon being clicked using React and Typescript logic

Mastering Checkbox State Control in Vue3 Using Component Props

Update the JSON data following deletion

When refreshing the page, redux-persist clears the state

Challenge in Decision Making

Passing data between child components using Vuejs 3.2 for seamless communication within the application

Menus that mimic the style of Google Translate's select options

Quasar Framework Vue.js project experiencing unexpected disablement of console/debug output in PWA InjectManifest workbox

Ways to send users to a different page with parameters without relying on cookies

Tips on choosing filters and leveraging the chosen value for searching in a Vue application