Click here to Skip to main content
15,886,055 members
Search within:


Articles / Desktop Programming / MFC
 

QuickFill: An Efficient Flood Fill Algorithm

Rate me:
Please Sign up or sign in to vote.
4.84/5 (71 votes)
12 Mar 200413 min read 526.5K   12K   103  
Design and implementation of efficient flood fill algorithms.
 
1 * Start) G( 1, 7 ), 
 PopLine( 0 ) {
2 * FindLeft() G( 1, 7 ), G( 0, 7 ), FindRight() G( 1, 7 ), G( 2, 7 ), Draw() D( 1, 7 ), 
}
PopLine( 0 ) {
3 * FindLeft() G( 1, 6 ), G( 0, 6 ), FindRight() G( 1, 6 ), G( 2, 6 ), Draw() D( 1, 6 ), 
}
PopLine( 0 ) {
4 * FindLeft() G( 1, 8 ), G( 0, 8 ), FindRight() G( 1, 8 ), G( 2, 8 ), Draw() D( 1, 8 ), 
}
PopLine( 0 ) {
5 * FindLeft() G( 1, 9 ), G( 0, 9 ), FindRight() G( 1, 9 ), G( 2, 9 ), Draw() D( 1, 9 ), 
}
PopLine( 0 ) {
6 * FindLeft() G( 1, 10 ), G( 0, 10 ), FindRight() G( 1, 10 ), G( 2, 10 ), Draw() D( 1, 10 ), 
}
PopLine( 0 ) {
7 * FindLeft() G( 1, 11 ), G( 0, 11 ), FindRight() G( 1, 11 ), G( 2, 11 ), Draw() D( 1, 11 ), 
}
PopLine( 0 ) {
8 * FindLeft() G( 1, 12 ), G( 0, 12 ), FindRight() G( 1, 12 ), G( 2, 12 ), Draw() D( 1, 12 ), 
}
PopLine( 0 ) {
9 * FindLeft() G( 1, 13 ), G( 0, 13 ), FindRight() G( 1, 13 ), G( 2, 13 ), G( 3, 13 ), G( 4, 13 ), G( 5, 13 ), G( 6, 13 ), G( 7, 13 ), G( 8, 13 ), G( 9, 13 ), G( 10, 13 ), G( 11, 13 ), G( 12, 13 ), G( 13, 13 ), G( 14, 13 ), G( 15, 13 ), G( 16, 13 ), G( 17, 13 ), Draw() D( 1, 13 ), D( 2, 13 ), D( 3, 13 ), D( 4, 13 ), D( 5, 13 ), D( 6, 13 ), D( 7, 13 ), D( 8, 13 ), D( 9, 13 ), D( 10, 13 ), D( 11, 13 ), D( 12, 13 ), D( 13, 13 ), D( 14, 13 ), D( 15, 13 ), D( 16, 13 ), 
}
PopLine( 0 ) {
10 * FindLeft() G( 1, 14 ), SkipRight() G( 1, 14 ), G( 2, 14 ), G( 3, 14 ), G( 4, 14 ), G( 5, 14 ), G( 6, 14 ), G( 7, 14 ), G( 8, 14 ), G( 9, 14 ), G( 10, 14 ), G( 11, 14 ), G( 12, 14 ), G( 13, 14 ), G( 14, 14 ), G( 15, 14 ), G( 16, 14 ), 
}
PopLine( 0 ) {
11 * FindLeft() G( 1, 12 ), SkipRight() G( 1, 12 ), G( 2, 12 ), G( 3, 12 ), FindRight() G( 3, 12 ), G( 4, 12 ), Draw() D( 3, 12 ), SkipRight() G( 4, 12 ), G( 5, 12 ), FindRight() G( 5, 12 ), G( 6, 12 ), G( 7, 12 ), Draw() D( 5, 12 ), D( 6, 12 ), SkipRight() G( 7, 12 ), G( 8, 12 ), FindRight() G( 8, 12 ), G( 9, 12 ), G( 10, 12 ), Draw() D( 8, 12 ), D( 9, 12 ), SkipRight() G( 10, 12 ), G( 11, 12 ), FindRight() G( 11, 12 ), G( 12, 12 ), G( 13, 12 ), Draw() D( 11, 12 ), D( 12, 12 ), SkipRight() G( 13, 12 ), G( 14, 12 ), FindRight() G( 14, 12 ), G( 15, 12 ), Draw() D( 14, 12 ), SkipRight() G( 15, 12 ), G( 16, 12 ), FindRight() G( 16, 12 ), G( 17, 12 ), Draw() D( 16, 12 ), 
}
PopLine( 0 ) {
12 * FindLeft() G( 16, 11 ), G( 15, 11 ), FindRight() G( 16, 11 ), G( 17, 11 ), Draw() D( 16, 11 ), 
}
PopLine( 0 ) {
13 * FindLeft() G( 14, 11 ), G( 13, 11 ), FindRight() G( 14, 11 ), G( 15, 11 ), Draw() D( 14, 11 ), 
}
PopLine( 0 ) {
14 * FindLeft() G( 11, 11 ), G( 10, 11 ), FindRight() G( 11, 11 ), G( 12, 11 ), G( 13, 11 ), Draw() D( 11, 11 ), D( 12, 11 ), 
}
PopLine( 0 ) {
15 * FindLeft() G( 8, 11 ), G( 7, 11 ), FindRight() G( 8, 11 ), G( 9, 11 ), G( 10, 11 ), Draw() D( 8, 11 ), D( 9, 11 ), 
}
PopLine( 0 ) {
16 * FindLeft() G( 5, 11 ), G( 4, 11 ), FindRight() G( 5, 11 ), G( 6, 11 ), G( 7, 11 ), Draw() D( 5, 11 ), D( 6, 11 ), 
}
PopLine( 0 ) {
17 * FindLeft() G( 3, 11 ), G( 2, 11 ), FindRight() G( 3, 11 ), G( 4, 11 ), Draw() D( 3, 11 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 10 ), G( 2, 10 ), FindRight() G( 3, 10 ), G( 4, 10 ), Draw() D( 3, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 10 ), G( 4, 10 ), FindRight() G( 5, 10 ), G( 6, 10 ), G( 7, 10 ), Draw() D( 5, 10 ), D( 6, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 8, 10 ), SkipRight() G( 8, 10 ), G( 9, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 11, 10 ), G( 10, 10 ), FindRight() G( 11, 10 ), G( 12, 10 ), G( 13, 10 ), Draw() D( 11, 10 ), D( 12, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 10 ), G( 13, 10 ), FindRight() G( 14, 10 ), G( 15, 10 ), Draw() D( 14, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 10 ), G( 15, 10 ), FindRight() G( 16, 10 ), G( 17, 10 ), Draw() D( 16, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 9 ), G( 15, 9 ), FindRight() G( 16, 9 ), G( 17, 9 ), Draw() D( 16, 9 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 9 ), G( 13, 9 ), FindRight() G( 14, 9 ), G( 15, 9 ), Draw() D( 14, 9 ), 
}
PopLine( 0 ) {
FindLeft() G( 11, 9 ), G( 10, 9 ), G( 9, 9 ), G( 8, 9 ), G( 7, 9 ), G( 6, 9 ), G( 5, 9 ), G( 4, 9 ), FindRight() G( 11, 9 ), G( 12, 9 ), G( 13, 9 ), Draw() D( 5, 9 ), D( 6, 9 ), D( 7, 9 ), D( 8, 9 ), D( 9, 9 ), D( 10, 9 ), D( 11, 9 ), D( 12, 9 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 9 ), SkipRight() G( 5, 9 ), G( 6, 9 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 9 ), G( 2, 9 ), FindRight() G( 3, 9 ), G( 4, 9 ), Draw() D( 3, 9 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 8 ), G( 2, 8 ), FindRight() G( 3, 8 ), G( 4, 8 ), G( 5, 8 ), G( 6, 8 ), G( 7, 8 ), G( 8, 8 ), G( 9, 8 ), G( 10, 8 ), G( 11, 8 ), G( 12, 8 ), G( 13, 8 ), G( 14, 8 ), G( 15, 8 ), Draw() D( 3, 8 ), D( 4, 8 ), D( 5, 8 ), D( 6, 8 ), D( 7, 8 ), D( 8, 8 ), D( 9, 8 ), D( 10, 8 ), D( 11, 8 ), D( 12, 8 ), D( 13, 8 ), D( 14, 8 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 8 ), SkipRight() G( 5, 8 ), G( 6, 8 ), G( 7, 8 ), G( 8, 8 ), G( 9, 8 ), G( 10, 8 ), G( 11, 8 ), G( 12, 8 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 10 ), SkipRight() G( 5, 10 ), G( 6, 10 ), G( 7, 10 ), G( 8, 10 ), G( 9, 10 ), G( 10, 10 ), G( 11, 10 ), G( 12, 10 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 8 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 8 ), G( 15, 8 ), FindRight() G( 16, 8 ), G( 17, 8 ), Draw() D( 16, 8 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 7 ), G( 15, 7 ), FindRight() G( 16, 7 ), G( 17, 7 ), Draw() D( 16, 7 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 7 ), SkipRight() G( 3, 7 ), G( 4, 7 ), G( 5, 7 ), G( 6, 7 ), G( 7, 7 ), G( 8, 7 ), G( 9, 7 ), G( 10, 7 ), G( 11, 7 ), G( 12, 7 ), G( 13, 7 ), G( 14, 7 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 9 ), SkipRight() G( 3, 9 ), G( 4, 9 ), G( 5, 9 ), G( 6, 9 ), G( 7, 9 ), G( 8, 9 ), G( 9, 9 ), G( 10, 9 ), G( 11, 9 ), G( 12, 9 ), G( 13, 9 ), G( 14, 9 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 6 ), G( 15, 6 ), FindRight() G( 16, 6 ), G( 17, 6 ), Draw() D( 16, 6 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 5 ), G( 15, 5 ), FindRight() G( 16, 5 ), G( 17, 5 ), Draw() D( 16, 5 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 5 ), G( 0, 5 ), FindRight() G( 1, 5 ), G( 2, 5 ), Draw() D( 1, 5 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 4 ), G( 0, 4 ), FindRight() G( 1, 4 ), G( 2, 4 ), Draw() D( 1, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 4 ), G( 15, 4 ), FindRight() G( 16, 4 ), G( 17, 4 ), Draw() D( 16, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 3 ), G( 15, 3 ), FindRight() G( 16, 3 ), G( 17, 3 ), Draw() D( 16, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 3 ), G( 0, 3 ), FindRight() G( 1, 3 ), G( 2, 3 ), Draw() D( 1, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 2 ), G( 0, 2 ), FindRight() G( 1, 2 ), G( 2, 2 ), Draw() D( 1, 2 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 2 ), G( 15, 2 ), FindRight() G( 16, 2 ), G( 17, 2 ), Draw() D( 16, 2 ), 
}
PopLine( 0 ) {
FindLeft() G( 16, 1 ), G( 15, 1 ), G( 14, 1 ), G( 13, 1 ), G( 12, 1 ), G( 11, 1 ), G( 10, 1 ), G( 9, 1 ), G( 8, 1 ), G( 7, 1 ), G( 6, 1 ), G( 5, 1 ), G( 4, 1 ), G( 3, 1 ), G( 2, 1 ), G( 1, 1 ), G( 0, 1 ), FindRight() G( 16, 1 ), G( 17, 1 ), Draw() D( 1, 1 ), D( 2, 1 ), D( 3, 1 ), D( 4, 1 ), D( 5, 1 ), D( 6, 1 ), D( 7, 1 ), D( 8, 1 ), D( 9, 1 ), D( 10, 1 ), D( 11, 1 ), D( 12, 1 ), D( 13, 1 ), D( 14, 1 ), D( 15, 1 ), D( 16, 1 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 1 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 0 ), SkipRight() G( 1, 0 ), G( 2, 0 ), G( 3, 0 ), G( 4, 0 ), G( 5, 0 ), G( 6, 0 ), G( 7, 0 ), G( 8, 0 ), G( 9, 0 ), G( 10, 0 ), G( 11, 0 ), G( 12, 0 ), G( 13, 0 ), G( 14, 0 ), G( 15, 0 ), G( 16, 0 ), 
}
PopLine( 0 ) {
FindLeft() G( 1, 2 ), SkipRight() G( 1, 2 ), G( 2, 2 ), G( 3, 2 ), FindRight() G( 3, 2 ), G( 4, 2 ), Draw() D( 3, 2 ), SkipRight() G( 4, 2 ), G( 5, 2 ), FindRight() G( 5, 2 ), G( 6, 2 ), G( 7, 2 ), Draw() D( 5, 2 ), D( 6, 2 ), SkipRight() G( 7, 2 ), G( 8, 2 ), FindRight() G( 8, 2 ), G( 9, 2 ), G( 10, 2 ), Draw() D( 8, 2 ), D( 9, 2 ), SkipRight() G( 10, 2 ), G( 11, 2 ), FindRight() G( 11, 2 ), G( 12, 2 ), G( 13, 2 ), Draw() D( 11, 2 ), D( 12, 2 ), SkipRight() G( 13, 2 ), G( 14, 2 ), FindRight() G( 14, 2 ), G( 15, 2 ), Draw() D( 14, 2 ), SkipRight() G( 15, 2 ), G( 16, 2 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 3 ), G( 13, 3 ), FindRight() G( 14, 3 ), G( 15, 3 ), Draw() D( 14, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 11, 3 ), G( 10, 3 ), FindRight() G( 11, 3 ), G( 12, 3 ), G( 13, 3 ), Draw() D( 11, 3 ), D( 12, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 8, 3 ), G( 7, 3 ), FindRight() G( 8, 3 ), G( 9, 3 ), G( 10, 3 ), Draw() D( 8, 3 ), D( 9, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 3 ), G( 4, 3 ), FindRight() G( 5, 3 ), G( 6, 3 ), G( 7, 3 ), Draw() D( 5, 3 ), D( 6, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 3 ), G( 2, 3 ), FindRight() G( 3, 3 ), G( 4, 3 ), Draw() D( 3, 3 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 4 ), G( 2, 4 ), FindRight() G( 3, 4 ), G( 4, 4 ), Draw() D( 3, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 4 ), G( 4, 4 ), FindRight() G( 5, 4 ), G( 6, 4 ), G( 7, 4 ), Draw() D( 5, 4 ), D( 6, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 8, 4 ), SkipRight() G( 8, 4 ), G( 9, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 11, 4 ), G( 10, 4 ), FindRight() G( 11, 4 ), G( 12, 4 ), G( 13, 4 ), Draw() D( 11, 4 ), D( 12, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 4 ), G( 13, 4 ), FindRight() G( 14, 4 ), G( 15, 4 ), Draw() D( 14, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 5 ), G( 13, 5 ), FindRight() G( 14, 5 ), G( 15, 5 ), Draw() D( 14, 5 ), 
}
PopLine( 0 ) {
FindLeft() G( 11, 5 ), G( 10, 5 ), G( 9, 5 ), G( 8, 5 ), G( 7, 5 ), G( 6, 5 ), G( 5, 5 ), G( 4, 5 ), FindRight() G( 11, 5 ), G( 12, 5 ), G( 13, 5 ), Draw() D( 5, 5 ), D( 6, 5 ), D( 7, 5 ), D( 8, 5 ), D( 9, 5 ), D( 10, 5 ), D( 11, 5 ), D( 12, 5 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 5 ), SkipRight() G( 5, 5 ), G( 6, 5 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 5 ), G( 2, 5 ), FindRight() G( 3, 5 ), G( 4, 5 ), Draw() D( 3, 5 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 6 ), G( 2, 6 ), FindRight() G( 3, 6 ), G( 4, 6 ), G( 5, 6 ), G( 6, 6 ), G( 7, 6 ), G( 8, 6 ), G( 9, 6 ), G( 10, 6 ), G( 11, 6 ), G( 12, 6 ), G( 13, 6 ), G( 14, 6 ), G( 15, 6 ), Draw() D( 3, 6 ), D( 4, 6 ), D( 5, 6 ), D( 6, 6 ), D( 7, 6 ), D( 8, 6 ), D( 9, 6 ), D( 10, 6 ), D( 11, 6 ), D( 12, 6 ), D( 13, 6 ), D( 14, 6 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 6 ), SkipRight() G( 5, 6 ), G( 6, 6 ), G( 7, 6 ), G( 8, 6 ), G( 9, 6 ), G( 10, 6 ), G( 11, 6 ), G( 12, 6 ), 
}
PopLine( 0 ) {
FindLeft() G( 5, 4 ), SkipRight() G( 5, 4 ), G( 6, 4 ), G( 7, 4 ), G( 8, 4 ), G( 9, 4 ), G( 10, 4 ), G( 11, 4 ), G( 12, 4 ), 
}
PopLine( 0 ) {
FindLeft() G( 14, 6 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 7 ), SkipRight() G( 3, 7 ), G( 4, 7 ), G( 5, 7 ), G( 6, 7 ), G( 7, 7 ), G( 8, 7 ), G( 9, 7 ), G( 10, 7 ), G( 11, 7 ), G( 12, 7 ), G( 13, 7 ), G( 14, 7 ), 
}
PopLine( 0 ) {
FindLeft() G( 3, 5 ), SkipRight() G( 3, 5 ), G( 4, 5 ), G( 5, 5 ), G( 6, 5 ), G( 7, 5 ), G( 8, 5 ), G( 9, 5 ), G( 10, 5 ), G( 11, 5 ), G( 12, 5 ), G( 13, 5 ), G( 14, 5 ), 
}

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.


Written By
John R. Shaw
Software Developer (Senior)
United States United States
I am a senior software engineer who has been designing and developing software for many years, mostly in C/C++. You might say that I think in code; which is why I am passionate about my first rule of coding: “First do no harm”. So if I get carried away in my explanations, please realize that it is just part of my personality. I enjoy learning new things and, when I have the time, passing that knowledge onto others.

Comments and Discussions

Permalink
Advertise
Privacy
Cookies
Terms of Use
Layout: fixed | fluid

Posted 2 Feb 2004

Article Copyright 2004 by John R. Shaw
Everything else Copyright © CodeProject, 1999-2024

Web01 2.8:2024-04-02:1