Editing Flood fill

{{Short description|Algorithm in computer graphics to add color or texture}}
[[Image:Recursive Flood Fill 4 (aka).gif|right|thumb|Recursive flood fill with 4 directions]]

'''Flood fill''', also called '''seed fill''', is a [[flooding algorithm]] that determines and alters the area [[Glossary of graph theory#Connectivity|connected]] to a given node in a multi-dimensional [[Array data structure|array]] with some matching attribute. It is used in the "bucket" fill tool of [[paint program]]s to fill connected, similarly colored areas with a different color, and in games such as [[Go (game)|Go]] and [[Minesweeper (video game)|Minesweeper]] for determining which pieces are cleared. A variant called '''boundary fill''' uses the same algorithms but is defined as the area [[Glossary of graph theory#Connectivity|connected]] to a given node that does not have a particular attribute.<ref name="79Smith">{{Cite conference |title=Tint Fill |last=Smith |first=Alvy Ray |year=1979 |conference=SIGGRAPH '79: Proceedings of the 6th annual conference on Computer graphics and interactive techniques |pages=276–283 |doi=10.1145/800249.807456 }}</ref>

Note that flood filling is not suitable for drawing filled polygons, as it will miss some pixels in more acute corners.<ref name="81Ackland">{{Cite conference |title=The edge flag algorithm — A fill method for raster scan displays |last1=Ackland |first1=Bryan D |last2=Weste |first2=Neil H |year=1981 |conference=IEEE Transactions on Computers (Volume: C-30, Issue: 1) |pages=41–48 |doi=10.1109/TC.1981.6312155 }}</ref> Instead, see [[Even–odd rule|Even-odd rule]] and [[Nonzero-rule]].

==The algorithm parameters==
[[Image:Recursive Flood Fill 8 (aka).gif|right|thumb|Recursive flood fill with 8 directions]]
The traditional flood-fill algorithm takes three parameters: a start node, a target color, and a replacement color. The algorithm looks for all nodes in the array that are connected to the start node by a path of the target color and changes them to the replacement color. For a boundary-fill, in place of the target color, a border color would be supplied.

In order to generalize the algorithm in the common way, the following descriptions will instead have two routines available.<ref name="85Fishkin" /> One called <code>Inside</code> which returns true for unfilled points that, by their color, would be inside the filled area, and one called <code>Set</code> which fills a pixel/node. Any node that has <code>Set</code> called on it must then no longer be <code>Inside</code>.

Depending on whether we consider nodes touching at the corners connected or not, we have two variations: eight-way and four-way respectively.

== Stack-based recursive implementation (four-way) ==

The earliest-known, implicitly stack-based, [[recursion (computer science)|recursive]], four-way flood-fill implementation goes as follows:<ref name="73Newman">{{Cite book |title=Principles of Interactive Computer Graphics |last1=Newman |first1=William M |last2=Sproull |first2=Robert Fletcher |page=253 |edition=2nd |year=1979 |publisher=McGraw-Hill |isbn=978-0-07-046338-7 }}</ref><ref name="82Pavlidis">{{Cite book |title=Algorithms for Graphics and Image Processing |last=Pavlidis |first=Theo |page=181 |year=1982 |publisher=Springer-Verlag |isbn=978-3-642-93210-6 }}</ref><ref name="82Levoy">{{Cite conference |title=Area Flooding Algorithms |last=Levoy |first=Marc |year=1982 |conference=SIGGRAPH 1981 Two-Dimensional Computer Animation course notes}}</ref><ref name="90Foley">{{Cite book |title=Computer Graphics: Principles and Practice |last1=Foley |first1=J D |last2=van Dam |first2=A |last3=Feiner |first3=S K |last4=Hughes |first4=S K |year=1990 |edition=2nd |publisher=Addison–Wesley |pages=979–982 |isbn=978-0-201-84840-3}}</ref>

 '''Flood-fill''' (node):
  1. If ''node'' is not ''Inside'' return.
  2. ''Set'' the ''node''
  3. Perform '''Flood-fill''' one step to the south of ''node''.
  4. Perform '''Flood-fill''' one step to the north of ''node''
  5. Perform '''Flood-fill''' one step to the west of ''node''
  6. Perform '''Flood-fill''' one step to the east of ''node''
  7. Return.

Though easy to understand, the implementation of the algorithm used above is impractical in languages and environments where stack space is severely constrained (e.g. [[Microcontroller]]s).

=== Moving the recursion into a data structure ===

{{multiple image
| align = right
| image1 = Wfm floodfill animation queue.gif
| width1 = 200
| alt1 = 
| caption1 = Four-way flood fill using a queue for storage
| image2 = Wfm floodfill animation stack.gif
| width2 = 200
| alt2 = 
| caption2 = Four-way flood fill using a stack for storage
| footer = 
}}

Moving the recursion into a data structure (either a [[Stack (abstract data type)|stack]] or a [[Queue (abstract data type)|queue]]) prevents a [[stack overflow]]. It is similar to the simple recursive solution, except that instead of making recursive calls, it pushes the nodes onto a [[Stack (abstract data type)|stack]] or [[Queue (abstract data type)|queue]] for consumption, with the choice of data structure affecting the proliferation pattern:

{{clear}}

 '''Flood-fill''' (node):
   1. Set ''Q'' to the empty queue or stack.
   2. Add ''node'' to the end of ''Q''.
   3. While ''Q'' is not empty:
   4.   Set ''n'' equal to the first element of ''Q''.
   5.   Remove first element from ''Q''.
   6.   If ''n'' is ''Inside'':
          ''Set'' the ''n''
          Add the node to the west of ''n'' to the end of ''Q''.
          Add the node to the east of ''n'' to the end of ''Q''.
          Add the node to the north of ''n'' to the end of ''Q''.
          Add the node to the south of ''n'' to the end of ''Q''.
   7. Continue looping until ''Q'' is exhausted.
   8. Return.

=== Further potential optimizations ===
* Check and set each node's pixel color before adding it to the stack/queue, reducing stack/queue size.
* Use a loop for the east–west directions, queuing pixels above/below as you go (making it similar to the span filling algorithms, below).
* Interleave two or more copies of the code with extra stacks/queues, to allow [[Out-of-order execution|out-of-order processors]] more opportunity to parallelize.
* Use multiple threads (ideally with slightly different visiting orders, so they don't stay in the same area).<ref name="82Levoy" />

=== Advantages ===
* Very simple algorithm - easy to make bug-free.<ref name="82Levoy" />

=== Disadvantages ===
* Uses a lot of memory, particularly when using a stack.<ref name="82Levoy" />
* Tests most filled pixels a total of four times.
* Not suitable for pattern filling, as it requires pixel test results to change.
* Access pattern is not cache-friendly, for the queuing variant.
* Cannot easily optimize for multi-pixel words or bitplanes.<ref name="81Ackland" />

== Span filling ==

[[Image:Smiley fill.gif|right|thumb|212px|Scanline fill using a stack for storage]]

It's possible to optimize things further by working primarily with spans, a row with constant <code>y</code>. The first published complete example works on the following basic principle.<ref name="79Smith" />

# Starting with a seed point, fill left and right. Keep track of the leftmost filled point <code>lx</code> and rightmost filled point <code>rx</code>. This defines the span. 
# Scan from <code>lx</code> to <code>rx</code> above and below the seed point, searching for new seed points to continue with.

As an optimisation, the scan algorithm does not need restart from every seed point, but only those at the start of the next span. Using a [[Stack (abstract data type)|stack]] explores spans depth first, whilst a [[Queue (abstract data type)|queue]] explores spans breadth first.

{{clear}}

 fn '''fill'''(''x'', ''y''):
     if not '''Inside'''(''x'', ''y'') then return
     let ''s'' = new empty stack or queue
     Add (''x'', ''y'') to ''s''
     while ''s'' is not empty:
         Remove an (''x'', ''y'') from ''s''
         let ''lx'' = ''x''
         while '''Inside'''(''lx'' - 1, ''y''):
             '''Set'''(''lx'' - 1, ''y'')
             ''lx'' = ''lx'' - 1
         while '''Inside'''(''x'', ''y''):
             '''Set'''(''x'', ''y'')
             ''x'' = ''x'' + 1
       '''scan'''(''lx'', ''x'' - 1, ''y'' + 1, ''s'')
       '''scan'''(''lx'', ''x'' - 1, ''y'' - 1, ''s'')
 
 fn '''scan'''(''lx'', ''rx'', ''y'', ''s''):
     let ''span_added'' = ''false''
     for ''x'' in ''lx'' .. ''rx'':
         if not '''Inside'''(''x'', ''y''):
             ''span_added'' = ''false''
         else if not ''span_added'':
             Add (''x'', ''y'') to ''s''
             ''span_added'' = ''true''

Over time, the following optimizations were realized:
* When a new scan would be entirely within a grandparent span, it would certainly only find filled pixels, and so wouldn't need queueing.<ref name="79Smith" /><ref name="82Levoy" /><ref name="85Fishkin">{{Cite conference |title=An Analysis and Algorithm for Filling Propagation |last1=Fishkin |first1=Kenneth P |last2=Barsky |first2=Brian A |year=1985 |conference=Computer-Generated Images: The State of the Art Proceedings of Graphics Interface ’85 |pages=56–76 |doi=10.1007/978-4-431-68033-8_6 }}</ref>
* Further, when a new scan overlaps a grandparent span, only the overhangs (U-turns and W-turns) need to be scanned.<ref name="85Fishkin" />
* It's possible to fill while scanning for seeds <ref name="82Levoy" />

The final, combined-scan-and-fill span filler was then published in 1990. In pseudo-code form:<ref name="90Heckbert">{{Cite book |title=Graphics Gems |last=Heckbert |first=Paul S |chapter=IV.10: A Seed Fill Algorithm |pages=275–277 |editor-last=Glassner |editor-first=Andrew S |year=1990 |publisher=Academic Press |isbn=0122861663 }}</ref>

 fn '''fill'''(''x'', ''y''):
     if not '''Inside'''(''x'', ''y'') then return
     let ''s'' = new empty queue or stack
     Add (''x'', ''x'', ''y'', 1) to ''s''
     Add (''x'', ''x'', ''y'' - 1, -1) to ''s''
     while ''s'' is not empty:
         Remove an (''x1'', ''x2'', ''y'', ''dy'') from ''s''
         let ''x'' = ''x1''
         if '''Inside'''(''x'', ''y''):
             while '''Inside'''(''x'' - 1, ''y''):
                 '''Set'''(''x'' - 1, ''y'')
                 ''x'' = ''x'' - 1
             if ''x'' < ''x1'':
                 Add (''x'', ''x1'' - 1, ''y'' - ''dy'', -''dy'') to ''s''
         while ''x1'' <= ''x2'':
             while '''Inside'''(''x1'', ''y''):
                 '''Set'''(''x1'', ''y'')
                 ''x1'' = ''x1'' + 1
             if ''x1'' > ''x'':
                 '''Add''' (''x'', ''x1'' - 1, ''y'' + ''dy'', ''dy'') to ''s''
             if ''x1'' - 1 > ''x2'':
                 '''Add''' (''x2'' + 1, ''x1'' - 1, ''y'' - ''dy'', -''dy'') to ''s''
             ''x1'' = ''x1'' + 1
             while ''x1'' < ''x2'' and not '''Inside'''(''x1'', ''y''):
                 ''x1'' = ''x1'' + 1
             ''x'' = ''x1''

===Advantages===
* 2–8x faster than the pixel-recursive algorithm.
* Access pattern is cache and bitplane-friendly.<ref name="82Levoy" />
* Can draw a horizontal line rather than setting individual pixels.<ref name="82Levoy" />

===Disadvantages===
* Still visits pixels it has already filled. (For the popular algorithm, 3 scans of most pixels. For the final one, only doing extra scans of pixels where there are holes in the filled area.)<ref name="85Fishkin" />
* Not suitable for pattern filling, as it requires pixel test results to change.

== Adding pattern filling support ==

Two common ways to make the span and pixel-based algorithms support pattern filling are either to use a unique color as a plain fill and then replace that with a pattern or to keep track (in a 2d Boolean array or as regions) of which pixels have been visited, using it to indicate pixels are no longer fillable. ''Inside'' must then return ''false'' for such visited pixels.<ref name="85Fishkin" />

== Graph-theoretic filling ==

Some theorists applied explicit graph theory to the problem, treating spans of pixels, or aggregates of such, as nodes and studying their connectivity. The first published graph theory algorithm worked similarly to the span filling, above, but had a way to detect when it would duplicate filling of spans.<ref name="78Lieberman">{{Cite conference |title=How to Color in a Coloring Book |last=Lieberman |first=Henry |year=1978 |conference=SIGGRAPH '78: Proceedings of the 5th annual conference on Computer graphics and interactive techniques |pages=111–116 |doi=10.1145/800248.807380 }}</ref> Unfortunately, it had bugs that made it not complete some fills.<ref name="80Shani">{{Cite conference |title=Filling regions in binary raster images: A graph-theoretic approach |last=Shani |first=Uri |year=1980 |conference=SIGGRAPH '80: Proceedings of the 7th annual conference on Computer graphics and interactive techniques |pages=321–327 |doi=10.1145/800250.807511 }}</ref> A corrected algorithm was later published with a similar basis in graph theory; however, it alters the image as it goes along, to temporarily block off potential loops, complicating the programmatic interface.<ref name="80Shani" /> A later published algorithm depended on the boundary being distinct from everything else in the image and so isn't suitable for most uses;<ref name="81Pavlidis">{{Cite conference |title=Contour Filling in Raster Graphics |last=Pavlidis |first=Theo |year=1981 |conference=SIGGRAPH '81: Proceedings of the 8th annual conference on Computer graphics and interactive techniques |pages=29–36 |doi=10.1145/800224.806786 }}</ref><ref name="85Fishkin" /> it also requires an extra bit per pixel for bookkeeping.<ref name="85Fishkin" />

===Advantages===
* Suitable for pattern filling, directly, as it never retests filled pixels.<ref name="78Lieberman" /><ref name="80Shani" /><ref name="81Pavlidis" />
* Double the speed of the original span algorithm, for uncomplicated fills.<ref name="85Fishkin" />
* Access pattern is cache and bitplane-friendly.<ref name="82Levoy" /><ref name="85Fishkin" />

===Disadvantages===
* Regularly, a span has to be compared to every other 'front' in the queue, which significantly slows down complicated fills.<ref name="85Fishkin" />
* Switching back and forth between graph theoretic and pixel domains complicates understanding.
* The code is fairly complicated, increasing the chances of bugs.

== Walk-based filling (Fixed-memory method)==
A method exists that uses essentially no memory for [[Pixel connectivity|four-connected]] regions by pretending to be a painter trying to paint the region without painting themselves into a corner. This is also [[Maze-solving algorithm|a method for solving mazes]]. The four pixels making the primary boundary are examined to see what action should be taken. The painter could find themselves in one of several conditions:

# All four boundary pixels are filled.
# Three of the boundary pixels are filled.
# Two of the boundary pixels are filled.
# One boundary pixel is filled.
# Zero boundary pixels are filled.

Where a path or boundary is to be followed, the right-hand rule is used. The painter follows the region by placing their right-hand on the wall (the boundary of the region) and progressing around the edge of the region without removing their hand.

For case #1, the painter paints (fills) the pixel the painter is standing upon and stops the algorithm.

For case #2, a path leading out of the area exists. Paint the pixel the painter is standing upon and move in the direction of the open path.

For case #3, the two boundary pixels define a path which, if we painted the current pixel, may block us from ever getting back to the other side of the path. We need a "mark" to define where we are and which direction we are heading to see if we ever get back to exactly the same pixel. If we already created such a "mark", then we preserve our previous mark and move to the next pixel following the right-hand rule.

A mark is used for the first 2-pixel boundary that is encountered to remember where the passage started and in what direction the painter was moving. If the mark is encountered again and the painter is traveling in the same direction, then the painter knows that it is safe to paint the square with the mark and to continue in the same direction. This is because (through some unknown path) the pixels on the other side of the mark can be reached and painted in the future. The mark is removed for future use.

If the painter encounters the mark but is going in a different direction, then some sort of loop has occurred, which caused the painter to return to the mark. This loop must be eliminated. The mark is picked up, and the painter then proceeds in the direction indicated previously by the mark using a left-hand rule for the boundary (similar to the right-hand rule but using the painter's left hand). This continues until an intersection is found (with three or more open boundary pixels). Still using the left-hand rule the painter now searches for a simple passage (made by two boundary pixels). Upon finding this two-pixel boundary path, that pixel is painted. This breaks the loop and allows the algorithm to continue.

For case #4, we need to check the opposite 8-connected corners to see whether they are filled or not. If either or both are filled, then this creates a many-path intersection and cannot be filled. If both are empty, then the current pixel can be painted and the painter can move following the right-hand rule.

The algorithm trades time for memory. For simple shapes it is very efficient. However, if the shape is complex with many features, the algorithm spends a large amount of time tracing the edges of the region trying to ensure that all can be painted.

A walking algorithm was published in 1994.<ref name="94Henrich">{{Cite conference |title=Space-efficient region filling in raster graphics |last=Henrich |first=Dominik |year=1994 |conference=The Visual Computer |pages=205–215 |doi=10.1007/BF01901287 }}</ref>

=== Pseudocode ===
This is a pseudocode implementation of an optimal fixed-memory flood-fill algorithm written in structured English:

; The variables
* <code>cur</code>, <code>mark</code>, and <code>mark2</code> each hold either pixel coordinates or a null value
** NOTE: when <code>mark</code> is set to null, do not erase its previous coordinate value. Keep those coordinates available to be recalled if necessary.
* <code>cur-dir</code>, <code>mark-dir</code>, and <code>mark2-dir</code> each hold a direction (left, right, up, or down)
* <code>backtrack</code> and <code>findloop</code> each hold Boolean values
* <code>count</code> is an integer
; The algorithm
: NOTE: All directions (front, back, left, right) are relative to <code>cur-dir</code>
 set cur to starting pixel
 set cur-dir to default direction
 clear mark and mark2 (set values to null)
 set backtrack and findloop to false
 
 '''while''' front-pixel is empty '''do'''
     move forward
 '''end while'''
 
 jump to START
 
 MAIN LOOP:
     move forward
     '''if''' right-pixel is inside '''then'''
         '''if''' backtrack is true '''and''' findloop is false '''and''' either front-pixel '''or''' left-pixel is inside '''then'''
             set findloop to true
         '''end if'''
         turn right
 PAINT:
         move forward
     '''end if'''
 START:
     '''set''' ''count'' to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
     '''if''' ''count'' '''is not''' 4 '''then'''
         '''do'''
             turn right
         '''while''' front-pixel is inside
         '''do'''
             turn left
         '''while''' front-pixel is not inside
     '''end if'''
     '''switch''' ''count''
         case 1
             '''if''' backtrack is true '''then'''
                 set findloop to true
             '''else if''' findloop is true '''then'''
                 '''if''' mark is null '''then'''
                     restore mark
                 '''end if'''
             '''else if''' front-left-pixel and back-left-pixel are both inside '''then'''
                 clear mark
                 set cur
                 jump to PAINT
             '''end if'''
         end case
         case 2
             '''if''' back-pixel is not inside '''then'''
                 '''if''' front-left-pixel is inside '''then'''
                     clear mark
                     set cur
                     jump to PAINT
                 '''end if'''
             '''else if''' mark is not set '''then'''
                 set mark to cur
                 set mark-dir to cur-dir
                 clear mark2
                 set findloop and backtrack to false
             '''else'''
                 '''if''' mark2 is not set '''then'''
                     '''if''' cur is at mark '''then'''
                         '''if''' cur-dir is the same as mark-dir '''then'''
                             clear mark
                             turn around
                             set cur
                             jump to PAINT
                         '''else'''
                             set backtrack to true
                             set findloop to false
                             set cur-dir to mark-dir
                         '''end if'''
                     '''else if''' findloop is true '''then'''
                         set mark2 to cur
                         set mark2-dir to cur-dir
                     '''end if'''
                 '''else'''
                     '''if''' cur is at mark '''then'''
                         set cur to mark2
                         set cur-dir to mark2-dir
                         clear mark and mark2
                         set backtrack to false
                         turn around
                         set cur
                         jump to PAINT
                     '''else''' if cur at mark2 '''then'''
                         set mark to cur
                         set cur-dir and mark-dir to mark2-dir
                         clear mark2
                     '''end if'''
                 '''end if'''
             '''end if'''
         end case
         case 3
             clear mark
             set cur
             jump to PAINT
         end case
         case 4
             set cur
             done
         end case
     '''end switch'''
 end MAIN LOOP

===Advantages===
* Constant memory usage.

===Disadvantages===
* Access pattern is not cache or bitplane-friendly.
* Can spend a lot of time walking around loops before closing them.

==Vector implementations==
Version 0.46 of [[Inkscape]] includes a bucket fill tool, giving output similar to ordinary bitmap operations and indeed using one: the canvas is rendered, a flood fill operation is performed on the selected area and the result is then traced back to a path. It uses the concept of a [[boundary value problem|boundary condition]].

==See also==
* [[Breadth-first search]]
* [[Depth-first search]]
* [[Graph traversal]]
* [[Connected-component labeling]]
* [[Dijkstra's algorithm]]
* [[Watershed (image processing)]]

==External links==
* [http://lodev.org/cgtutor/floodfill.html Sample implementations for recursive and non-recursive, classic and scanline flood fill], by Lode Vandevenne.
* [https://web.piyushgarg.in/2021/09/flood-fill-4-directional-using-java.html Sample Java implementation using Q non-recursive.]

== References ==

<references />

{{DEFAULTSORT:Flood Fill}}
[[Category:Computer graphics algorithms]]
[[Category:Articles with example pseudocode]]
[[Category:Flooding algorithms]]