What is the best "bucket-fill" algorithm?

Question

I'm pretty new to image processing, and I am currently working on a paint-like application that will feature a bucket-fill. However, I have no idea what the best algorithm for a bucket-fill is.

I implemented an example I found from this site, however, it ran into infinite loop problems when a user tried to bucket-fill an area that had already been bucket-filled with the same color.

I'm currently working around that problem by filling left, right, up and then down; however, I made it so that once a pixel has been filled in to the left, it cannot fill to the right, which means shapes such as:

Example

will not be filled properly if the bucket tool is used at the red dot.

Therefore, I am hoping someone knows of an algorithm or a link to one that will resolve all these issues.

Additional Information: This will be implemented using Javascript as the paint tool. It will be used online utilizing the Canvas element.

• Demian Brecht: Is this vector or bitmap based? I'm assuming bitmap by the image, but just making sure..
• RLH: I think you've implemented something incorrectly. I skimmed the document and according to the image examples, this should fill images like the one above. Did you copy and paste his code, or did you re-write it?
• Bwmat: Think graph traversal.
• Ivan: @RLH: I copy and pasted his code with a few changes in order to make it work with my set up.
• Doc Brown: @Ivan: don't start to search for a new algo before you got your "infinite loop" problems solved. If can not even fix that for an existing implementation, you will definitely run into much more trouble when you are going to rewrite the whole thing from scratch.

Answer 1

It sounds like you're actually looking for whats called a Flood Fill algorithm. That may be why you havent found tons of examples for it. There's several Flood Fill methods listed on the Wikipedia page for the algorithm. I highly recommend one of the non-recursive, 'queued' methods.

• Elfayer: I highly recommend one of the non-recursive, 'queued' methods. - Could you explain why?
• boxcartenant: @Elfayer Every time a function is called (say "X()" has a call to "Y()"), the parameters and memory location from the originating function ("X()") are stored on the stack. So, if you're filling a large and complicated space, then there will be a lot of recursive function calls. Depending on your compiler and language, this can lead to stack overflows or excessive memory consumption.

Answer 2

I'm currently doing the same thing. However, when I ran into the issue you point out, I opted for simply ending the function if the tool was clicked over an area of the same color you're trying to paint (this also seems to be the behavior of ms-paint).

The queued method should be extremely intuitive for anyone with some programming experience.

If painting the area surrounding a spot of the same color as your paint is a concern, one you could:

• check for background color.
• search for the edge of the same-colored spot you clicked at.
• queue the surrounding points to the spot.
• proceed with normal execution using this (in this case) white-dot filled queue.

If you wish you can take a look at my (quite embarrasing) code here.

It's far from being fast but it works fine...

• Juan Pablo Alvarez Alfaro: Why the downvotes? :( I know the method isn't particularly "fast", but it works, and also does the proposed solution :(
• gnat: this post is rather hard to read (wall of text). Would you mind editing it into a better shape?
• TtT23: Seriously? People mass down voted because it was hard to read? Why not opt to edit? It's not like the content is problematic.
• gnat: @l46kok 'There are other reasons to downvote something, but "hard to read" is legit. This isn't some grade-school essay contest...'