PRESENTATION

 PRESENTATION

 https://www.slideshare.net/avelraj/lecture-filling-algorithms

https://www.slideshare.net/kumar_vic/fill-areaalgorithms

 

FILL ALGORITHM:  

Polygon Fill Algorithm 

• Different types of Polygons 

– Simple Convex 

– Simple Concave 

– Non-simple : self-intersecting 

– With holes

Polygon surfaces 

A polygon is an important graphics primitive.

A polygon is a closed area of image bounded by straight or curved lines and filled with one solid color. 

Since images are two dimensional, a polygon is a closed planar figure.  

A polygon can be defined as an image which consists of a finite ordered set of straight boundaries called edges . 

The polygon can also be defined by an ordered sequence of vertices , i.e, the corners of the polygon. 

The edges of the polygon are then obtained by traversing the vertices in the given order; 

Two consecutive vertices define one edge. 

The polygon can be closed by connecting the last vertex to the first.

 

Area Filling Algorithms 

Scan line polygon fill algorithm 

Boundary fill algorithm 

Flood fill algorithm 

 

 

Inside-outside tests

Odd-even rule (odd parity rule or even-odd rule) 

Counting the number of edge crossing along the line from point P to infinity 

Odd number ->  interior point P 

Even number ->  exterior point P 

Non-zero winding number rule (vector method) 

-> winding number: no of times that the polygon edges wind around a point in the counterclockwise direction 

-> if the winding number = 0 ->  exterior point 

-> if the winding number != 0 ->  interior point

 

<IMAGE>

 

 Boundary Fill 

Suppose that the edges of the polygon has already been colored. 

Suppose that the interior of the polygon is to be colored a different color from the edge. 

Suppose we start with a pixel inside the polygon, then we color that pixel and all surrounding pixels until we meet a pixel that is already colored.  

 

 Boundary Fill

 void boundaryFill(int x, int y, int fillColor, int borderColor) { 

int interiorColor; 

getPixel(x,y,interiorColor);

if ((interiorColor!=borderColor)&&(interiorColor!=fillColor)) {

setPixel(x,y,fillColor);

boundaryFill(x+1,y,fillColor,borderColor);

boundaryFill(x-1,y,fillColor,borderColor);

boundaryFill(x,y+1,fillColor,borderColor);

boundaryFill(x,y-1,fillColor,borderColor);

}

}

 <IMAGE>

 

 Flood Fill 

Suppose we want to color the entire area whose original color is interiorColor, and replace it with fillColor.

Then, we start with a point in this area, and then color all surrounding points until we see a pixel that is not interiorColor.

 

void floodFill(int x, int y, int fillColor, int interiorColor) { 

int color; 

getPixel(x,y,color);

if (color==interiorColor) { 

setPixel(x,y,fillColor);

floodFill(x+1,y,fillColor,interiorColor);

floodFill(x-1,y,fillColor,interiorColor);

floodFill(x,y+1,fillColor,interiorColor);

floodFill(x,y-1,fillColor,interiorColor); 

} 

}

 

  <IMAGE>

THANK YOU