Coloring HTML5 canvas regions on mouse over – Part 2

As promised, here comes the actual region recognition algorithm – flood fill – and my js implementation of it. I enclosed all the logic related to it in the PixelMatrix class, so that we have all the pieces required for the functionality mentioned in the first post, in one place. The name comes from the fact that all of the PixelMatrix code is doing its work on a two-dimensional array which is a representation of the canvas pixel data.

There are two most importants methods here: restoreRegions and recalculate. The first one takes a data parameter which is this one, huge, flat array of pixels you get from the canvas context’s getImageData. The implementation looks like this:

restoreRegions(data) {
    let currentColor = this._originalColor;

    this._recalculate(data);

    for (let y = 0; y < this._matrix.length; y++) {
        for (let x = 0; x < this._matrix[y].length; x++) {
            if (this._matrix[y][x] !== this._originalColor) {
                continue;
            }

            this._colorRegion(x, y, currentColor);

            currentColor++;
        }
    }
}

First, we assign the mutable currentColor variable with the original color which is the initial value passed to the constructor. Why am I not just initializing it here to, say, zero? Well in my implementation colors are just one-digit numbers, but it’s easy to change it all to use actual hex values. That way there won’t be a need to map a color number to the actual color in the PageManager class. I thought leaving it as an option would be fine, even thought keeping a gigantic 2d string array in memory is worse than having it as a number array :). As for the recalculate method – it’s building the initial version of our 2d in-memory representation of pixel data. We’ll get back to its definition in a moment.

After this initial matrix setup we go into iterating over the pixel data starting from the top and going to the right in each row. If the pixel encountered is different from the original color, it means it’s a transparency (it will become clear after you see the recalculate method implementation), which in turn means, we won’t do anything to it.

Next we hit the colorRegion method, definition below:

_colorRegion(x, y, targetColor) {
    const queue = [[x, y]];
    const uniqueChecker = {};

    while (queue.length > 0) {
        const current = queue.shift();
        const neighbours = this._getNeighbours(current[0], current[1], targetColor);

        this._matrix[current[1]][current[0]] = targetColor;

        for (let i = 0; i < neighbours.length; i++) {
            if (uniqueChecker[neighbours[i][0] + ':' + neighbours[i][1]] === true) {
                continue;
            }

            uniqueChecker[neighbours[i][0] + ':' + neighbours[i][1]] = true;

            queue.push(neighbours[i]);
        }
    }
}

The queue const holds a list of x, y pixel coordinates that is used to fill parts of the previously buit matrix with a color and the uniqueChecker const is used as a hash map in order to be able to quickly determine if the algorithm has already visited a given pixel and not push it onto the queue one more time, because that would cause and infinite loop (queue’s length would never go down to zero).

And now we go into the body of the while loop. It’s taking the first item from the queue, calculating it’s immediate neighbors, coloring it’s pixel in the matrix and then adding the neighbors to the queue so that all the adjacent pixels are colored properly. The code behind getNeighbours is simpler than you may think, so I won’t be posting and explaining it here – you can find it in the github repo.

One last piece of code I wanted to discuss is the recalculate method. Again – not that hard, but I thought it may be a little bit harder to understand than the other methods, which I skipped.

_recalculate(data) {
    this._matrix = [];

    for (let i = 0; i < data.data.length; i += data.width * 4) {
        const slice = data.data.slice(i, i + (data.width * 4));
        const row = [];

        for (let j = 0; j < slice.length; j += 4) {
            row.push(slice[j + 3] < 128 ? this._transparency : this._originalColor);
        }

        this._matrix.push(row);
    }
}

Remember that the data variable holds the original canvas pixel data (flat array) ? Yup, so this method is used to transform the one-dimensional representation of coords and colors into a two-dimensional representation of color symbols, where the matrix indices are actual pixel positions. To go into a bit more detail about the original data: say you have a 2x2px image filled with white color (red: 255, green: 255, blue: 255, alpha: 255). The first pixel (0,0 coord) consists of the values ranging from the index 0 to 3 (inclusive) in the array, the second (0, 1) goes from 4 to 7 and so on. That’s why all those weird-looking calculations and multiplications by 4 are here. The other piece that may surprise you is the ternary expression checking if a value is less than 128. Well, after some experimentation I found out that the coloring looks the smoothest when I treat pixels with alpha value less than 128 as fully transparent and the other ones as non-transparent. It might be a subject of some optimizations if we want the coloring to look very smooth, but in my case it was good enough.

So that’s it! You can find the github repo URL below, let me know what you think and see you next time! 🙂

https://github.com/mostlyunity/flood-fill

EDIT:
One thing that just came to my mind is that some of you may think of the findRegionWithColor method as being not as performant as it could be. Well duh… 🙂 One optimization that pops up immediately is that I could create a map of color: region, thus eliminating the need to iterate over the whole matrix time and time again, just to find a specific region. Actually that’s how it works in the production code, but in this solution I was trying to keep everything to minimum – as the best place for the cache creation is during regions’ restore process, I didn’t want to clutter the code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s