Bresenham’s Line Drawing Algorithm

  1. Read two end points (x1,y1) and (x2,y2) store initial point (x1,y1)
  2. Load (x1,y1) into frame buffer and plot it.
  3. calculate decision perimeter P it as follows:
    • p=2 Δx-Δy
    • where Δx=x2-x1 and Δy=y2-y1
  4. if p<0 then the next point to plot is (x,y+1) and p=p Δx+2 otherwise the next point is (x+1,y+1) and p=p+2Δx+2Δy
  5. Repeat step 4  Δy times

now we have

x1=0,y1=0,x2=3 and y2=8

Δx=x2-x1=3

Δy=y2-y1=-2

p= 2Δx- Δy=-2

Now the loop steps can be talculated as:

algo

Scan-Line Polygon Fill Algorithm

The Scan-Line Polygon Fill Algorithm is very efficient and cheaper alternative it is also known as Alternative fill method. In this method scan lines are used for filling the polygon.It’s wokig effectively with the self intersecting polygon

In this we have to use the smallest rectangle which fits the polygon which needs the rectangle to be created from the lower left corner to the upper right corner co-ordinate of the polygon for generating the scan line we have to consider the largest by value and move towards the smallest by value and draw a horizontal line among all possible values of y since we are using scan line to fill the polygon this method is known as scan line fill method

Scan line polygon fill algorithm
 
Step 1 Determine the smallest possible rectangle which fits in the polygon to be filled
Step 2 Arrange all the edges of polygon in the order of y values
Step 3 Determine all the polygon edges which are required to be considered with current scan line
Step 4 Find the intersection points between the scan line and all the ages under consideration
Step 5 Draw a line segment between the two successive pairs of intersection points 
Step 7 Shift to the next cell line and also check for the possible exclusion and inclusion of new boundary of the polygon for the concentration