Bresenham’s Circle Algorithm

Hey guys!
Today we will be learning another approach to drawing circles in Computer Graphics. Basically another approach to the same task we tackled in the previous post. Bresenham’s Circle Algorithm follows the footsteps of Midpoint Circle Algorithm, both working for the same purpose in slightly different ways. Let us see how.



Let us start with the equation of the circle, as here

One thing we must keep in mind is that a circle can be assumed to be symmetrical among octants. Hence we could (and do) calculate pixel coordinates for only one octant to plot and the rest could be obtained via symmetry. We can see the diagram for the same here:

Hence in this lesson, we will perform all our operations for the quadrant lying between 45 to 90 degrees. The slope is < 1 in this region. Hence we will have to introduce unit increments along X Axis at every iteration while calculating the increment along Y for the same.

Further, this algorithm is based on the fact that

• the value of the Y coordinate remains the same for the subsequent iteration

or

• the value of Y coordinate is decreased by unit amount

Hence if the initial points for a calculation are (x_k, y_k), the subsequent points we can have according to our subsequent calculations, can only be either

• (x_k+1, y_k), or
• (x_k+1, y_k-1)

Hence, the magnitude of the two distances of the two different pixel positions from the projected path of circle, according to the following diagram

leaves us with the following two equations for the subsequent points at each iteration we could choose

Now to obtain a decision parameter p_k, we add up the above two equations and obtain the expression

Now that we have the expression for p_k, we can obtain the expression for p₀. We would do so by replacing x_k, y_k by (0,r), as we start plotting our circle from this coordinate. By doing so, we get

So now we have the initial coordinates needed to plot, the initial decision parameter to decide upon the subsequent coordinates to be plotted. Let us make some decisions then!

• if p_k (or p₀) < 0, d₁ is lesser than d₂. Hence the subsequent pixel coordinates for the next point to plot will be (x_k+1, y_k) and the expression for the subsequent decision parameter will be 
  
• if p_k (or p₀) > 0, d₁ is greater than d₂. Hence the subsequent pixel coordinates for the next point to plot will be (x_k+1, y_k-1) and the expression for the subsequent decision parameter will be 
  

And with that we complete our theoretical analysis of Bresenham's Circle Algorithm. Let us see its code implementation.

//Shubham Mehta, Write a program to implement Bresenham's Circle Algorithm.
#include <stdio.h>
#include <conio.h>
#include <graphics.h>
void main()
{
 int gd=DETECT,gm;
 int radius, x0, y0, x, y, pk;
 initgraph(&gd, &gm, "C:\\TC\\BGI");
 printf("%s", "Enter the radius of the circle: ");
 scanf("%d", &radius);
 printf("%s", "Enter the coordinates of the center...\nX: ");
 scanf("%d", &x0);
 printf("%s", "Y: ");
 scanf("%d", &y0);
 pk=3-2*radius;
 x=0;
 y=radius;
 while(x<=y)
 {
  if(pk>0)
  {
   x++;
   y--;
   pk=pk+4*x-4*y+10;
   putpixel(x+x0,y+y0,WHITE);
   putpixel(y+x0,x+y0,WHITE);
   putpixel(-x+x0,-y+y0,WHITE);
   putpixel(-x+x0,y+y0,WHITE);
   putpixel(-y+x0,-x+y0,WHITE);
   putpixel(x+x0,-y+y0,WHITE);
   putpixel(-y+x0,x+y0,WHITE);
   putpixel(y+x0,-x+y0,WHITE);
  } 
  if(pk<0)
  {
   x++;
   y=y;
   pk=pk+4*x+6;
   putpixel(x+x0,y+y0,WHITE);
   putpixel(y+x0,x+y0,WHITE);
   putpixel(-x+x0,-y+y0,WHITE);
   putpixel(-x+x0,y+y0,WHITE);
   putpixel(-y+x0,-x+y0,WHITE);
   putpixel(x+x0,-y+y0,WHITE);
   putpixel(-y+x0,x+y0,WHITE);
   putpixel(y+x0,-x+y0,WHITE);
  }
 }
 getch();
 closegraph();
}

With that, we complete our lesson on Bresenham's Circle Algorithm. You may see the references here. Hope I made some things clear. For any doubts, feel free to contact me in the comments. See you later :)