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.
-
Is this vector or bitmap based? I'm assuming bitmap by the image, but just making sure..Demian Brecht– Demian Brecht09/03/2011 00:45:48Commented Sep 3, 2011 at 0:45
-
1I 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– RLH09/03/2011 00:56:42Commented Sep 3, 2011 at 0:56
-
Think graph traversal.Bwmat– Bwmat09/03/2011 01:54:37Commented 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– Ivan09/03/2011 05:10:59Commented 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– Doc Brown09/03/2011 09:39:14Commented Sep 3, 2011 at 9:39
2 Answers 2
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.
-
I highly recommend one of the non-recursive, 'queued' methods.
- Could you explain why?Elfayer– Elfayer03/30/2019 15:46:48Commented 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– boxcartenant11/15/2019 22:42:37Commented Nov 15, 2019 at 22:42
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...
-
Why the downvotes? :( I know the method isn't particularly "fast", but it works, and also does the proposed solution :(Juan Pablo Alvarez Alfaro– Juan Pablo Alvarez Alfaro03/03/2015 13:35:00Commented Mar 3, 2015 at 13:35
-
1
-
2Seriously? People mass down voted because it was hard to read? Why not opt to edit? It's not like the content is problematic.TtT23– TtT2303/05/2015 03:18:48Commented Mar 5, 2015 at 3:18
-
2@l46kok 'There are other reasons to downvote something, but "hard to read" is legit. This isn't some grade-school essay contest...'gnat– gnat03/05/2015 17:40:40Commented Mar 5, 2015 at 17:40