Midpoint Circle Algorithm

The midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle. A circle is a frequently used component in pictures and graphs.

Center Position : (xc , yc )

Distance : r ( Radius )

The Pythagorean theorem expresses this distance relationship 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 the 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 the 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, moreover, in each octant also. Once the pixel positions at one octant are 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 was used for circle drawing.

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 outside 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 round p0 to

p0 = 1 ? r (for r an integer)

since all increments are integers.

• Input radius r and circle center (xc,yc), and obtain the first point on the circumference of a circle centered on the origin as (x0,y0) = (0, r).

• Calculate the initial value of the decision parameter as p0 = 5/4 – r

• 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

• Determine symmetry points in the other seven octants.

• Move each calculated pixel position (x,y) onto the circular path centered on (xc,yc) and plot the coordinate values.   x = x + xc,       y = y + yc

• Repeat steps 3 through 5 until x ³ y.

#include<stdio.h>

#include<conio.h>

#include<graphics.h>

void main() {

   int gd = DETECT, gm;

   int x, y, r;

   voidDrawcircle(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();

}

• Overview Of Graphics System

  1. Applications of computer graphics

  2. Video Display Devices

  3. Architecture and components of Raster-Scan Systems & Random-Scan Systems

  4. Various Input Devices

• Basic Drawing Techniques

  1. DDA Line Algorithm 

  2. Midpoint Circle Algorithm 

  3. Clipping & Point Clipping