Interview Questions And Answers 
-
Write a routine to draw a circle given a center coordiante (x,y) and a radius (r) without making use of any floating point computations.
4,606 Views |
(11 votes, avg: 3.64)
Loading ...
Answers »
Our Sponsors
Our Sponsors
void circle(int x,int y, int rad)
{
//check boundary first
for (int xi = x-rad, int yi = y-rad;
xi<=x+rad,yi<y+rad; xi++,yi++)
if((xi-x)*(xi-x)+(yi-y)*(yi-y) = rad *rad + Error)
set_point;
}
In order circle using only integers this might be the solution.
{(x,y) represent center and k the radius.}
loop thru till u complete drawing the circles
x = x + y/k;
y = y + x/k
end loop.
– Nitin Motgi (nmotgi@cs.ucf.edu)
In order to avoid floating point calculations, we can do two things:
1) instead of fixing one co-ordinate and looking for anothe via the equation, search the whole co-ordinate space from x +- r and y +- r. Plot the point that is close.
But this is a costly N*N algo.
2) To go for an efficient workhorse, go for Bresenham’s circle drawing algo, found in any of the good graphics textbooks.
Lets forget about the circle’s center point (Xc,Yc) for a minute. To minimize calculations you should consider the next notes:
1) It is enough to calculate all the points just in one quarter of a circle. For each calculated point you can build three additional points by a simple sign manipulation (and than shifting according given Xc and Yc)
2) Now we need to calculate all (X,Y) points which belong to the circle’s quarter sector. There are [Rad+1] of such points. X[0]=0, X[1]=1 … X[Rad] = Rad. And here is the most important optimization: Y(X[n]) INF, that is a pretty optimal O(N) algorithm
vladmir, u can optimise ur soln even more by considering symmetry about x and y axes. so effectively, u can calculate points in one half of a quadrant and use that to compute 7 more points and then shifting the points according to the center of the circle
listen
you better go byconversion in radians i.e angle
rcos@,rsin@ now vary @0 to 360
Leave an Answer/Comment