I am looking for a solution to approximating ellipses with circular
arcs. Currently i have solutions for 2 radius and 3 radius 90 deg
ellipses giving the least error from a true ellipse. However if this
error is too great it is difficult for me to solve the problem with
more radii. The constraints are that the radii must be tagential to
each other and the the apexes must pertfectly horizontal and vertical.
The solution must include formula and if possible code for solving the
problem.

If a wider solution can be found for fitting the circular arcs to any
curve/points this would be even better.

Fitting an arc to set of points can be solved with Least Square method.
Some manipulation is required, to make the regression linear.
Considerable attention was paid to efficiency, since such methods are
used in computer graphics.

Here is a paper with over-all decription of the problem and solution:
www2.parc.com/istl/groups/ pda/papers/salient-arcs-spl-93-017.pdf

and here discussion of efficiency
http://www.math.uab.edu/cl/cl2/cl2/node4.html


Here is a technical paper with references (which may require subscription)

http://www.citebase.org/cgi-bin/citations?id=oai:arXiv.org:cs/0301001




These two papers deal specificaly with aproximating ellipses 


 Approximating an Ellipse by Circular Arcs

http://www.geometrictools.com/ Documentation/ApproximateEllipse.pdf


"This describes two intiutive ways how to draw wllipses using compas:
The above methods all make accurate ellipses. It is much more
convenient to represent an ellipse by circular arcs that can be drawn
with a compass than to connect points laboriously determined. The
simplest case is shown in the figure at the left, called a
three-center arch. To a draftsman, it is a "four-center ellipse"
  It is a long article. Yhe text on circles is in the milddle (use Find if
 you do not have patience to read it all)

http://www.du.edu/~jcalvert/math/ellipse.htm

and here is that same issue elaborated in 10 pages
http://users.cs.cf.ac.uk/Paul.Rosin/resources/papers/oval8.pdf

---

Request for Answer Clarification by dacat-ga on 14 Mar 2006 02:36 PST

Thank you for your attention to my question. The question may not have
been as clear as i thought and so i will try to clarify it for you.

I believe the shape i am looking for is called a Biarc, a number of
circular arcs tangetial to each other. The biarc needs to approximate
the ellipse within a specified tolerance. I have found the articles
you found and while the are on a similar subject they do not give me a
solution for an approximation to an ellipse with more than 3 radii per
90°. The solution found from Paul Rosin at cardiff university solves
for 3 radii but does not give the best fit and does not solve using
more radii.

---

Clarification of Answer by hedgie-ga on 14 Mar 2006 05:40 PST

dacat-ga

 We do make special allowances for new customers, and so please take this 
 as a polite request, not as a criticism.

 If you are looking specifically for 'something like Biarc algorithm', perhaps
 a program, perhaps theory, you have to say that. Literature on
'fitting circles' is enormous, and chances that we find a fit [ :-) ]
by shooting at random are slim. Also, I wonder if you looked at all
the references I gave you.

Two aproximate by three arcs, some by five, and some discuss 'circular
arc splines' - which is what (it now looks like) you want.

The paper from PARC in paticular (if I recall correctly) was developed
to aproximate shape of fonts. Splines (per defintion) can be refined
to arbitrary
precision and are 'smooth', if so specified, have even n smooth derivatives.
http://www2.parc.com/istl/groups/ pda/papers/salient-arcs-spl-93-017.pdf

So, please, look at it again, and clarify what you need and I will
give it another shot. It always help if you explain what you are
trying to do with it,
and it is always necessary to say what you already know.

Hedgie

---

Request for Answer Clarification by dacat-ga on 14 Mar 2006 16:57 PST

My apologies,

I will try to give you some background to the problem!

I work for a company that curves steel sections, mainly into circles.
Quite often we need to bend sections to ellipses sometimes for
aesthetic reasons sometimes for fitting true ellipses closely.

The machinery works best if the ellipse is split into tangential
circular arcs, this aids repeatability and production speed. I have
written programs for optimising the best fit 3 and 5 centered
approximations which work well. However when the ellipse becomes large
these approximations are not accurate enough to use and another manual
method is used to optimise the radii which takes some time.

The solutions I have found ar based upon finding the smallest maximum
deviation from the true curve and not the "Least Square Method" as
this generally the most important criteria. I have found the best fit
solution does not have the radius change points exactly on the
ellipse.

Hopefully this gives you more of an insite into the problem, again i
apologise for the original question as i can appreciate you need all
the information to solve the problem.(It is the first time I have ever
done this!)

Although it is not part of the question related problems to this
include following other shapes including partial elliptical arcs,
parabolic curves and cycloids and unspecified co-ordinate geometry.

And if you are feeling very helpfull we often get work for
rollercoasters. We are supplied with x,y,z co-ordinates for the spine
tube and have to convert these into tangential(near) arcs. Each
succesive arc will have a rotation between them thus producing the
required 3 dimentional shape within a tolerance. This can take 2/3
days using the near manual method i use. (Perhaps this is worth more
than £50)

---

Clarification of Answer by hedgie-ga on 15 Mar 2006 04:52 PST

Thank you for your clarification. 
I do believe that with this extra info I can answer your question:

Let's get out terminology straight:

The Method of Least Squares	LSQ methods
	
