From: bkph@wheat-chex.ai.mit.edu (Berthold K.P. Horn)
Newsgroups: comp.sys.next.programmer,comp.lang.postscript
Subject: Re: Arcs and circles from curveto
Date: 13 Jan 93 02:25:19 GMT
Organization: MIT Artificial Intelligence Lab
NNTP-Posting-Host: wheat-chex.ai.mit.edu
In-reply-to: henry@trilithon.mpk.ca.us's message of 12 Jan 93 17:51:32 GMT


In article <1993Jan12.175132.27149@trilithon.mpk.ca.us> henry@trilithon.mpk.ca.us (Henry McGilton) writes:

   In article <1993Jan11.014246.4735@drefla.mese.com> matt@drefla.mese.com (Matt  
   Brandt) writes:
       *  I've been able to come up with a pretty good approximation
       *  of a circle using curveto . . .
   <<<<<   stuff deteleted  >>>>>>
       *  of course, you can repeat for the bottom of the circle.
       *  Like I said though, this is only an approximation. Does
       *  anybody out there have a better approximation of circle
       *  drawing using curveto? I need to do it this way for bizarre
       *  reasons and I would like to improve the accuracy a little bit.

   You can't get an accurate enough circle with only two curves.  You
   need one curve per quadrant, and you draw four of them.  The ``magic
   number'' for the circle is  0.555.  Here's an example which you
   can hack to your needs.

	       %!PS
	       /R 288 def
	       /M R 0.555 mul def
	       306 396 translate
	       R 0 moveto
	       R M dup R dup 0 exch curveto
	       M neg R dup neg M R neg 0 curveto
	       R neg M neg dup R neg dup 0 exch curveto
	       M R neg R M neg R 0 curveto
	       closepath
	       stroke

   I cross posted this to comp.lang.postscript, because, as Eric Scott
   pointed out, this topic is pure PostScript and only tangentially
   NeXT related.


	   ........  Henry

Addendum: Approximating circular arcs with Bezier curves:

The smaller the angle of the circular arc the better an
approximation you can get out of a Bezier curve, obviously.
For a unit radius circle, a good approximation
of an arc turning through angle theta uses

	eta = (4/3) (1 - cos(theta/2)) / sin(theta/2)

where eta is the distance of the control points from the knots,
measured along a line tangent at the knots (sorry you'll
have to draw the figure yourself, my ASCII curve drawing skills
are unequal to the task).

For  theta=pi/2  you get  eta = (4/3)(sqrt(2) - 1) = .55228...
which yields a very good approximation to a quadrant of a circle

For  theta=pi  you get  eta = (4/3) = 1.33333....
which is a not so good approximation of a semicircle.

In the limit as theta tends to zero, by the way, the control
points end up 2/3 of the way from the knots to the
intersection of the tangents.  This is a quick and dirty way 
to generate a good approximation, if breaking up an arc into 
many pieces is not a concern.

By the way, the above approximations all have the Bezier curve
departing from the true arc in one direction (error always has 
the same sign).  One can do twice as well by balancing the
positive and the negative errors, but then no closed form 
solution to the problem appears to be at hand.  
For  theta=pi/2  the optimum is 

	eta = .5541...

The same technique can obviously be used for ellipses, since
ellipses are circles on an anisotropically scaled coordinate system.
Super-ellipses can also be very well aproximated by Bezier curves
(super-ellipses have equations of the form (x/a)^beta + (y/b)^beta = 1).

Cubic `splines' are quite `flexible' since they have 8 parameters (2 knots
and 2 control points).  On average, it takes twice as many quadratic splines
to describe a shape adequately as it does cubic splines.

Exercise for the reader:

Suppose you draw a pen-stroke with a pen that has a circular nib, where the
center of stroke follows a given Bezier curve.  Can the `outer' and `inner'
edges of the resulting shape be described exactly using a Bexier curve?
If not, how do you compute an adequate approximation - one that does not
require splicing together too many separate cubic splines?

Berthold K.P. Horn
Cambridge, Massachusetts, USA
Newsgroups: comp.sys.next.programmer