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:
and here discussion of efficiency
Here is a technical paper with references (which may require subscription)
These two papers deal specificaly with aproximating ellipses
Approximating an Ellipse by Circular Arcs
"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)
and here is that same issue elaborated in 10 pages
Request for Answer Clarification by
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
Clarification of Answer by
14 Mar 2006 05:40 PST
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
precision and are 'smooth', if so specified, have even n smooth derivatives.
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.
Request for Answer Clarification by
14 Mar 2006 16:57 PST
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
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
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
Clarification of Answer by
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
2) More general definition from MathWorld:
In practice, the vertical offsets from a line (polynomial, surface,
are almost always minimized instead of the perpendicular offsets
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)
And here is tutorial (simplified) description of that method:
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
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 ...
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.
There is lot of the more or less free software which do this
An Interactive Introduction to Splines
All sources are free. The whole Splines.zip (215kb, 5 Dec 2003)
But frankly and justbetween us: I bet may hat that a standard
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
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.