DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 968,873 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for Flood Fill algorithm: A graphical step-by-step explanation of the paint bucket
crayoncode
crayoncode

Posted on

Flood Fill algorithm: A graphical step-by-step explanation of the paint bucket

Finally (πŸŽ‰πŸŽ†) I was able to put the idea of illustrating bits of my knowledge and create Youtube videos from it into practice and therefore πŸ–οΈcrayon codeπŸ–οΈ was born.
Today I'd like to share this episode on the Flood Fill algorithm with all the friendly people on dev.to. I'm grateful for any kind of feedback - especially on the video itself and of course on anything else you like or think could use improvement.

Below you can watch the video as well as read the transcript with selected frames from the illustration.

Flood Fill is a simple implementation of what makes the paint bucket work in graphics software. It can be implemented in basically two ways: Recursively and iteratively. In this episode we're going to cover the iterative version, which will also make use of the queue data structure.

Schema of recursive and iterative implementation

All flood fill needs, is

  • an image to work on
  • a so called seed which is simply the x and y coordinates for instance where paint bucket was clicked
  • and a fillColor which we'll pour over the image.

Flood fill signature

So, imagine having a nice little image with different color patches. The marked pixel of the white patch is the seed, because that's where the user clicked.
Now, the goal of the Flood Fill algorithm is to find all pixels which have the same color as the seed pixel and which are also connected to it.

Seed and seed color

Right at the beginning, the seed pixel is a quite important one as it defines the so called seedColor. Only neighboring pixels that have the same color as the seed color are seen as part of the area to be filled. Non-adjacent pixels of different colors are therefore ignored.

With a queue we'll keep track of the neighboring pixels that need to be looked at next. So the first pixel that needs to be looked at is the seed pixel itself. Which is why it's the first one to be added to the queue.

Alt Text

Now, by using a while loop we'll work our way through the image, which means that as long as there are pixels in the queue, we'll keep processing them.

The pixel currently being looked at is stored in the variable called current. So we change the color of the current pixel to the new fill color and start expanding to the neighboring pixels. This simply means that we add the four adjacent pixels east, south, west and north to the queue.

Alt Text

And from there on it's literally just repeating that over and over, which means that all pixels in the queue are colored one after another and expanded to their respective neighbors.

However, one piece of logic is still missing. In case the current pixel is pointing at a pixel that does not match the seed color, this pixel is neither colored nor expanded to its neighbors, which is the reason why the loop is simply continued without further action. That way it's ensured that the algorithm does not cross over to areas that do not match the seed color.

Alt Text

Now, you may have wondered, why the diagonal neighbors like south-east and north-west are not taken into acount. This final situation shows perfectly well, why. If the south-eastern neighbor would be taken into account, flood fill would be able to cross through the diagonal border, causing it to flood more image areas than actually desired.

Alt Text

Top comments (0)

"I made 10x faster JSON.stringify() functions, even type safe"

☝️ Must read for JS devs