17

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.

Improve this question
5
  • Is this vector or bitmap based? I'm assuming bitmap by the image, but just making sure..
    – Demian Brecht
    Sep 3, 2011 at 0:45
  • 1
    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, 2011 at 0:56
  • Think graph traversal.
    – Bwmat
    Sep 3, 2011 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, 2011 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, 2011 at 9:39

2 Answers 2

Reset to default
21

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.

Improve this answer
2
  • I highly recommend one of the non-recursive, 'queued' methods. - Could you explain why?
    – Elfayer
    Mar 30, 2019 at 15:46
  • 1
    @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.
    – boxcartenant
    Nov 15, 2019 at 22:42
-1

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

Improve this answer
4

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