Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!jarthur!nntp-server.caltech.edu!josephc
From: josephc@nntp-server.caltech.edu (Joseph I. Chiu)
Newsgroups: comp.sys.ibm.pc.misc
Subject: Fast circle drawing.
Summary: Fast way to draw a circle.
Message-ID: <1991Jan25.055135.4172@nntp-server.caltech.edu>
Date: 25 Jan 91 05:51:35 GMT
Organization: California Institute of Technology, Pasadena
Lines: 60

The discussion of ellipse drawing prompted me to write the article because
I had a hard time coming up with a fast circle-drawing routine when I needed
it for a programming class last year.  I hope someone can use this...


Okay, here it goes (I'm going to go through the process from the start
 because I need to jog my memory...)

The traditional 'easy' way of drawing a circle is done by multiplying the
'radius' of the circle with the sines and cosines of the loop (i.e., from
zero to 360 degrees), and connecting the points.

But, computing the sines and cosines of each point take a ridiculous part
of our drawing routine if we use the sine/cosine math library functions... 
So we use a little bit of math...    

We know, from our high-school math that:

   sin (a+b)  =  sin (a) cos (b) + sin (b) cos (a)
   cos (a+b)  =  cos (a) cos (b) - sin (a) sin (b)

So, let's say we start our circle at theta = 0; Well, the sin/cos values
for angle 0 is simply:

   sin (0) = 0    cos (0) = 1

Now, to find the sin/cos values of the next point of interest, say at angle
theta(2), where theta(2) = theta + delta.  By using the identities above,

   sin (theta(2)) = sin (theta)*cos (delta) + sin(delta)*cos(theta)
   cos (theta(2)) = cos (theta)*cos (delta) - sin(theta)*sin(delta)

By using the method again, we can find the values for sin/cos for the angle
theta(3) where theta(3) = theta + 2*delta = theta(2) + delta by:

   sin (theta(3)) = sin (theta(2))*cos (delta) + sin (delta)*cos (theta(2))
   cos (theta(3)) = cos (theta(2))*cos (delta) - sin (theta(2))*sin (delta)

And we can repeat the process for successive angles by repeating the process.
Note that in all cases, cos(delta) and sin(delta) are constant.


Thus, to express the idea in C code:

sine = 0; cosine = 1;    /* Starting sine/cosine values at theta = 0 */
sine_delta = sin(delta_angle); cosine_delta = cos(delta_angle);

for (i = 0; i < N; i++) {
   new_sine = sine * cosine_delta + sine_delta * cosine;
   new_cosine = cosine * cosine_delta - sine * sine_delta;
   /* line drawing goes here */
   sine = new_sine;  cosine = new_cosine;
   }

Hope this helps...    

-- Joseph
-- 
--
josephc@coil.caltech.edu               ...Just another lost soul in the universe