Floodfill

Floodfill or flood filling is a term used in computer graphics. It is a simple algorithm to detect faces of contiguous pixels of a color in a digital image and to fill it with a new color.

Starting from a pixel within the area of ​​its neighboring pixels are tested if these neighboring pixels also contain the old paint each. Each pixel found with the old color will be immediately replaced it with the new color.

Two variants of the algorithm are common:

4 -connected or 4 -neighbor

In each case, the four neighboring pixels down, left, up and right from the starting point examined ( the coordinate origin is in the top-left corner ).

Fill4 (x, y, old color, new color) {      if ( getPixel (x, y) == old color) {         marked pixel (x, y, new color );         fill4 (x, y 1, old color, new color ); / / Below       fill4 (x, y - 1, old color, new color ); / / Above       fill4 (x - 1, y, old color, new color ); / / Left       fill4 (x 1, y, old color, new color ); / / Right      }    return; } 8 -connected or 8 -neighbor

In each case, the eight neighboring pixels up, down, left, right, top - left, top - right, bottom - left and bottom-right looking from the starting point ( origin is top-left in the corner).

Fill8 (x, y, old color, new color) {      if ( getPixel (x, y) == old color) {         marked pixel (x, y, new color );         fill8 (x, y 1, old color, new color ); / / below       fill8 (x, y - 1, old color, new color ); / / above       fill8 (x 1, y, old color, new color ); / / right       fill8 (x - 1, y, old color, new color ); / / left       fill8 (x 1, y 1, old color, new color ); / / bottom - right       fill8 (x 1, y - 1, old color, new color ); / / top - right       fill8 (x - 1, y 1, old color, new color ); / / bottom - left       fill8 (x - 1, y - 1, old color, new color ); / / top - left      }    return; } With the same initial conditions, the 8 -connected variant usually fills a larger area than the 4 -connected variant because it " crawls through fine cracks ". This is often not desired.

Due to the simplicity of the algorithm, it is of limited use for non-trivial applications. The algorithm is highly recursive. Therefore, there is a high risk that the algorithm leads to a stack overflow. Similarly, the possible number stack operations require the recursions as compared to the actual operations of the algorithm are relatively long.

Last but not least many Rekursionsaufrufe of the algorithm are unnecessary because it unnecessarily pixels are tested which have been previously been set to the new color. Each recursion encounters at least one such pixel, that pixel, which has just marked in the overlying Rekursionslevel.

Iterative flood fill

Using a stack or a similar data structure, an iterative implementation is possible. The neighboring pixel coordinates are stored and then processed sequentially. The order in which the coordinates are read out of the data structure is not important. Due to the high risk of a stack overflow in recursive flood fill the iterative version is the better choice to implement the method in general.

Fill4 (x, y, old color, new color) {       stack.push (x, y);       while ( stack.isNotEmpty ) {        (x, y) = stack.pop;          if ( getPixel (x, y) == old color) {           marked pixel (x, y, new color );             stack.push (x, y 1);           stack.push (x, y - 1);           stack.push (x 1, y);           stack.push (x - 1, y);        }     }     return; } This example corresponds to the recursive algorithm with four neighbors. The one with eight neighbors is implemented according to analogy.

Teiliterative flood layer ( clamping Flood Fill)

In teiliterativer flood fill algorithm consists of an iterative part, the ever- running and always turns in a certain direction, for example, always to the left. If the iterative part is no more pixels to color, the recursive part is started, the now much less goes deep into the recursion. Thus, a stack overflow is less likely.

• Computer Graphics
• Algorithm (computer graphics )