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

1) You are on the right track, except that if you have 'n' points the number of unknowns (the a's) is also n, and the equation is a polynomial of order n-1, so the matrix of equation is:



This will give a polynomial solution for a function that passes through all n points. You mentioned an ellipse, but the equation for an ellipse is nt of this form, so the solution using this technique will never result in an ellipse. Which goes to show that there are multiple equations that can be solutions to passing through the n points. And this technique simply finds the polynomial version.

2) When you ask about "similar" curves I assume you mean that they are all of the same degree (i.e, all of order n-1). One approach would be to simply find the mean of the set of coefficients associated with each power of x. For example suppose you have three equations of the form y=a_0+a_1x+a_2x^2, like this:

y = 2 + 3x + 3x^2
y = 1 + 4x + 3x^2
y = 2 + 5x + 1 x^2

The mean value of a_0 is 5/3, the mean value for a)1 is 4, and the mean value of a_2 is 7/3. So the resulting "average" equation is 5/3 + 4x + 7/3x^2.

Thank you very much for the precious information.

Do you think that the "Lagrangian Interpolation" is more suitable for my purpose?

Informally, I need to get the equation (possibly as general as possible and parametric), or any other mathematical stuff, that uniquely (unambiguously) represents a given shape (denoted by its points).

The function that I need must take into account only (and exactly) the points that belong to my shape and no other. So I cannot use "best fit techniques" like "minimize euclidean distance" of "direct least squares", etc.

For "similar curves" I wanted to mean, "similar shape". Consider for example, the point's contour of a rugby ball (obtained for example via edge fitting technique, but no matter how). Suppose that I've two (of more) rugby balls (of course, properly scaled and positioned in the Cartesian plane all the same), and suppose that I want to find a way to model and define a rugby ball that is an "average" of the rugby balls previously mentioned.

I hope I was clear.

Thanks you again

I think the major issue here is that a rugby ball cannot be represented very well by an nth order polynomial. Here's an example to illlustrate this: suppose I have an ellipse defined by:



and suppose a = 2 and b = 1. The following 3 points are all on that ellipse:

(0,1)
(1, 0.866)
(2,0)

If I use these values to solve for the coefficients in the equation I get:

.

You can see from the attached figure that this parabola doesn't match the ellipse very welll at all.

Attached Images

 

As always, you are right.

So, do you think that the only thing I could do is to interpolate alle the point of the shape via Lagrangian interpolation?

Consider also that the points has a sort of "monotonic" structure as you can imagine from the shape.

Lagrangian interpolation will simply give you the nth order polynomial that we've been talking about. I think if you take enough data points the method can give a pretty good approximation; it's just not going to be exact. Attached you can see what happens if you approximate the ellipse by 2nd order, 4the order, an 8th order polynomials - it gets pretty good within the range of points measured.

Attached Images

 

Thank you, you are always very clear.

Yes, it seems that the approximation is very good with the growth of the points to be interpolated (consider that in my cases there are a lot the points, for example in an image of 640X480 pixels, imagine how many thousands of points are needed to represent the boundary of a rugby ball). However, the thing that interests me is that all the points of the shape are taken into account, no exceptions, regardless of the shape that I intend to represent, which could be an ellipsoid, but also, more specifically, an ovoid or otherwise any other closed curve exhibiting a symmetry along the semi-major axis.

However, from this discussion I can derive that, given a set of points representing a form (not known a priori), there isn't a general method that allows to obtain the equation that represents that shape, and the only "mathematically/geometrically correct" representation of this shape may be obtained only by interpolating all its points in a lagrangian form?

According to you, I'm right?

Yes. The basic problem here is that given N points there are an infinite number of curves that can fit those N points, so without any additional information it's impossible to know which curve is "correct." Using the method we've been dicussing here gives one possible curve that fits the points, and given large enough N it may be "good enough." But keep in mind that the nth-order polynomial is a proper function - given x there is one value for y - whereas for an ellipse, circle, or any cliosed shape there may be two (and perhaps more) values of y for each value of x. So the polynomial fails if you enter two values for y for the same value of x; for example no polynomial can fit both (0,1) and (0,-1). Also be careful to not use both positive and negative values of 'y' as it can mess things up - attached is the 8th order polynomial but with some of the y values being negative, and it looks nothing like the ellipse the points were taken from!

Attached Images

 

Thank you very much for all. If I have some other question I'll let you know.

I'm sorry for your trouble and thank you again.

No trouble at all! Good luck with your project.