View Question
 Question
 Subject: Circular Arcs approximating an Ellipse Category: Science > Math Asked by: dacat-ga List Price: \$50.00 Posted: 13 Mar 2006 12:19 PST Expires: 12 Apr 2006 13:19 PDT Question ID: 706840
 ```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.```