Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

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
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 '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
add comment

1 Answer

up vote 13 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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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