4.Midpoint Circle Algorithm

Overview

Midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle.
Circle is a frequently used component in pictures and graphs.
Center Position : (xc , yc )
Distance : r ( Radius )

This distance relationship is expressed by the Pythagorean theorem in Cartesian coordinates as

(x – xc)2 + (y – yc)2 = r2

the above equation can be used to calculate the successive y values by stepping x values as

y = yc ± Ö r2 – (xc – x)2

but in this method, the computation time is high and spacing between pixels is not uniform. One way to eliminate the unequal spacing is to calculate points using polar coordinates r and q.

                        x = xc + r cos q

                        y = yc + r sin q

the step size for q value depends on the display device.

Computations can be reduced by considering the symmetry of circles. The shape of the circle is similar in each quadrant, more over in each octant also. Once the pixel positions at one octant is calculated its reflection can also be obtained as shown in the figure.

In these cases, the computation time is high. To reduce the computation time the midpoint algorithm used for circle drawing.


Mid-Point Circle Algorithm

Screen Center Point : (xc , yc )
Calculate Pixel Position : ( x, y )
Screen Posisotn Adding :
xc = xc + x
yc = yc + y

The circle function is defined as:
¦circle (x,y) = x2 + y2 – r2

any point (x,y) on the boundary of the circle with radius r satisfies the equation ¦circle(x,y)=0, that is

                            < 0, if (x,y) is inside the circle boundary
¦circle (x,y)             = = 0, if (x,y) is on the circle boundary
                            > 0, if (x,y) is outsider the circle boundary

the relative position of any point can be determined by checking the sign of the circle function.

Sampling Position :
(xk , yk )
Next Determine,
(xk+1, yk) or (xk+1, yk-1)
The circle function tests in the above equation are performed for the midpoints between pixels near the circle path at each sampling step. The figure shows the midpoint between two pixels. Assuming we have just plotted the pixel at (xk,yk). We next need to determine whether the pixel at position (xk+1, yk) or the one at position (xk+1, yk-1) is closer to the circle. The decision parameter is calculated as

    pk = ¦circle (xk+1, yk – ½ )
        = (xk+1)2 + (yk- ½)2 – r2

if pk > 0, this midpoint is inside the circle and the pixel on scan line yk is closer to the circle boundary. Otherwise, the mid-position is outside or on the circle boundary, and we select the pixel on scan-line yk-1.

Successive decision parameters are obtained using incremental calculations. P
    pk+1 = ¦circle (xk+1 + 1, yk+1 – ½ )
            = [ (xk+1) + 1 ]2 + [yk+1 – ½ ]2 – r2

    or pk+1 = pk + 2(xk+1) + (yk+12- yk2) – (yk+1 – yk) + 1

where yk+1 is either yk or yk-1, depending on the sign of pk.
Increments for obtaining pk+1 are either 2xk+1 + 1 (if pk is negative) or 2xk+1 + 1 – 2yk+1. Evaluation of the terms 2xk+1 and 2yk+1 can also be done incrementally as

            2xk+1 = 2xk + 2
            2yk+1 = 2yk – 2

Two Terms ( 0,r ) and (0,2r)
Each successive value is obtained by adding 2 to the previous value of 2x and subtracting 2 from the previous value of 2y.

The initial decision parameter is obtained by evaluating the circle function at the start position (x0,y0) = (0,r):

p0 = ¦circle (1, r- ½)

= 1 + (r- ½)2 – r2

(or) p0 = 5/4 – r

if the radius r is specified as an integer, we can simply round p0 to
p0 = 1 – r (for r an integer)
since all increments are integers.


The steps involved in the midpoint circle algorithm as follows:

1.      Input radius r and circle centre (xc,yc), and obtain the first poitn on the circumference of a circle            centered on the origin as (x0,y0) = (0, r).
2.      Calculate the initial value of the decision parameter as p0 = 5/4 – r
3.      At each xk position, starting at k=0, perform the following test: if pk < 0, the next point along the circle centered on (0,0) is (xk+1, yk) and p
                  pk+1 = pk + 2xk+1 + 1
      otherwise, the next point along the circle is (xk+1, yk-1) and
                  pk+1 = pk + 2xk+1 + 1 – 2yk+1 where
                  2xk+1 = 2xk + 2; and 2yk+1 = 2yk - 2
4.      Determine symmetry points in the other seven octants.
5.      Move each calculated pixel position (x,y) onto the circular path cetered on (xc,yc) and plot the coordinate values.   x = x + xc,       y = y + yc
6.      Repeat steps 3 through 5 until x ³ y.


Circle Algorithm Using C Programming

#include<stdio.h>
#include<conio.h>
#include<graphics.h>

void main()
{
 int gd=DETECT,gm;
 int x,y,r;
 void Drawcircle(int,int,int);
 printf("Enter the Mid points and Radious:");
 scanf("%d%d%d",&x,&y,&r);
 initgraph(&gd,&gm,"");
 Drawcircle(x,y,r);
 getch();
 closegraph();
}

void Drawcircle(int x1,int y1,int r)
{
 int x=0,y=r,p=1-r;
 void cliplot(int,int,int,int);
 cliplot(x1,y1,x,y);
 while(x<y)
 {
 x++;
 if(p<0)
  p+=2*x+1;
  else
  {
   y--;
   p+=2*(x-y)+1;
  }
  cliplot(x1,y1,x,y);
 }
}


void cliplot(int xctr,int yctr,int x,int y)
{
 putpixel(xctr +x,yctr +y,1);
 putpixel(xctr -x,yctr +y,1);
 putpixel(xctr +x,yctr -y,1);
 putpixel(xctr -x,yctr -y,1);
 putpixel(xctr +y,yctr +x,1);
 putpixel(xctr -y,yctr +x,1);
 putpixel(xctr +y,yctr -x,1);
 putpixel(xctr -y,yctr -x,1);
 getch();
}