Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!caen!Firewall!uunet!mcsun!ukc!ox-prg!msc3.comlab!imc
From: imc@prg.ox.ac.uk (Ian Collier)
Newsgroups: comp.lang.c
Subject: Re: Help w/Plotting a circle...
Message-ID: <899.imc@uk.ac.ox.prg>
Date: 14 Jun 91 15:09:26 GMT
References: <1991Jun11.154335.130@sugaree.uu.net>
Sender: news@prg.ox.ac.uk
Reply-To: imc@prg.ox.ac.uk (Ian Collier)
Organization: Oxford University Computing Laboratory, UK
Lines: 46

In article <1991Jun11.154335.130@sugaree.uu.net>, bill@sugaree.uu.net (William Bishop) wrote:

>Does anyone out there have an algorithim for plotting the points
>of a circle.

I tried to reply by email, but it bounced, so I'm posting. Sorry for
wasting bandwidth for those not interested.

This solution refutes two points made in a previous posting, namely
that you need a quarter of the circle (in fact you need an eighth, as
previously suggested), and that it is a trig problem.
[Aside: trig is usually slower, and can not be guaranteed to generate
 every point precisely once. However there is a good algorithm using
 trig which approximates a circle by a polygon].

To plot a circle of radius r and centre cx,cy do something like this
(assuming that each distinct pair of coordinates is a distinct point):

for each y=0,1,... int[r/sqr2], do this:
   x=sqr(r*r-y*y)
   plot cx+x,cy+y
   plot cx+y,cy+x
   plot cx-x,cy+y
   plot cx+y,cy-x
   plot cx-x,cy-y
   plot cx-y,cy-x
   plot cx+x,cy-y
   plot cx-y,cy+x

where sqr2=1.4142135... (equals approximately 181/256 or 46341/65536)
and for integer x, sqr(x) is the integer square root of x.
I think the cicle is prettier if it is the nearest integer to the square
root of x, rather than the integer part of that.

If plotting points twice produces undesirable results, then you will need
to check x!=y before plotting any of the above coordinates which has a y
in the first expression, and y!=0 before plotting any expression containing
-y. Otherwise I don't think there are any problems with this algorithm.

The algorithm is easily extensible to produce a filled circle made up of
horizontal (or vertical) lines.

[I can supply a fast integer-square-root algorithm if you need one].

Ian Collier
Ian.Collier@prg.ox.ac.uk | imc@ecs.ox.ac.uk