Editing Flood fill (section)

== 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" />