1) Usual definition:
The method of least squares assumes that the best-fit curve of a given
type is the curve that has the minimal sum of the deviations squared
(least square error) from a given set of data.

Suppose that the data points are , , ...,  where  is the independent
variable and  is the dependent variable

minimise  sum of (y,i - f(x.i) ^2      as described here

http://www.efunda.com/math/leastsqua

2) More general definition from MathWorld:

In practice, the vertical offsets from a line (polynomial, surface,
hyperplane, etc.)
 are almost always minimized instead of the perpendicular offsets
http://mathworld.wolfram.com/LeastSquaresFitting.html

Usual meaning is LSQ with vertical offsets LSQ-VO
the other method LSQ  with perpendicular offsets - LSQ-PO 
is also Least Squares. Just the sides of the squares are different.

3) Even more general mthod, which is 'minimising energy' . Energy 
is 'elastic energy' of bending a steel spline + energy of the rubberbands
which tie the spline to the control points. etc etc 


How to turn 'non-linear regression' into a linear LSQ problem:
--------------------------------------------------------------

Here is a very clever article,13 pages, which describes how to fit
conics (circles, ellipses ,.. )
to scatteres data points. (These of course could be the control points)

http://citeseer.ist.psu.edu/646747.html

And here is tutorial (simplified) description of that method:
http://answers.google.com/answers/threadview?id=449830


With that, you should have all the tool to automatise your arc-fitting


But wait - there is more :

Here is description of your Bi-Arc algorithm

Biarc

A Recursive Subdivision Algorithm for Piecewise Circular Spline	
Ahmad H. Nasri, C. W. A. M. van Overveld & Brian Wyvill	

We present an algorithm for generating a piecewise G1 circular spline
curve from an arbitrary given control polygon. For every corner, a
circular biarc is generated with each piece being parameterized by its
arc length. This is the first subdivision scheme that produces a
piecewise biarc curve that can interpolate an arbitrary set of points.

A piecewise circular spline, the application of the algorithm 
 which can be used to generate piecewise circular spline ...
www.blackwell-synergy.com/ doi/abs/10.1111/1467-8659.00473


And here is a piece of theory on pieca-wise cricular splines

Circular Bernstein-Bezier Polynomials 
dvi file or postscript file . With Marian Neamtu and Larry Schumaker,
to appear, in Mathematical Methods for Curves and Surfaces, M.
Daehlen, T. Lyche, and L. Schumaker (eds.) Vanderbilt University
Press, Nashville, 1995. We discuss a natural way to define barycentric
coordinates associated with circular arcs. This leads to a theory of
Bernstein-Bezier polynomials which parallels the familiar interval
case, and which has close connections to trigonometric polynomials.

http://www.math.utah.edu/~pa/papers.html


There is lot of the more or less free software which do this

http://www.nea.fr/abs/html/nesc9602.html


An Interactive Introduction to Splines
Circular arcs.
All sources are free. The whole Splines.zip (215kb, 5 Dec 2003)
http://www.ibiblio.org/e-notes/Splines/Intro.htm

But frankly and justbetween us: I bet may hat that a standard
minimalisation routine
will refine a reasonable 'initial guess' quickly and adequatly for all
practical purposes of the type your mention. People are developing these clever
algorithms because they need to be efficient: They have millions of data points
(rendering complex things - like human face) and theu want to render
(graphically) using
some cheap mcroprocessor. In your case, with few tens of points and a
real PC, and not very
tricky shapes, you probably do not need complicate your life with that.

 Let's close this question/answer for now.  After you have time to digest all
 this info, if you feel you need your asistance, you can always come back with
another question.  It is even possible to put into the tirle of the question
"for whoever-ga" : circular splines  (or whatever) of you want a paerticular
 whoever-ga to research your problem.

Rating appreciated.

Hedgie-ga

Did you know that it is easy to draw ellipses?
Two pins in your drawing board, a piece of string tied in a loop that
is large enough to surround them, and then tighten the string with a
pencil and trace its path around the pins, keeping the string taut.
The closer the pins are, the more the ellipse will approach a circle;
the further apart they are, the narrower the ellipsie will be.

No doubt, there is a formula for the length of the loop and distance
between the pins that can be solved to give an ellipse of given width
and length.

CHeck out this site:
http://mathforum.org/library/drmath/sets/select/dm_ellipse.html

Here is another method:
http://carverscompanion.com/Ezine/Vol2Issue4/Judt/Ellipses.html

There are several fairly easy ways to draw an ellipse including the
one myoarin alluded to.  Am I right to assume you already know about
these?  If not, let me know and I'll summarize a few.  If you are only
interested in the method you are describing, please clarify the
approach.  I'm not sure I understand the rules of construction you are
referring to.

Perhaps you had this in mind.  An ellipse can be constructed given a
circle with its center point O, an arbitrary point in the interior F
of the circle, and an arbitrary point on the circle P.  Points O and F
are the two foci of the ellipse.  Construct line segments OP and FP. 
Label the midpoint of FP as point M.  Construct the perpendicular
bisector of FP thru point M.  The perpendicular bisector of FP will
intersect OP.  Label the point of intersection point T.  Now as you
drag point P around the circle, the line defined by the points M and T
will create a series of tangent lines to the ellipse with foci O and
F.

If you have access to Geometer's Sketchpad you can view this
dynamically as you drag point P around the circle.

Let me know if this helps.