Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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:


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.

share|improve this question
Is this vector or bitmap based? I'm assuming bitmap by the image, but just making sure.. – Demian Brecht Sep 3 '11 at 0:45
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? – RLH Sep 3 '11 at 0:56
Think graph traversal. – Bwmat Sep 3 '11 at 1:54
@RLH: I copy and pasted his code with a few changes in order to make it work with my set up. – Ivan Sep 3 '11 at 5:10
@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. – Doc Brown Sep 3 '11 at 9:39
up vote 19 down vote accepted

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.

share|improve this answer

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...

share|improve this answer
Why the downvotes? :( I know the method isn't particularly "fast", but it works, and also does the proposed solution :( – Juan Pablo Alvarez Alfaro Mar 3 '15 at 13:35
this post is rather hard to read (wall of text). Would you mind editing it into a better shape? – gnat Mar 3 '15 at 13:36
Seriously? People mass down voted because it was hard to read? Why not opt to edit? It's not like the content is problematic. – l46kok Mar 5 '15 at 3:18

protected by gnat Mar 3 '15 at 13:36

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.