Boundary-Fill Algorithm

Another approach [6] to area filling is to start at a point inside a region and paint the interior outward toward the boundary. If the boundary is specified in a single color, the fill algorithm proceeds outward pixel by pixel until the boundary color is encountered. This method, called the boundary-fill algorithm, is particularly useful in interactive painting packages, where interior points are easily selected. Using a graphics tablet or other interactive device, an artist or designer can sketch a figure outline, select a fill color or pattern from a color menu, and pick an interior point. The system then paints the figure interior. To display a solid color region (with no border), the designer can choose the fill color to be the same as the boundary color.

A boundary-fill procedure [6] accepts as input the coordinates of an interior point (x, y), a fill color, and a boundary color. Starting from (x, y), the procedure tests neighboring positions to determine whether they are of the boundary color. If not, they are painted with the fill color, and their neighbors are tested. This process continues until all pixels up to the boundary color for the area have been tested. Both inner and outer boundaries can be set up to specify an area, and some examples of defining regions for boundary fill are shown in Fig. 4.4.

Fig.4.4. Example Color Boundaries for a Boundary-Fill Procedure[6]

Figure 4.5 shows two methods for proceeding to neighboring pixels from the current test position. In Fig. 4.5(a), four neighboring points are tested. These are the pixel positions that are right, left, above, and below the current pixel. Areas filled by this method are called 4-connected. The second method, shown in Fig. 4.5(b), is used to fill more complex figures. Here the set of neighboring positions to be tested includes the four diagonal pixels. Fill methods using this approach are called 8-connected. An 8-connected boundary-fill algorithm would correctly fill the interior of the area defined in Fig. 4.6, but a 4-connected boundary-fill algorithm produces the partial fill shown.

The following procedure illustrates a recursive method for filling a 4-connected area with an intensity specified in parameter fill up to a boundary color specified with parameter boundary. We can extend this procedure to fill an 8-connected region by including four additional statements to test diagonal positions, such is (x+1, y+1).

Fig.4.5. 4-connected area (a) and 8-connected area (b)

Fig.4.6. The area defined within the color boundary (a) is only

partially filled in (b) using a 4-connected boundary-fill

algorithm

void boundaryFill4 (int x, int y, int fill, int boundary)

{

int current;

current = getpixel (x, y);

if ((current!= boundary) && (current!= fill)) {

setcolor (fill);

setpixel (x, y);

boundaryFill4 (x+l, y, fill, boundary);

boundaryFill4 (x-1, y, fill, boundary);

boundaryFill4 (x, y+l, fill, boundary);

boundaryFill4 (x, y-1, fill, boundary);

}

}

Recursive boundary-fill algorithms may not fill regions correctly if some interior pixels are already displayed in the fill color. This occurs because the algorithm checks next pixels both for boundary color and for fill color. Encountering a pixel with the fill color can cause a recursive branch to terminate, leaving other interior pixels unfilled. To avoid this, we can first change the color of any interior pixels that are initially set to the fill color before applying the boundary-fill procedure.

Also, since this procedure requires considerable stacking of neighboring points, more efficient methods are generally employed. These methods fill horizontal pixel spans across scan lines, instead of proceeding to 4-connected or 8-connected neighboring points. Then we need only stack a beginning position for each horizontal pixel span, instead of stacking all unprocessed neighboring positions around the current position. Starting from the initial interior point with this method, we first fill in the contiguous span of pixels on this starting scan line. Then we locate and stack starting positions for spans on the adjacent scan lines, where spans are defined as the contiguous horizontal string of positions bounded by pixels displayed in the area border color. At each subsequent step, we unstack the next start position and repeat the process.

Поиск по сайту: