I took the longest time implementing the fill tool 
on Mandalagaba. How hard could it be? Recurse through pixels looking for a color and update them to a new color.
While this method certainly works and is easy to implement, it is also extremely slow. Slow in a way that hangs the browser, yielding infamous messages from the browser.
Here we’ll take a look at various Javascript flood fill implementations along with their drawbacks. Jump to #4 if you are only interested in the best one.
2018-10-04 – edit – added fill algorithm #5 which proposes an alternate approach to filling pixel by pixel. Depending on your project it may or may not serve your needs better.
In all cases, the code is available in the example iframe, look for the function flood_fill.
1. Simple Recursive
Not much to explain here, we simply recursively call the function on adjacent pixels when they match the color we are trying to fill over.
Click to change color / pop-out link
It’s reasonably fast but the problem with this one is that any fill area slightly large yields too much recursion which breaks subsequent JS. This Canvas box is 200x200px and at 300x300px, Firefox complained about:
It’s easy to see how this implementation will not satisfy a reasonably featured paint program. Even if your browser let you stack more function on the heap, I would bet it would lead to slowness.
2. Iterative
We simply take the previous idea of looking at adjacent pixels and filling them, and make it iterative instead so the function calls don’t get stacked to a ceiling.
Click to change color / pop-out link
The problem with this is is that is is sloooow. So slow it stalls browser. Most of time is spent having to keep track of pixels_stack. Recursion doesn’t have that need but as we’ve seen, it has other issues.
3. Recursive-Iterative (AKA catch-your-breath iterative)
This is a twist on #2 which every so often, recurses on itself via a setTimeout to let the browser catch it breath a little. It also yields a cool visual effect.
Click to change color / pop-out link
I really like the visual effect, and it makes the slowness tolerable. But the issue is that Mandalagaba has a network engine and allows for re-rendering of one’s work. So synchronization is a big deal, and you know what makes synchronization easy? Not having to worry about it.
So as long as I can help it, my life is a lot easier if the operations the users can perform are atomic. Operations need to be able to be processed one after the other counting on the fact that the ones that came before have completed.
The first 2 solutions are atomic but suck; this 3rd one, however cool it may be, isn’t.
4. The Holy Grail
I’m not sure where this algorithm originated from, but I’ve gotten to know it on this web page which explains it very well (with GIFs!). It is iterative and goes about finding pixels to fill in a much smarter way.
Click to change color / pop-out link
That’s it, no drawback here 🙂 I’ve tested it on large canvasses and this is what is implemented on Mandalagaba. Now of course, in a real application there is a ton more complexity dealing with smoothing edges and blending alpha. I only wanted to expose boiled down versions of these algorithms so they are easier to wrap your mind around.
5. The Holier Grail?
While #4 is fastest algorithm for filling pixel by pixel, I found myself in the need to have a fill operation in for form of a path which is filled with the native HTML5 canvas capabilities. This algorithm is a bit different from all the other ones in that it doesn’t go through every pixel and fills it. What it does is pathfinding to draw the outline of the shape of be filled, and then simply calls the native canvas fill() function. It does come with certain drawbacks and so I wouldn’t recommend it unless you specifically need this sort of approach.
Click to change color / pop-out link
Feel free to ask questions in the comments.
Using your code, I have been able to create an animated map to track my travels. Something I’ve wanted to do for a long time. Thank you!
Thank you 🙂 always good to know it’s helpful to others.
Have you considered trying web-workers to offload the pixel filling computations to a separate thread?
https://developer.mozilla.org/en-US/docs/Web/API/Web_Workers_API/Using_web_workers
I’m about to create my own version of the bucket fill effect and, since pixel manipulation in the canvas revolves around manipulating a pixel array, you can offload the compuationally intensive workload to a web-worker so that the main JS thread doesn’t hang. I’ve tried this before with various other image manipulation algorithms and it works very well. 🙂
I never considered it even though it’s painfully obvious :). I’ve actually done work with web workers so they’re not foreign in the least. Thank you for pointing it out :).
Regardless, I think it’s still worth trying to find something computationally efficient, which yields quick feedback to a user.
May I ask what cool project you’re working on?
Hey, thanks for the post.
Just wanted to tell you that approach 5 is broken. It leaves the outlines behind every time that you fill again. So the area that actually gets filled becomes smaller and smaller.
You’re right, it’s a known issue having to do with transparency on the edges of drawn paths. The issue is that when you draw a path, it comes with some transparency on the edges (for smoothing), and this builds up the more you do it because the color matching is thus made inexact at these locations.
This algorithm also has a few pathfinding quirks :). It’s super specific and I don’t recommend using it unless you specifically need to fill using canvas paths. In my implementation on Mandalagaba, I keep track of path borders separately so I don’t have the build up issue. Here I distilled the algorithm to its simplest form and so it doesn’t have the extra complexity needed to avoid this build-up issue.
Thanks for taking the time to let me and other readers know about it. What are you working on? 🙂