Line Algorithm

Examples

• 2

  Bresenham Line Drawing Algorithm
  2

  Background Theory: Bresenham’s Line Drawing Algorithm is an efficient and accurate raster line generating algorithm developed by Bresenham. It involves only integer calculation so it is accurate and fast. It can also be extended to display circles another curves.

  In Bresenham line drawing algorithm:
  

  For Slope |m|<1:
  Either value of x is increased
  OR both x and y is increased using decision parameter.
  

  For Slope |m|>1:
  Either value of y is increased
  OR both x and y is increased using decision parameter.
  

  Algorithm for slope |m|<1:
  

  1. Input two end points (x1,y1) and (x2,y2) of the line.

  2. Plot the first point (x1,y1).

  3. Calculate
     Delx =| x2 – x1 |
     Dely = | y2 – y1 |

  4. Obtain the initial decision parameter as
     P = 2 * dely – delx

  5. For I = 0 to delx in step of 1
     
     If p < 0 then
     X1 = x1 + 1
     Pot(x1,y1)
     P = p+ 2dely
     
     Else
     X1 = x1 + 1
     Y1 = y1 + 1
     Plot(x1,y1)
     P = p + 2dely – 2 * delx
     
     End if
     
     End for
     

  6. END

  Source Code:

  /* A C program to implement Bresenham line drawing algorithm for |m|<1 */
  #include<stdio.h>
  #include<conio.h>
  #include<graphics.h>
  #include<math.h>
  
  int main()
  {    
   int gdriver=DETECT,gmode;
   int x1,y1,x2,y2,delx,dely,p,i;
   initgraph(&gdriver,&gmode,"c:\\TC\\BGI");
  
  printf("Enter the intial points: ");
  scanf("%d",&x1);
  scanf("%d",&y1);
  printf("Enter the end points: ");
  scanf("%d",&x2);
  scanf("%d",&y2);
  
  putpixel(x1,y1,RED);
  
  delx=fabs(x2-x1);
  dely=fabs(y2-y1);
  p=(2*dely)-delx;
  for(i=0;i<delx;i++){
  if(p<0)
  {
   x1=x1+1;
   putpixel(x1,y1,RED);
   p=p+(2*dely);
  }
  else
  {
   x1=x1+1;
   y1=y1+1;
   putpixel(x1,y1,RED);
   p=p+(2*dely)-(2*delx);
  }
  }
   getch();
   closegraph();
   return 0;
  }
  

  Algorithm for slope |m|>1:

  1. Input two end points (x1,y1) and (x2,y2) of the line.
  2. Plot the first point (x1,y1).
  3. Calculate
     Delx =| x2 – x1 |
     Dely = | y2 – y1 |
  4. Obtain the initial decision parameter as
     P = 2 * delx – dely
  5. For I = 0 to dely in step of 1
     
     If p < 0 then
     y1 = y1 + 1
     Pot(x1,y1)
     P = p+ 2delx
     
     Else
     X1 = x1 + 1
     Y1 = y1 + 1
     Plot(x1,y1)
     P = p + 2delx – 2 * dely
     
     End if
     
     End for
     
     
  6. END

  Source Code:

  /* A C program to implement Bresenham line drawing algorithm for |m|>1 */
  #include<stdio.h>
  #include<conio.h>
  #include<graphics.h>
  #include<math.h>
  int main()
  {
  int gdriver=DETECT,gmode;
  int x1,y1,x2,y2,delx,dely,p,i;
  initgraph(&gdriver,&gmode,"c:\\TC\\BGI");
  printf("Enter the intial points: ");
  scanf("%d",&x1);
  scanf("%d",&y1);
  printf("Enter the end points: ");
  scanf("%d",&x2);
  scanf("%d",&y2);
  putpixel(x1,y1,RED);
  delx=fabs(x2-x1);
  dely=fabs(y2-y1);
  p=(2*delx)-dely;
  for(i=0;i<delx;i++){
  if(p<0)
  {
  y1=y1+1;
  putpixel(x1,y1,RED);
  p=p+(2*delx);
  }
  else
  {
  x1=x1+1;
  y1=y1+1;
  putpixel(x1,y1,RED);
  p=p+(2*delx)-(2*dely);
  }
  }
  getch();
  closegraph();
   return 0;
  }
  

  edited Jan 20 at 11:44

  

  
  discuss