# Deriving the equation of points for exact fitting and shape analysis

2 replies to this topic

### #1giusy.venezia

New Member

• Members
• 1 posts

Posted 29 November 2012 - 12:58 PM

Hello,

I would like to ask you some questions.

1) I've a closed curve (for example an ellipse, which may represent the contour of an object) represented by the set of its (known) points. I need to find the equation of that curve to pass through all and every point (exact fit). I think that to do this I need a polynomial whose grade is equal to the number of points less 1.

Something like this:

a0+a1 x1+a2 x1^2+ ...+ an x1^n = y1
a0+a2 x2+a2 x2^2+ ...+ an x2^n = y2
...
a0+a2 xn+a2 xn^2+ ...+ an xn^n = yn

This argument is right? Do you have suggestions (or anything else relevant) for me in this regard for which is the best way to solve my problem? This equation can be made in parametric form?

2) After I got the exact equation of this curve. Suppose we have a set of curves very similar to each other (represented by their equation), I would like to find the equation that represents the shape which best approaches to all previous curves, a sort of average curve created from those previously acquired.
Do you know if this thing can be done and how? What is the best way (most efficient and / or mathematically more correct) to do this?

Best Regards,

Giusy

### #2Stainless

Member

• Members
• 582 posts
• LocationSouthampton

Posted 29 November 2012 - 04:21 PM

http://en.wikipedia....uardt_algorithm

I think that's the academic solution.

I haven't done any work in this area for a hell of a long time, but I seem to remember there are some cheats you can use.

Finite differences can tell you the degree of the equation, you calculate finite difference by calculating the difference between two successive points, then the differences between successive differences until you reach a difference of 0.

so take y=x*x;

X Y Diff
1 1 .
2 4 (1-4) = -3
3 9 (4-9) = -5 -3-(-5) = 2
4 16 (9-16) = -7 -5-(-7) = 2 2-2=0;
5 25 (16-25)=-9 -7-(-9) = 2 2-2=0;

Third diff so order is 2

### #3Reedbeta

DevMaster Staff

• 5310 posts
• LocationSanta Clara, CA

Posted 29 November 2012 - 05:41 PM

giusy.venezia, on 29 November 2012 - 12:58 PM, said:

I need to find the equation of that curve to pass through all and every point (exact fit). I think that to do this I need a polynomial whose grade is equal to the number of points less 1.

Yes, to get a polynomial to pass through 3 points exactly you'll need a quadratic, 4 points you'll need a cubic, etc. You need one variable for each constraint (point to pass through), then it's just a linear system you can solve. However this will of course give you only polynomial curves. If your curve is an ellipse as you said, no polynomial will match it, and if you try this procedure you'll probably get something weird. High-degree polynomials aren't very good approximators, either - see Runge's phenomenon.

If your ultimate goal is to produce an "average" approximating curve, it may well be best to forego the exact-fit polynomials altogether and jump directly to least-squares optimization via Levenberg-Marquardt or similar. This requires you to choose the degree of curve to fit, though (or choose the functional form of the curve more generally). IIRC, polynomial fitting can be done directly by linear least squares, with no need for L-M or more complicated stuff, at least as long as the number of points is not too big. But L-M will work for other kinds of curves too, or for larger numbers of points.
reedbeta.com - developer blog, OpenGL demos, and other projects

#### 1 user(s) are reading this topic

0 members, 1 guests, 0 anonymous users