Theory/Logic:
If a circle is to be plotted efficiently, the use of trigonometric and power functions must be avoided. And as with the generation of a straight line, it is also desirable to perform the calculations necessary to find the scan-converted points with only integer addition, subtraction, and multiplication by powers of 2. Midpoint circle algorithm allows these goals to be met.
Scan-converting a circle using midpoint algorithm works are follows. If the eight-way symmetry of a circle is used to generate a circle, points will only have to be generated through a 45° angle. And, if points are generated from 90 to 45°, moves will be made only in the +x and -y directions (see Figure 4).
Figure 4 Circle scan-converted with Midpoint algorithm.
The best approximation of the true circle will be described by those pixels in the raster that fall the least distance from the true circle. Examine Figures 5(a) and 5(b). Notice that if points are generated from 90 and 45°, each new point closest to the true circle can be found by taking either of two actions: (1) move in the x direction one unit or (2) move in the x direction one unit and move in the negative y direction one unit. Therefore, a method of selecting between these two choices is all that is necessary to find the points closest to the true circle.
Due to the 8-way symmetry, we need to concentrate only on the are from (0, r) to . Here we assume r to be an integer.
Suppose that P(xi, yi) has been selected as closest to the circle. The choice of the next pixel is between U and D (Fig.6).
Figure 6
w Let F(x, y) = x2 + y2 - r2. We know that
F(x, y) = 0 then (x, y) lies on the circle
> 0 then (x, y) is outside
the circle
< 0 then (x, y) is inside the circle
Let M be the midpoint of DU. If M is outside then pixel D is closer to the circle, and if M is inside, pixel U is closer to the circle.
w Let dold = F(xi+1, yi
- )
= (xi + 1)2 + (yi
- )2
-
r2
* If dold < 0, then U (xi+1, yi) is chosen and the next midpoint will be one increment over x.
Thus
dnew = F(xi+2, yi
- )
= dold
+ 2xi + 3
The increment in d is
dU = dnew
-
dold = 2xi + 3
* If dold
³ 0, M is outside the circle and D is chosen. The new midpoint will be one increment over x and one increment down in y:
dnew = F (xi + 2, yi
- )
= dold + 2xi
- 2yi + 5
The increment in d is therefore
dD = dnew
-
dold = 2(xi
-
yi ) + 5
Since the increments dU and dD are functions of (xi , yi), we call point P(xi, yi) the point of evaluation.
w Initial point: (0, r). The next midpoint lies at (1, r- ) and so
F (1, r
- ) = 1 + (r
- )2
-
r2 = -
r
Figure 5 Midpoint Circle Algorithm
Midpoint Circle Algorithm
h = 1 -
r ; /*initialization */
x = 0;
y = r;
Plot Point (x, y);
While y > x
if h < 0 then /* Select U */
dU = 2*x + 3;
h = h + dU;
x = x + 1;
else /* Select D */
dD = 2*(x
-
y) + 5;
h = h
-
dD;
x = x + 1;
y = y
- 1;
endif
End While
Advantage:
This faster method to draw a circle then conventional method.
Disadvantages:
Accumalation of error at every step because of rounding
Source code
#include<stdio.h>
#include<graphics.h>
#include<math.h>
int midalgo(int ,int ,int,int);
void plotpoints(int ,int, int,int,int,int);
int k=0;
void main()
{
int xc,yc,rad,choice;
int gdriver=DETECT, gmode;
char c;
initgraph(&gdriver, &gmode, "C:\\TC\\BGI");
start:
clrscr();
rectangle(0,70,getmaxx(),getmaxy());
line(getmaxx()/2, 70, getmaxx()/2, getmaxy());
line(0, getmaxy()/2+35, getmaxx(), getmaxy()/2+35);
printf("1.Solid 2.Dash 3.Dash dot 4.Exit\n");
scanf("%d",&choice);
if(choice==4)
goto exit;
printf("Enter the center of the circle: ");
scanf("%d %d",&xc,&yc);
printf("Enter the radius: ");
scanf("%d",&rad);
midalgo(xc,yc,rad,choice);
scanf("%c",&c);
//goto start;
exit:
getch();
return;
}
int midalgo(int xc,int yc,int rad,int choice)
{
int p0,x,y,x1,y1;
x1=xc; y1=yc;
x=0;
y=rad;
plotpoints(x1,y1,x,y,k,choice);
p0=1-rad;
while(x<y)
{
if(p0<0)
{
x++;
p0=p0+2*x+1;
}
else
{
x++;
y--;
p0=p0+2*(x-y)+1;
}
k++;
plotpoints(xc,yc,x,y,k,choice);
}
return;
}
void plotpoints(int xc,int yc,int x,int y,int k,int choice)
{
if(choice==1)
{
putpixel((getmaxx()/2)+xc+x, (getmaxy()/2)+35+yc+y, 1);
putpixel((getmaxx()/2)+xc-x, (getmaxy()/2)+35+yc+y, 1);
putpixel((getmaxx()/2)+xc+x, (getmaxy()/2)+35+yc-y, 1);
putpixel((getmaxx()/2)+xc-x, (getmaxy()/2)+35+yc-y, 1);
putpixel((getmaxx()/2)+xc+y, (getmaxy()/2)+35+yc+x, 1);
putpixel((getmaxx()/2)+xc-y, (getmaxy()/2)+35+yc+x, 1);
putpixel((getmaxx()/2)+xc+y, (getmaxy()/2)+35+yc-x, 1);
putpixel((getmaxx()/2)+xc-y, (getmaxy()/2)+35+yc-x, 1);
}
if(choice==2)
{
if(k%2==0)
{
putpixel((getmaxx()/2)+xc+x, (getmaxy()/2)+35+yc+y, 1);
putpixel((getmaxx()/2)+xc-x, (getmaxy()/2)+35+yc+y, 1);
putpixel((getmaxx()/2)+xc+x, (getmaxy()/2)+35+yc-y, 1);
putpixel((getmaxx()/2)+xc-x, (getmaxy()/2)+35+yc-y, 1);
putpixel((getmaxx()/2)+xc+y, (getmaxy()/2)+35+yc+x, 1);
putpixel((getmaxx()/2)+xc-y, (getmaxy()/2)+35+yc+x, 1);
putpixel((getmaxx()/2)+xc+y, (getmaxy()/2)+35+yc-x, 1);
putpixel((getmaxx()/2)+xc-y, (getmaxy()/2)+35+yc-x, 1);
}
}
if(choice==3)
{
if((k%10<5) || k%3==0)
{
putpixel((getmaxx()/2)+xc+x, (getmaxy()/2)+35+yc+y, 1);
putpixel((getmaxx()/2)+xc-x, (getmaxy()/2)+35+yc+y, 1);
putpixel((getmaxx()/2)+xc+x, (getmaxy()/2)+35+yc-y, 1);
putpixel((getmaxx()/2)+xc-x, (getmaxy()/2)+35+yc-y, 1);
putpixel((getmaxx()/2)+xc+y, (getmaxy()/2)+35+yc+x, 1);
putpixel((getmaxx()/2)+xc-y, (getmaxy()/2)+35+yc+x, 1);
putpixel((getmaxx()/2)+xc+y, (getmaxy()/2)+35+yc-x, 1);
putpixel((getmaxx()/2)+xc-y, (getmaxy()/2)+35+yc-x, 1);
}
}
}
No comments:
Post a Comment