Graphics Reference
In-Depth Information
Finally, the configuration
1 1 1 1
1 1 0 1
1 1 1 0
1
1
shows that the choice of adjacency is important. The algorithm fails if
C
is a 4-
component and must be changed. See [RosK76].
Algorithm 2.3.1 can be used to find
all
border points of a set
S
. It provides a way
of marking its border points so that one can then fill the interior of
S
using a fill algo-
rithm of the type discussed in the next section.
2.4
Fill Algorithms
Contour-filling algorithms are used in many places. For example, in pattern recogni-
tion problems integrals may have to be computed over areas; in photo typesetting,
fonts are described by contours that are later filled; in animation, the cel painter who
fills figures has the next most time-consuming job after the animator.
There are two broad classes of such algorithms -
polygon-based
(
edge-filling
) algo-
rithms and
pixel-based
algorithms. The former can be used in the case where the
regions to be filled are defined by polygons and we can use the equations for the edges.
The latter are, in a sense, more general because they can be used both for polygonal
regions and also arbitrary regions whose boundaries are defined on the pixel level.
There is also a distinction as to how the algorithm decides whether a point is in
the interior of a region. Some use a
parity check
that is based on the fact that lines
intersect a closed curve an even number of times (if one counts intersections at certain
special points such as at points of tangency correctly). This test is always used in case
of polygon-based algorithms, but can also be used for pixel-based ones. Other algo-
rithms, called
seed fill
algorithms, use connectivity methods. Here it is assumed that
one is given a starting point or seed. Then one sees which pixels can be reached from
this one without crossing the contour. The bounding curves can be quite general. This
approach applies only to pixel-based algorithms. Also, one needs to know an interior
point. This is okay in interactive situations (where one picks one using a mouse, for
example), but if one wants to automate the process, note how border-following algo-
rithms become relevant.
In this section we shall describe the pixel-based seed fill algorithms. Section 2.9.1
will look at polygon-based fill algorithms.
The Flood Fill Problem:
Given
distinct
colors c and c¢, a set
A
of the same color c bounded
by points whose colors are
different
from c and c¢, find an algorithm that changes all points
of
A
and
only
those to the color c¢.
An algorithm that solves this problem is called a
flood fill
algorithm. There are a
number of related fill problems and associated algorithms. For example,
boundary fill
algorithms assume that all points of the boundary have the
same
color, which is
dif-
