Midpoint Circle Generation Algorithm
Using Midpoint circle generation algorithm which is a variant of Bresenham's line algorithm, write a C- Program to generate pixel activation list for drawing a circle with a given centre of circle P(x, y) and a radius r?
Aim: To implement midpoint circle generation algorithm or bresenham’s circle algorithm for drawing a circle of given center (x, y) and radius r.
Description:
Circles have the property of being highly symmetrical, which is handy when it comes to drawing them on a display screen.
- We know that there are 360 degrees in a First we see that a circle is symmetrical about the x axis, so only the first 180 degrees need to be calculated.
- Next we see that it's also symmetrical about the y axis, so now we only need to calculate the first 90
- Finally we see that the circle is also symmetrical about the 45 degree diagonal axis, so we only need to calculate the first 45
- We only need to calculate the values on the border of the circle in the first The other values may be determined by symmetry.
Bresenham's circle algorithm calculates the locations of the pixels in the first 45 degrees. It assumes that the circle is centered on the origin. So for every pixel (x, y) it calculates, we draw a pixel in each of the eight octants of the circle. This is done till when the value of the y coordinate equals the x coordinate. The pixel positions for determining symmetry are given in the below algorithm.
- Assume that we have just plotted point (xk, yk)
- The next point is a choice between (xk+1, yk) and (xk+1, yk-1)
- We would like to choose the point that is nearest to the actual circle
- So we use decision parameter here to
Algorithm:
- Input radius r and circle centre (xc, yc), then set the coordinates for the first point on the circumference of a circle centred on the origin as:
( x 0 ,y 0 ) =( 0 , r )
- Calculate the initial value of the decision parameter as:
p = 5 - r
4
- Starting with k = 0 at each position xk, perform the following If pk < 0, the next point along the circle centred on (0, 0) is (xk+1, yk) and:
p k + 1 =p + 2 x k + 1 + 1
Otherwise the next point along the circle is (xk+1, yk-1) and:
p k + 1 =p + 2 x k + 1+ 1 -2 y k + 1
- Determine symmetry points in the other seven octants
- Move each calculated pixel position (x, y) onto the circular path centred at (xc, yc) to plot the coordinate values:
- Repeat steps 3 to 5 until x >= y
x = x + xc y = y + yc
Symmetric pixel positions:
- putpixel(xc+x,yc-y,GREEN); //For pixel (x,y)
- putpixel(xc+y,yc-x, GREEN); //For pixel (y,x)
- putpixel(xc+y,yc+x, GREEN); //For pixel (y,-x)
- putpixel(xc+x,yc+y, GREEN); //For pixel (x,-y)
- putpixel(xc-x,yc+y, GREEN); //For pixel (-x,-y)
- putpixel(xc-y,yc+x, GREEN); //For pixel (-y,-x)
- putpixel(xc-y,yc-x, GREEN); //For pixel (-y,x)
- putpixel(xc-x,yc-y, GREEN); //For pixel (-x,y)
Program:
#include<dos.h>
#include<stdio.h>
#include<conio.h>
#include<graphics.h>
void draw_circle(int,int,int);
void symmetry(int,int,int,int); void main()
{
int xc,yc,R;
int gd=DETECT,gm; initgraph(&gd,&gm,"C:\\TurboC3\\BGI"); printf("Enter the center of the circle:\n"); printf("Xc =");
scanf("%d",&xc);
printf("Yc =");
scanf("%d",&yc);
printf("Enter the radius of the circle :"); scanf("%d",&R);
draw_circle(xc,yc,R); getch(); closegraph();
}
void draw_circle(int xc,int yc,int rad)
{
int x = 0; int y = rad;
int p = 1-rad; symmetry(x,y,xc,yc); for(x=0;y>x;x++)
{
if(p<0)
p += 2*x + 3; else
{
p += 2*(x-y) + 5;
y--;
}
symmetry(x,y,xc,yc); delay(50);
}}
void symmetry(int x,int y,int xc,int yc)
{
putpixel(xc+x,yc-y,GREEN); //For pixel (x,y) delay(50);
putpixel(xc+y,yc-x, GREEN); //For pixel (y,x) delay(50);
putpixel(xc+y,yc+x, GREEN); //For pixel (y,-x)
delay(50);
putpixel(xc+x,yc+y, GREEN); //For pixel (x,-y) delay(50);
putpixel(xc-x,yc+y, GREEN); //For pixel (-x,-y) delay(50);
putpixel(xc-y,yc+x, GREEN); //For pixel (-y,-x) delay(50);
putpixel(xc-y,yc-x, GREEN); //For pixel (-y,x) delay(50);
putpixel(xc-x,yc-y, GREEN); //For pixel (-x,y) delay(50);
}
Output:
