By an area is understood a set of raster points mutually contiguously linked together. Let us define the notion of adjacency for a point. To each raster point P within a raster picture belong eight adjacent points, marked as 0, 1, ?, 7. The points 0, 2, 4, 6 are called direct adjacent points of the point P. We know the following areas: 4-contiguous and 8-contiguous. With a 4-contiguos area (or 8-contiguos) we can interconnect each two points through an order of 4 adjacent points (or of 8 adjacent points) in this area. The area defined by its internal points is called the internally defined area. The area defined by its limits is called limit defined area.
Applet 4 and 8 adjacency of the point P
Applet 4-connectivity 8-connectivity. Select first point with mouse. You can change raster size on left side. Author Michal Švirec
Wave algorithm
This algorithm assigns a new color to the points of a 4-contiguous area if the given point complies with the condition that it is inside of the area being filled.
Applet Filling of areas. Set a starting point.
Wave algorithm filling:
void Filling (int x,int y,Color old_color,Color new_color)
{
if (read_pixel (x,y) == old_color) // pixel color test
{
write_pixel
(x, y, new_color); // paints the pixel in a new color
Filling
(x, y-1, old_color, new_color);
Filling
(x, y+1, old_color, new_color);
Filling
(x-1, y, old_color, new_color);
Filling
(x+1, y, old_color, new_color);
}
}
Algorithm source:
Applet algorithm is designed as real boundary fill alg., but for visibility, it is drawing not only single pixels, but 10x10px squares. By clicking on the canvas, you specify starting point where algorithm is started... Thats why white spaces are creating near borders of other colors...
Author Martin Pullmann
One of the basic procedures in computer graphics is the assignment of a point of a polygon. The point is internal if the half-line parallel to the x axis starting from this point crosses a polygon through an odd number of penetrations of edges (conjunctions). This can be transformed also for the use of filling a polygon. A detailed description is in [1].
One of disadvantages of the previous algorithm is that the algorithm is recursive, and this is not always advantageous. Therefore several effective algorithms reducing the depth of recursion have been created. An algorithm filling an area by lines is one example.
By raster scanning of a polygon is understood the filling of an area the limits of which comprise a polygon. Most usually we proceed so that we make a scanning into lines, and then, we use the scan-line algorithm.
Applet Table of edge list (on the right side edge list, which return intersect scan-line)
Applet Scan-line algorithm of a polygon; select a line for scan-line right from the vertical abscissa
Fill pogygon. Set points for polygon. You can set color for each new point. After finish press button "vykresli". You get colored polygon created with scan-line alghoritm. Press "zmaz" button for clear scene. Author Dzurec Jan
Source codeApplet Scan line polygon clipping. Set polygon type from 3 to 6 points, then you can move these points. Press mouse on right side of vertical line for points from scan-line alghoritm. Author Ľuboš Ľahký
Source code