Areas

Filling of areas

    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

Applet 4 and 8 adjacency of the point P

$$$APPLET

Applet 4-connectivity 8-connectivity. Select first point with mouse. You can change raster size on left side. Author Michal Švirec

Source code

Simple recursive algorithms of filling areas.

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

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);
        }
 }

FloodFill algorithm

$$$APPLET

Applet FloodFill algorithm Author: Bezak Martin

Algorithm source:

Source code

FloodFill algorithm applet 2

$$$APPLET

Applet FloodFill algorithm Author: Peter Kan

Algorithm source:

Boundary Fill Algorithm:

  • Choosing a specific interior point [x,y]- which will be a start point for filling.
  • I will use a 4-connected approach to visualize the functionality of the algorithm.
$$$APPLET

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

Source code

Filling according to parity

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

Reducing the recursion depth

    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.

Raster resolution of a polygon

    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.

Scan-line algorithm

$$$APPLET

Applet Table of edge list (on the right side edge list, which return intersect scan-line)

$$$APPLET

Applet Scan-line algorithm of a polygon; select a line for scan-line right from the vertical abscissa

Fill polygon

$$$APPLET

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 code

Scan line polygon clipping

$$$APPLET

Applet 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
Copyright (c) 1999-2017 Juraj Štugel. www.netgraphics.sk