Flood fill, also called seed fill, is a flooding algorithm that determines and alters the area connected to a given node in a multi-dimensional array with some matching attribute. It is used in the "bucket" fill tool of paint programs to fill connected, similarly-colored areas with a different color, and in games such as Go and Minesweeper for determining which pieces are cleared. A variant called boundary fill uses the same algorithms but is defined as the area connected to a given node that does not have a particular attribute. [1]
Note that flood filling is not suitable for drawing filled polygons, as it will miss some pixels in more acute corners. [2] Instead, see Even-odd rule and Nonzero-rule.
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. [3] One called Inside
which returns true for unfilled points that, by their color, would be inside the filled area, and one called Set
which fills a pixel/node. Any node that has Set
called on it must then no longer be Inside
.
Depending on whether we consider nodes touching at the corners connected or not, we have two variations: eight-way and four-way respectively.
The earliest-known, implicitly stack-based, recursive, four-way flood-fill implementation goes as follows: [4] [5] [6] [7]
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. Microcontrollers).
Moving the recursion into a data structure (either a stack or a 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 or queue for consumption, with the choice of data structure affecting the proliferation pattern:
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.
It's possible to optimize things further by working primarily with spans, a row with constant y
. The first published complete example works on the following basic principle. [1]
lx
and rightmost filled point rx
. This defines the span.lx
to rx
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 explores spans depth first, whilst a queue explores spans breadth first.
This algorithm is the most popular, for both citations and implementations [ citation needed ], despite testing most filled pixels three times in total.
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 sspan_added = true
Over time, the following optimizations were realized:
The final, combined-scan-and-fill span filler was then published in 1990. In pseudo-code form: [8]
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 sx1 = x1 + 1 while x1 < x2 and not Inside(x1, y): x1 = x1 + 1 x = x1
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. [3]
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. [9] Unfortunately, it had bugs that made it not complete some fills. [10] 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. [10] A later published algorithm depended on the boundary being distinct from everything else in the image and so isn't suitable for most uses; [11] [3] it also requires an extra bit per pixel for bookkeeping. [3]
A method exists that uses essentially no memory for four-connected regions by pretending to be a painter trying to paint the region without painting themselves into a corner. This is also 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:
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.
This algorithm was first available commercially in 1981 on a Vicom Image Processing system manufactured by Vicom Systems, Inc. [ citation needed ] A walking algorithm was published in 1994. [12] The classic recursive flood fill algorithm was available on the Vicom system as well.
This is a pseudocode implementation of an optimal fixed-memory flood-fill algorithm written in structured English:
cur
, mark
, and mark2
each hold either pixel coordinates or a null value mark
is set to null, do not erase its previous coordinate value. Keep those coordinates available to be recalled if necessary.cur-dir
, mark-dir
, and mark2-dir
each hold a direction (left, right, up, or down)backtrack
and findloop
each hold boolean valuescount
is an integercur-dir
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 thenif 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: setcount to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY) ifcountis not 4 thendo turn right while front-pixel is inside do turn left while front-pixel is not inside end ifswitchcount case 1 if backtrack is true then set findloop to true else if findloop is true thenif mark is null then restore mark end ifelse 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 thenif front-left-pixel is inside then clear mark set cur jump to PAINT end ifelse if mark is not set then set mark to cur set mark-dir to cur-dir clear mark2 set findloop and backtrack to false elseif mark2 is not set thenif cur is at mark thenif 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 ifelse if findloop is true then set mark2 to cur set mark2-dir to cur-dir end ifelseif 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 ifend ifend 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
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 condition.
In 3D computer graphics, ray tracing is a technique for modeling light transport for use in a wide variety of rendering algorithms for generating digital images.
Scanline rendering is an algorithm for visible surface determination, in 3D computer graphics, that works on a row-by-row basis rather than a polygon-by-polygon or pixel-by-pixel basis. All of the polygons to be rendered are first sorted by the top y coordinate at which they first appear, then each row or scan line of the image is computed using the intersection of a scanline with the polygons on the front of the sorted list, while the sorted list is updated to discard no-longer-visible polygons as the active scan line is advanced down the picture.
Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image, as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures. It is an incremental error algorithm, and one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm may be used for drawing circles.
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. The algorithm starts at the root node and explores as far as possible along each branch before backtracking. Extra memory, usually a stack, is needed to keep track of the nodes discovered so far along a specified branch which helps in backtracking of the graph.
In computer graphics, a line drawing algorithm is an algorithm for approximating a line segment on discrete graphical media, such as pixel-based displays and printers. On such media, line drawing requires an approximation. Basic algorithms rasterize lines in one color. A better representation with multiple color gradations requires an advanced process, spatial anti-aliasing.
Maze generation algorithms are automated methods for the creation of mazes.
Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.
In computer science, tree traversal is a form of graph traversal and refers to the process of visiting each node in a tree data structure, exactly once. Such traversals are classified by the order in which the nodes are visited. The following algorithms are described for a binary tree, but they may be generalized to other trees as well.
In computer science, corecursion is a type of operation that is dual to recursion. Whereas recursion works analytically, starting on data further from a base case and breaking it down into smaller data and repeating until one reaches a base case, corecursion works synthetically, starting from a base case and building it up, iteratively producing data further removed from a base case. Put simply, corecursive algorithms use the data that they themselves produce, bit by bit, as they become available, and needed, to produce further bits of data. A similar but distinct concept is generative recursion which may lack a definite "direction" inherent in corecursion and recursion.
In computer graphics, image tracing, raster-to-vector conversion or raster vectorization is the conversion of raster graphics into vector graphics.
In computer science, recursion is a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.
In computer science, tail recursive parsers are a derivation from the more common recursive descent parsers. Tail recursive parsers are commonly used to parse left recursive grammars. They use a smaller amount of stack space than regular recursive descent parsers. They are also easy to write. Typical recursive descent parsers make parsing left recursive grammars impossible. Tail recursive parsers use a node reparenting technique that makes this allowable.
A box blur is a spatial domain linear filter in which each pixel in the resulting image has a value equal to the average value of its neighboring pixels in the input image. It is a form of low-pass ("blurring") filter. A 3 by 3 box blur can be written as matrix
In computer science, graph traversal refers to the process of visiting each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.
Connected-component labeling (CCL), connected-component analysis (CCA), blob extraction, region labeling, blob discovery, or region extraction is an algorithmic application of graph theory, where subsets of connected components are uniquely labeled based on a given heuristic. Connected-component labeling is not to be confused with segmentation.
In the study of image processing, a watershed is a transformation defined on a grayscale image. The name refers metaphorically to a geological watershed, or drainage divide, which separates adjacent drainage basins. The watershed transformation treats the image it operates upon like a topographic map, with the brightness of each point representing its height, and finds the lines that run along the tops of ridges.
In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence.
A maze-solving algorithm is an automated method for solving a maze. The random mouse, wall follower, Pledge, and Trémaux's algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end filling and shortest path algorithms are designed to be used by a person or computer program that can see the whole maze at once.
In computer science, a ball tree, balltree or metric tree, is a space partitioning data structure for organizing points in a multi-dimensional space. A ball tree partitions data points into a nested set of balls. The resulting data structure has characteristics that make it useful for a number of applications, most notably nearest neighbor search.