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.