Challenges in implementing floodfill algorithm pseudocode

Question

Challenges in implementing floodfill algorithm pseudocode

I've been working on implementing the flood fill algorithm pseudocode that I found in Graphics Gemes 1.
Here is the pseudocode:

https://i.stack.imgur.com/X6jV4.png

Unfortunately, when I translated it to JavaScript and used my floodfill tool, it caused my code to hang. Here's a snippet of the code I used:

function inside(x, y) {
    const q = 4 * (x + y * that.w);
    const color = [img.data[q], img.data[q + 1], img.data[q + 2], img.data[q + 3]];
    return color[0] === toolColor[0] &&
        color[1] === toolColor[1] &&
        color[2] === toolColor[2];
}

function set(x, y) {
    const q = 4 * (x + y * that.w);
    img.data[q] = that.color.r;
    img.data[q + 1] = that.color.g;
    img.data[q + 2] = that.color.b;
    img.data[q + 3] = that.color.a;
}

// More code....

<p><code>img.data is an array displayed in the browser.

toolColor contains the colors for the area to be filled.

I'm struggling with why the algorithm only fills part of the area.

If you need more code details, feel free to ask.
Edit: After some updates, the code now partially fills the area.

https://i.stack.imgur.com/THPTh.png

javascript graphics 2d implementation flood-fill

Answer 1

Answer №1

After some modifications, the code is now optimized for speed. Hopefully, it can be useful to someone.

Check out the updated code below:

function inside(x, y) {
    const q = 4 * (x + y * that.w);
    const color = [img.data[q], img.data[q + 1], img.data[q + 2], img.data[q + 3]];
    return color[0] === toolColor[0] &&
        color[1] === toolColor[1] &&
        color[2] === toolColor[2];
}

function set(x, y) {
    const q = 4 * (x + y * that.w);
    img.data[q] = that.color.r;
    img.data[q + 1] = that.color.g;
    img.data[q + 2] = that.color.b;
    img.data[q + 3] = that.color.a;
}

function doFloodFill(x, y) {
    let skip = false, x1, x2, dy, start;
    const s = [];

    s.push([y, x, x, 1]);
    s.push([y + 1, x, x, -1]);

    while (s.length > 0) {
        const n = s.pop();
        y = n[3] + n[0];
        x1 = n[1];
        x2 = n[2];
        dy = n[3];
        x = x1;
        while (x >= 0 && inside(x, y)) {
            set(x, y);
            x--;
        }
        if (x >= x1) {
            //skip
            skip = true;
        }
        if (!skip) {
            start = x + 1;
            if (start < x1) {
                s.push([y, start, x1 - 1, -dy]);
            }
            x = x1 + 1;
        }
        do {
            if (!skip) {
                while (x <= that.w && inside(x, y)) {
                    set(x, y);
                    x++;
                }
                s.push([y, start, x - 1, dy]);
                if (x > x2 + 1) {
                    s.push([y, x2 + 1, x - 1, -dy]);
                }
            }
            //skip
            x++;
            while (x <= x2 && !inside(x, y)) {
                x++;
            }
            start = x;
            skip = false;
        } while (x < x2);
    }
}

There was a minor error in the previous version. The skip value should have been within the last loop instead of outside.

In addition, the initialization of the y value in the loop was incorrect. It should be: y = n[3] + n[0]; rather than y = n[0];

It seems that the code on English Wikipedia regarding this algorithm may contain inaccuracies.

I conducted speed tests on this algorithm. My implementation performs approximately 1.5 times faster compared to the code found on Wikipedia.

Answer 2

After some modifications, the code is now optimized for speed. Hopefully, it can be useful to someone.

Check out the updated code below:

function inside(x, y) {
    const q = 4 * (x + y * that.w);
    const color = [img.data[q], img.data[q + 1], img.data[q + 2], img.data[q + 3]];
    return color[0] === toolColor[0] &&
        color[1] === toolColor[1] &&
        color[2] === toolColor[2];
}

function set(x, y) {
    const q = 4 * (x + y * that.w);
    img.data[q] = that.color.r;
    img.data[q + 1] = that.color.g;
    img.data[q + 2] = that.color.b;
    img.data[q + 3] = that.color.a;
}

function doFloodFill(x, y) {
    let skip = false, x1, x2, dy, start;
    const s = [];

    s.push([y, x, x, 1]);
    s.push([y + 1, x, x, -1]);

    while (s.length > 0) {
        const n = s.pop();
        y = n[3] + n[0];
        x1 = n[1];
        x2 = n[2];
        dy = n[3];
        x = x1;
        while (x >= 0 && inside(x, y)) {
            set(x, y);
            x--;
        }
        if (x >= x1) {
            //skip
            skip = true;
        }
        if (!skip) {
            start = x + 1;
            if (start < x1) {
                s.push([y, start, x1 - 1, -dy]);
            }
            x = x1 + 1;
        }
        do {
            if (!skip) {
                while (x <= that.w && inside(x, y)) {
                    set(x, y);
                    x++;
                }
                s.push([y, start, x - 1, dy]);
                if (x > x2 + 1) {
                    s.push([y, x2 + 1, x - 1, -dy]);
                }
            }
            //skip
            x++;
            while (x <= x2 && !inside(x, y)) {
                x++;
            }
            start = x;
            skip = false;
        } while (x < x2);
    }
}

There was a minor error in the previous version. The skip value should have been within the last loop instead of outside.

In addition, the initialization of the y value in the loop was incorrect. It should be: y = n[3] + n[0]; rather than y = n[0];

It seems that the code on English Wikipedia regarding this algorithm may contain inaccuracies.

I conducted speed tests on this algorithm. My implementation performs approximately 1.5 times faster compared to the code found on Wikipedia.

Challenges in implementing floodfill algorithm pseudocode

Answer №1

Similar questions

"Implementing a comment system using Node.js and MySQL: A comprehensive guide

Exploring the connections between Ajax, asp.net mvc3 routing, and navigating relative URLs

Apply Jquery to add emphasis to every item on the list

Altering the backdrop upon hovering over an element

Are there any other options similar to PhantomJs that offer support for CSS 3D effects?

displaying 'undefined' upon completion of iterating through a JSON file using $.each

Transferring data from a callback function within a component to a different component

Encountering Internal Server Error when running Node-Express app on render.com with query parameters live

ReactJS: Dealing with issues in setting a dynamic index for the setState key

Delay the next loop iteration until receiving an HTTP request

Using React.js to select and change the color of an element

How to find the length of an array in Node.js without utilizing JQuery

Keycloak does not support using the updateToken() function within an asynchronous function

Updating a property on an object during iteration

Troubleshooting the onExited callback issue with Popover component in Material UI

Is it possible to implement a custom sign-in form for AWS Cognito?

Obtaining Input Field Value in Angular Using Code

Implementing a Vue.js v-bind:style attribute onto a dynamically generated element post-page initialization

Exploring the functionality of placeholders within jQuery

Passport JS allows you to create a secure login form that redirects users to different URIs based on their role