Graphic Design | Midpoint Circle Algorithm

Hi guys! How're you doing?
If you've been following me, we have studied of two methods that help us in drawing a line; The DDA and Bresenham Line Algorithm. We would now want to hence extend our knowledge and draw different things, more complex than a line, isn't it? Here you have it, today we would learn about a method to draw circle. The Mid-Point Circle Algorithm!
First let us possibly stop and imagine at this point how we would like to proceed.
A circle is defined as the set of points that are all at a given distance r from a centre position (x, y). The equation for the same is as following:

Just as we did in the last two methods, where we drew a line, we can use this equation, the characteristic equation of the curve we want to plot again and assuming values for one variable, derive values of the other in the following manner:

Also, another possible manner in which we might proceed is by using the polar coordinates for plotting a circle. Recall them from your High School lessons.

So right here, you looked at two possible methods on plotting a circle and still I demand that we do not plot using either of them. Rather its not not even I, anyone who is sensible enough will demand the same. Why?
Determining pixel positions along a circle circumference using either Method 1 or 2 still requires a good deal of computation time. The equation from Method 1 involves multiplications and square root calculations, while the parametric equations in Method 2 contain multiplications and trigonometric calculations. More efficient circle algorithms are based on incremental calculation of decision parameters, as in the Bresenham line algorithm, which involves only simple integral addition or subtraction operations,
Hence we find and take a Method 3, which will not involve the disadvantages we discussed above.

Midpoint Circle Algorithm

To form a brief introduction of the algorithm we are about to study, we perform unit increments along one axis while calculating the respective increment for the other axis, in accordance with the closest pixel position to the specified circle path at each step. Initially we assume the centre of the Cartesian plane, the origin, as the centre of our circle. Hence for a given radius r and screen centre position ( x , y,), we can first set up our algorithm to calculate pixel positions around a circle path centred at the coordinate origin (0,0).
Now as we now have performed the required calculations, we then need to move each calculated position (x, y) to its proper screen position by adding x, to x and y, to y. Along the circle section from x = 0 to x = y in the first quadrant, the slope of the curve varies from 0 to -1. Therefore, we can take unit steps in the positive x direction over this octant and use a decision parameter to determine which of the two possible y positions is closer to the circle path at each step. Positions in the other seven octants are then obtained by symmetry as shown here:

 
To apply the midpoint method, we define a circle function:

Just like we did in the earlier algorithms, after the point where we have the initial coordinates and the equation of the curve we wish to plot, we look forward to obtaining a simple binary variable called the decision parameter. Any point (x , y) on the boundary of the circle with radius r satisfies the above equation. If the point is inside the circle, the above circle function is negative. If the point is outside the circle, the above circle function is positive. To summarize, the relative position of any point (x, y) can be determined by checking the sign of the circle function as below:

Now maintaining an analogy with our previous lessons, what we achieved just above was the expression for the initial decision parameter. For performing subsequent calculations, we need to calculate the expression for subsequent decision parameters. To do so, we perform the following derivation using the following image for reference:



Assuming we have just plotted the pixel at (x_k, y_k), we next need to determine whether the pixel at position (x_k+1, y_k) or the one at position (x_k+1, y_k-1) is closer to the circle. The above diagram shows the midpoint between those two candidate pixels at sampling position x_k+1. Our new decision parameter is the circle function evaluated at the midpoint between these two pixels:



At this point as you might be able to see, we have the expressions for both p_k and p_k+1. Let us finish this up.

To find the decision parameter for the initial calculation, p₀, we substitute x_k=0 and y_k=r in the expression for p_k since we plotted our first point at the coordinates (0,r). Hence:


Having the initial coordinates to plot and the initial decision parameter to decide future points to be plotted, we know are left with only finding the requisite decision parameter for each subsequent calculation and the appropriate increment in X and Y axes. Hence:

• if p_k (or p₀) < 0 we increment along X Axis keeping the Y Coordinate the same. So x_k+1 = x_k + 1 while y_k+1 = y_k. The expression for p_k+1 is
• if p_k (or p₀) > 0 we increment along both the X and the Y Axes. So x_k+1 = x_k + 1 and y_k+!=y_k+1. The expression for p_k+1 is

Having obtained all of the required coordinates for the circle we wanted to form, the only thing left now is translating these very same coordinates to the required location. This is done by adding the distance we want to shift each point of the circle with in the original coordinate. Hence assuming the circle coordinates to be of the form (x,y) and (x_c, y_c) being the coordinates of the centre about which our actual circle is meant to be produced, we perform this last set of manipulations

With this we finish the conceptual and theoretical part of Midpoint Circle Algorithm. Let us revise the algorithm before moving on to see its implementation.

Moving on towards its implementation in C, we can use the code as following and see it for ourselves how it performs.

//Shubham Mehta, Write a program to implement Midpoint Circle Algorithm.
#include <iostream.h>
#include <conio.h>
#include <graphics.h>
void main()
{
 int gd=DETECT,gm;
 initgraph(&gd, &gm, "C:\\TC\\bgi"); 
 float r,x0,y0,x,y,pk;
 cout<<"Enter the radius of the circle: ";
 cin>>r;
 cout<<"Enter the center...";
 cout<<"X Coordinate: ";
 cin>>x0;
 cout<<"Y Coordinate: ";
 cin>>y0;
 pk=1.25-r;
 x=0;
 y=r;
 while(x<=y)
 {
  if(pk>0)
  {
   x++;
   y--;
   pk=pk+2*x-2*y+1;
   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+2*x+1;
   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 Midpoint Circle Algorithm. Hope you really learned something. You may see the references here. See you later. Take care :)