Citizendia
Your Ad Here

recursive flood-fill with 4 directions
recursive flood-fill with 4 directions

Flood fill, also called seed fill, is an algorithm that determines the area connected to a given node in a multi-dimensional array. In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation Graph theory is a growing area in mathematical research and has a large specialized vocabulary In Computer science an array is a Data structure consisting of a group of elements that are accessed by indexing. It is used in the "bucket" fill tool of paint programs to determine which parts of a bitmap to fill with color, and in puzzle games such as Minesweeper, Puyo Puyo, Lumines, and Magical Drop for determining which pieces are cleared. A raster graphics editor is a Computer program that allows users to paint and edit Pictures interactively on the computer screen and save them in one In Computer graphics, a bitmap or pixmap is a type of memory organization or Image file format used to store Digital images The Minesweeper is a single-player computer game The object of the game is to clear an abstract minefield without detonating a mine. Puyo Pop, known in Japan as is a Computer puzzle game made in 1991 by Compile for various video game systems is a Video puzzle game based on sound and light patterns Created by game designer Tetsuya Mizuguchi and his company Q Entertainment, it was first released Magical Drop is a series of puzzle games primarily for the Neo-Geo and Super Famicom, developed by Data East.

Contents

The algorithm

recursive flood-fill with 8 directions
recursive flood-fill with 8 directions

The 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 which are connected to the start node by a path of the target color, and changes them to the replacement color. There are many ways in which the flood-fill algorithm can be structured, but they all make use of a queue or stack data structure, explicitly or implicitly. A queue (pronounced /kjuː/ is a particular kind of collection in which the entities in the collection are kept in order and the principal (or only operations on the collection In Computer science, a stack is an Abstract data type and Data structure based on the principle of Last In First Out (LIFO One implicitly stack-based (recursive) flood-fill implementation (for a two-dimensional array) goes as follows:

Flood-fill (node, target-color, replacement-color):
 1. Recursion, in Mathematics and Computer science, is a method of defining functions in which the function being defined is applied within its own definition  If the color of node is not equal to target-color, return. 
 2.  Set the color of node to replacement-color. 
 3.  Perform Flood-fill (one step to the west of node, target-color, replacement-color). 
    Perform Flood-fill (one step to the east of node, target-color, replacement-color). 
    Perform Flood-fill (one step to the north of node, target-color, replacement-color). 
    Perform Flood-fill (one step to the south of node, target-color, replacement-color). 
 4.  Return.

Alternative implementations

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. Java applets). A Java applet is an Applet delivered in the form of Java bytecode.

An explicitly queue-based implementation might resemble the pseudo-code below. This implementation is not very efficient, but can be easily done without using the stack, and it is easy to debug:

Flood-fill (node, target-color, replacement-color):
 1.  Set Q to the empty queue. 
 2.  If the color of node is not equal to target-color, return. 
 3.  Add node to the end of Q. 
 4.  While "Q" is not empty: 
 5.      Set "n" equal to the first element of "Q"
 6.      If the color of n is equal to target-color, set the color of n to replacement-color. 
 7.      Remove first element from "Q"
 7.      If the color of the node to the west of n is target-color, set the color of that node to replacement-color, add that node to the end of Q. 
        If the color of the node to the east of n is target-color, set the color of that node to replacement-color, add that node to the end of Q. 
        If the color of the node to the north of n is target-color, set the color of that node to replacement-color, add that node to the end of Q. 
        If the color of the node to the south of n is target-color, set the color of that node to replacement-color, add that node to the end of Q. 
 8.  Return.

Most practical implementations use a loop for the west and east directions as an optimization to avoid the overhead of stack or queue management:

Flood-fill (node, target-color, replacement-color):
 1.  Set Q to the empty queue. 
 2.  If the color of node is not equal to target-color, return. 
 3.  Add node to Q. 
 4.  For each element n of Q:
 5.   If the color of n is equal to target-color:
 6.    Set w and e equal to n. 
 7.    Move w to the west until the color of the node to the west of w no longer matches target-color. 
 8.    Move e to the east until the color of the node to the east of e no longer matches target-color. 
 9.    Set the color of nodes between w and e to replacement-color. 
10.    For each node n between w and e:
11.     If the color of the node to the north of n is target-color, add that node to Q. 
       If the color of the node to the south of n is target-color, add that node to Q. 
12.  Continue looping until Q is exhausted. 
13.  Return.

Adapting the algorithm to use an additional array to store the shape of the region allows generalization to cover "fuzzy" flood filling, where an element can differ by up to a specified threshold from the source symbol. Using this additional array as an alpha channel allows the edges of the filled region to blend somewhat smoothly with the not-filled region. In Computer graphics, alpha compositing is the process of combining an image with a background to create the appearance of partial transparency

Scanline Fill

The algorithm can be sped up by filling lines. Instead of pushing each potential future pixel coordinate into the stack, it inspects the neighbour lines (previous and next) to find adjacent segments that may be filled in a future pass; the coordinates (either the start or the end) of the line segment are pushed on the stack. In most cases this scanline algorithm is at least an order of magnitude faster than the per-pixel one.

Vector implementations

The current development version of Inkscape (which is now version 0. Inkscape is a free and Open source Vector graphics editor application 46) 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 concept of a boundary condition. In Mathematics, in the field of Differential equations a boundary value problem is a Differential equation together with a set of additional restraints

See also

External links

Dictionary

flood fill

-noun

  1. (computing, graphics) A means of filling a discrete area with colour, based on colouring every pixel that can be recursively reached from a starting point.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic