[comp.lang.c] Help w/Plotting a circle...

bill@sugaree.uu.net (William Bishop) (06/12/91)

Hi,

Does anyone out there have an algorithim for plotting the points
of a circle.   Any all all help is appreciated.  Thanks!

...Bill

-- 
          **** All opinions stated above are my own!! ****
--------------------------------------------------------------------
William Bishop                 |  "Its a big country...
IKEA U.S. Services, Inc.       |      Someone's got to furnish it!"
Plymouth Commons               |                - IKEA 
Plymouth Meeting, PA 19462     |                
Tel:  (215) 834-0180           |  This space intentionally filled!!
Fax:  (215) 834-0872           |
Telex: 846223                  |  

sjb@piobe.austin.ibm.com (Scott J Brickner) (06/13/91)

I seem to remember a really neat article in Dr Dobbs Journal (the
magazine) about two or three years ago...  it had about six different
circle and line drawing algorithms of varying complexity... does anyone
else remember this and know which issue it was in?

In general, though, a quick optimization for any of the circle drawing
algorithms is to only COMPUTE 1/8th of the points, and use reflection
about the various axes x=0, y=0, y=x, and y= -x for the remainder.

Good luck...
Scott

session@seq.uncwil.edu (Zack C. Sessions) (06/13/91)

sjb@piobe.austin.ibm.com (Scott J Brickner) writes:

>In general, though, a quick optimization for any of the circle drawing
>algorithms is to only COMPUTE 1/8th of the points, and use reflection
>about the various axes x=0, y=0, y=x, and y= -x for the remainder.

Umm, wouldn't that be compute 1/4 of the points and then use the
reflection method to get the other points? Also, when using the
reflection method to obtain the remaining points, you need to consider
the coordinates of the center of the circle, if it isn't (0,0).
The computation is also elementary trigonometry which I won't go
into since any elememtary book on trig in your library should
be all you need.


Zack C. Sessions
session@seq.uncwil.edu
	  ^^^
	   |
	   +--->  Note! Username is session, NOT sessions. Not my fault!
					Ask my SysAdmin why!!

dave@tygra.Michigan.COM (David Conrad) (06/14/91)

In article <1991Jun11.154335.130@sugaree.uu.net> bill@sugaree.uu.net (William Bishop) writes:
>Hi,
>
>Does anyone out there have an algorithim for plotting the points
>of a circle.   Any all all help is appreciated.  Thanks!
>

I hear some guy named Bresenham has a pretty good one....
Seriously, look up the Bresenham Circle Drawing Algorithm, probably in
Knuth (God knows everything else is), as well as many other places.
I believe that Michael Abrash worked up an implementation in his
On Graphics column in Programmer's Journal a while back (sorry I can't
give a full citation), and Abrash also has a book out called Power
Graphics Programming, but it is completely IBM-PC EGA/VGA oriented.
Just don't use trig.  :-)
--
David R. Conrad
dave@michigan.com
-- 
=  CAT-TALK Conferencing Network, Computer Conferencing and File Archive  =
-  1-313-343-0800, 300/1200/2400/9600 baud, 8/N/1. New users use 'new'    - 
=  as a login id.  AVAILABLE VIA PC-PURSUIT!!! (City code "MIDET")        =
   E-MAIL Address: dave@Michigan.COM

olm@informatik.uni-kiel.dbp.de (Olaf Mehlberg) (06/14/91)

In <1667@seq.uncwil.edu> session@seq.uncwil.edu (Zack C. Sessions) writes:

>sjb@piobe.austin.ibm.com (Scott J Brickner) writes:

>>In general, though, a quick optimization for any of the circle drawing
>>algorithms is to only COMPUTE 1/8th of the points, and use reflection
>>about the various axes x=0, y=0, y=x, and y= -x for the remainder.

>Umm, wouldn't that be compute 1/4 of the points and then use the
>reflection method to get the other points? Also, when using the
>reflection method to obtain the remaining points, you need to consider
>the coordinates of the center of the circle, if it isn't (0,0).
>The computation is also elementary trigonometry which I won't go
>into since any elememtary book on trig in your library should
>be all you need.

I agree, you have to look for the coordinates of the center, but
1/8th of the points is enough. 
How to do assuming (0/0) as center: (* is the center c is a
computed point r a reflected point)
			         !     c 
                                 !      c 
                                 *-------c
                                 !      r
				 !     r
compute the 1/8 c, reflect them at the --- line and you have 1/4
of the circle. reflect this at the ! line and you have 1/2 of the
circle. flip x/y coordinates and you get the missing 1/2 of the
circle. Then move all coordinates into the right center.

I hope this is correct, sounds bit too simple ;-0

Olaf Mehlberg
--------------------------------------------------------------------
Errare humanum est
--------------------------------------------------------------------
Christian-Albrechts-Universitaet Kiel, Institut fuer Informatik
Preusserstr. 1 - 9                   , D - 2300 Kiel 1
Phone: ++49-431-5604-42              , Fax: ++49-431-566143
EMail: olm@informatik.uni-kiel.dbp.de
--------------------------------------------------------------------

imc@prg.ox.ac.uk (Ian Collier) (06/14/91)

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

paul@hal.com (Paul Sander) (06/15/91)

I hate to spoil the party, but I believe the definitive answer for drawing
ellipses using only integer adds and shifts is in the FAQ list in
comp.graphics.  You might take a look there.

Paul Sander
paul@hal.com

Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) (06/16/91)

In a message of <Jun 14 17:52>, William Bishop (1:114/15) writes: 
 >Hi,

 >Does anyone out there have an algorithim for plotting the points
 >of a circle.   Any all all help is appreciated.  Thanks!

You only need to plot 1/8th of the circle then relect it about y=x, then x=0, 
then y=0.  The obvious solution is to use x^2 + y^2 = r^2 then set y= 
sqrt(r^2-x^2) then plot the x and y until x is less than y.  On each of these 
points plot (x,y), (y,x), (-x,y), (x, -y), (-x, -y), (-y, x), (y, -x), and 
(-y, -x).  Add your center point to each of these coordinates before plotting. 
 

Now if you need some real speed, use the Brezenheim circle alogithm.  It 
reduces the problem such that you do not need to call the sqrt() function.

circle(int radius, int xcenter, int ycenter)
{
   int x,y,s;

   x = 0;
   y = radius;
   s = 3-2*radius;

   while (x<=y)
   {
      plot_eight(x,y,xcenter,ycenter);
      if (s <= 0)
         s+= 4*x+6;
      else
      {
         s+= 4*(x-y)+10;
         y--;
      }
      x++;
   }
}

#define plot_eight(int x, int y, int xcenter, int ycenter)  \
{                                                           \
   register int t1,t2,t3,t4;                                \
                                                            \
   t1 = x+xcenter;                                          \
   t2 = -x+xcenter;                                         \
   t3 = y+ycenter;                                          \
   t4 = -y+ycenter;                                         \

   plot(t1, t3);    /* actual pixel plot function */        \
   plot(t2, t3);                                            \
   plot(t1, t4);                                            \
   plot(t2, t4);                                            \

   plot(t3, t1);                                            \
   plot(t3, t2);                                            \
   plot(t4, t1);                                            \
   plot(t4, t2);                                            \
}

That should be real close to what you want anyway.  plot() probably takes a 
color as well but you get the idea.  I made plot_eight a macro for additional 
speed.  This should be within about 10% of the maximum speed possible for a 
circle algorithm.  Notice that there are no floating points or power functions 
needed.  That makes this function very fast.

Dave Harris.
 


 

--  
Uucp: ...{gatech,ames,rutgers}!ncar!asuvax!stjhmc!15!14!Dave.Harris
Internet: Dave.Harris@f14.n15.z1.fidonet.org

joe@proto.com (Joe Huffman) (06/18/91)

Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) writes:

>Now if you need some real speed, use the Brezenheim circle alogithm.  It 
>reduces the problem such that you do not need to call the sqrt() function.

The real problem with everything I have seen so far is plotting just an arc.
Like from 10 degrees to 25 degrees.  The start and end points are a pain 
without trig functions (which are slow).

-- 
uunet!proto!joe
joe@proto.com

Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) (06/20/91)

 >From: joe@proto.com (Joe Huffman)

 >Dave.Harris@f14.n15.z1.fidonet.org (Dave Harris) writes:

>Now if you need some real speed, use the Brezenheim circle alogithm.  It 
>reduces the problem such that you do not need to call the sqrt() function.

 >The real problem with everything I have seen so far is plotting just an 
 >arc.
 >Like from 10 degrees to 25 degrees.  The start and end points are a pain 
 >without trig functions (which are slow).

Nothing good comes to mind immediately.  It does look like you at least need 
to calculate the end points, then you should be able to use the standard 
circle function covered with condition statements.  If you need to plot many 
arcs then you can store the trig values in tables.   The tables can get big 
though if you a granularity of .01 or more.

 


 

--  
Uucp: ...{gatech,ames,rutgers}!ncar!asuvax!stjhmc!15!14!Dave.Harris
Internet: Dave.Harris@f14.n15.z1.fidonet.org