Flood fill

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.

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: It's possible to optimize things further by working primarily with spans, a row with constant y.

[1] As an optimisation, the scan algorithm does not need restart from every seed point, but only those at the start of the next span.

In pseudo-code form:[8] 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.

[3] Some theorists applied explicit graph theory to the problem, treating spans of pixels, or aggregates of such, as nodes and studying their connectivity.

[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.

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.

Still using the left-hand rule the painter now searches for a simple passage (made by two boundary pixels).

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.

[12] This is a pseudocode implementation of an optimal fixed-memory flood-fill algorithm written in structured English: 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.