0
$\begingroup$

I have n Cartesian points P(x,y). I would like to draw a curve through those points so that I can project it, compute tangents to it, etc.

In practice, 30 < n < 500, or thereabouts. My values for x and y are all integers and won't lie exactly on the ideal curve. The curves I've got generally look to me like arcs from parabolas. The parabolas can have any orientation, so we are dealing with the general case, not merely specific cases where the directrix is x=c or y=c.

I have very little clue how to do this. I could probably manage to best fit a quadratic in the case where the directrix is y=c - this is an algorithm I'd find in a text book - but as I explained above, the directrix will have gradient<>0. I could rotate the parabolas into this orientation but the problem with that is I don't know what angle to rotate them through until I have an equation, so it doesn't help.

The application is computer vision.

I suspect the answer is probably more complex than can realistically be posted here so perhaps a reference to an existing work could be given?

If it simplifies matters to say the curve isn't a parabola but something similar then that will do; this is an engineering question, after all!

$\endgroup$
5
$\begingroup$

The general equation of a conics is $$Ax^2 + Bxy + Cy^2 +Dx + Ey + F = 0$$ Dividing all terms by $A$, you then have $$x^2+a x y+b y^2+c x+d y+e=0$$ For each of the data point $(x_i,y_i)$, you then have the equation $$F_i=x_i^2+a x_i y_i+b y_i^2+c x_i+d y_i+e=0$$ and you could consider this as a multilinear regression. You also can solve the problem using matrix calculations.

This is equivalent to minimizing $$\Phi=\sum_{i=1}^n F_i^2$$

Edit

If you want to be sure that the curve is a parabola, you must impose $a^2=4b$ and the regression becomes nonlinear. You can use the values obtained in the first step to initialize the parameters in the nonlinear regression.

For illustration purposes, I made a small problem using the following data points $$\left( \begin{array}{cc} x_i & y_i \\ 6 & 10 \\ 7 & 12 \\ 8 & 15 \\ 9 & 17 \\ 6 & 6 \\ 7 & 6 \\ 8 & 7 \\ 9 & 8 \end{array} \right)$$

The first step leads to $\Phi=1.34617$ for the following coefficients $$a= -0.954238\quad b= 0.291388\quad c= -6.98518\quad d= 1.2781\quad e= 21.9119$$ but this would be an ellipse.

Using these as estimates and introducing the constraint leads to to $\Phi=1.85887$ for the following coefficients $$a= -1.21153\quad b= 0.366953\quad c= -4.81902\quad d= 1.69162\quad e= 12.6085$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Awesome - thanks. That looks sufficiently detailed yet sufficiently simple. And such a quick response, too. I will give it a try over the next couple of days. ;-) $\endgroup$ – Nobody Sep 3 '16 at 9:04
  • $\begingroup$ I've got this working - thanks - but the algorithm isn't fitting my curve terribly well. Sometimes it's fine but often the conic is computed to double back on itself so that it passes through the points twice. For the points known the curve kind of fits (somewhat poorly) but the idea is to extend the curve to make a projection. For that the curve is sadly useless. It's like throwing a ball to your partner but instead of it reaching your partner it goes in a near-straight line to the vertex then bounces right back at you. I used MathNet.Numerics.Fit.MultiDim using NormalEquations. Any ideas? $\endgroup$ – Nobody Sep 13 '16 at 23:49
  • $\begingroup$ Could you send me a .TXT file (format ${x_i,y_i}$) with a set of data making problems ? My e-mail address is in my profile. Cheers. $\endgroup$ – Claude Leibovici Sep 14 '16 at 5:36
  • $\begingroup$ @Nobody. I shall e-mail tomorrow. $\endgroup$ – Claude Leibovici Sep 14 '16 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.