Bresenham’s Line Generation Algorithm

Bresenham's Line Generation Algorithm

Bresenham's line algorithm is a line  drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap images, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures.

Algorithm:

                          (x0,y0)                             // initial points of line

                          (x1,y1)                             // end points of line

                          dx=x1-x0                        

                          dy=y1-y0

                       

                          x=x0

                          y=y0

                          p=2dy-dx

                         while(x<=x1): 

                                  putpixel(x,y)

                                  x=x+1

                                  if (p<0):

                                        p=p+2dy

                                  else:

                                       p=p+2dy-2dx

                                       y=y+1