Xref: utzoo comp.graphics:4470 sci.math:5685 comp.sources.wanted:6357
Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!ndcheg!ndmath!krueger
From: krueger@ndmath.UUCP (Andreas Krueger)
Newsgroups: comp.graphics,sci.math,comp.sources.wanted
Subject: Re: looking for a fast ellipse algorithm
Keywords: ellipse, graphics, circle
Message-ID: <1311@ndmath.UUCP>
Date: 14 Feb 89 23:58:19 GMT
References: <399@peritek.UUCP>
Organization: Math. Dept., Univ. of Notre Dame
Lines: 63

In article <399@peritek.UUCP>, dig@peritek.UUCP (David Gotwisner) writes:
> 
> 	I am looking for an algorithm (or code) which will allow circle
> generation onto a graphics device which drives a monitor with non-square
> pixels.

Drawing a circle on a device with non-square pixels is
equivalent to drawing an ellipse on a monitor with square pixels.

From any third-semester calculus book ("calculus with analytic
geometry") you can find the formula of an ellipse:

                    x^2   y^2
                    --- + --- = 1
                    a^2   b^2

This is the formula of an ellipse with center (0,0), the "diameter" in
direction of the x-axis is 2a, the "diameter" in direction of the y axis
is 2b. The points (a,0), (-a,0), (0,b), (0,-b) are the four
vertices of the ellipse (i.e., the points where the two symmetry
axes hit through the ellipse).

I've just been teaching this stuff in a third semester calculus
course (off semester), so this is actually a nice homework
exercise for me. Here is how I would go about implementing this:

If you want to draw a circle, proceed as follows: You'll have a
radius "r". Let "a" denote the number of pixels on a horizontal
line of length "r", and "b" denote the number of pixels on a
vertical line length "r".

Now let x run from 0 to a^2/sqrt(a^2+b^2) in steps of 1 (pixel).
For each such x, compute y by the above formula, which
when solved for y yields y = (b/a)*sqrt(a^2 - x^2). (You'll want
to put those numbers b/a and a^2 into temporary variables so the
computer doesn't compute them anew each time.) Round y to the
nearest integer.

If (x0,y0) are the pixel coordinates of the intended center of
your circle, set the four pixels (x+x0,y+y0), (-x+x0,y+y0), 
(x+x0,-y+y0), (-x+x0,-y+y0). (For efficiency, see to it that the
program computes x+x0, -x+x0, y+y0, -y+y0 only once each, rather
than twice. Just use some more temporary variables.)

Now you let y run from 0 to b^2/sqrt(a^2+b^2) in steps of 1 (pixel).
For each such y, compute x by the above formula, which when
solved for x yields x = (a/b)*sqrt(b^2 - y^2). Set the four
pixels (same as above).

From this, you can write the code yourself, I'd say. 

I don't know for what kind of computer you'll need this. If it
turns out that the arthmetic is too slow, you'll have to increase
your steps from 1 to some larger number and draw connecting lines
rather than just blacking individual pixels. The coding would become
slightly more messy, for you'll need to keep track of four unfinished
lines at one time.

Hope that's what you needed!

krueger@ndmath.math.nd.edu
gl5r7n@irishmvs.cc.nd.edu
gl5r7n@irishmvs.bitnet