1
$\begingroup$

In fact, I am not good at maths but good at developing software. My current project involves implementing a method, for interpolating a curve.

But I can´t figure out what kind of curve this is. I have analyzed a curve, which I want to "reproduce". Maybe you guys can tell me, which type of curve this is (click to enlarge):

Curve

I've used following control points (don't get me wrong, this curve is generated by a different software, I wan't to reproduce this by implementing the method in my program):

cpx = [0, 9.48732, 37.7707, 53.0929, 83.0766, 124.333,128.004]; 
cpy = [0, -89.9931, 19.9962, -89.9986, 0, -89.9991,0];
$\endgroup$
  • $\begingroup$ You have a "phase wrapping" phenomenon. The vertical bars have no meaning by themselves, you only have to unwrap by shifting down the part of the curve above interval $[195,121]$ or so by $2 \pi$ (Imagine your ordinate axis has ticks on multiples of $\pi$ with $\pi \leftrightarrow 200$). $\endgroup$ – Jean Marie Nov 6 '16 at 11:04
  • $\begingroup$ if you are working with matlab (fr.mathworks.com/help/matlab/ref/unwrap.html) $\endgroup$ – Jean Marie Nov 6 '16 at 11:09
  • $\begingroup$ I wasnt referring to the phase wrapping. That part is clear for me why this happened. I was asking for the function or algorithm which is used to generate this curve with those given control points. $\endgroup$ – Vertices Nov 6 '16 at 11:20
  • $\begingroup$ Sorry but as you have given an example showing this phenomenon without mentionning that there was not your problem, I couldn't guess... $\endgroup$ – Jean Marie Nov 6 '16 at 13:23
  • $\begingroup$ That was not an offense, I am sorry :) $\endgroup$ – Vertices Nov 6 '16 at 14:14
1
$\begingroup$

There are several common ways to perform interpolation. The two most common methods use polynomials and splines (usually cubic splines). Both methods are described on this page.

Just from looking at it, I would guess that the example curve you showed is a cubic spline. But that's just a guess.

If you have a choice, I would suggest using cubic splines. If you have $n+1$ points, then, to use a polynomial interpolant, you'd need one of degree $n$. High degree polynomials are expensive to evaluate, and they tend to be "wiggly". Splines don't suffer from either of these problems.

There are plenty of software packages available for constructing cubic splines. A few of them are referenced on this page. The one you choose will depend partly on the programming language you're using.

$\endgroup$
  • $\begingroup$ You are right, this is a bezier curve, I am an idiot, how did I missed that... Thanks... :) Now I have to figure out which bezier control points are used per vertex. $\endgroup$ – Vertices Nov 6 '16 at 11:36
  • $\begingroup$ A cubic spline is a sequence of cubic Bezier curves, strung end-to-end smoothly. The spline construction will tell you the equation of each cubic piece, and from there you can get the Bezier control points. $\endgroup$ – bubba Nov 6 '16 at 11:55
1
$\begingroup$

Like mentioned above, this curve is a bezier curve. What I am trying to figure out is, which contoll points are being calculated.

See, In the program where I am generating this curve above, I am only setting those control points:

cpx = [0, 9.48732, 37.7707, 53.0929, 83.0766, 124.333,128.004]; 
cpy = [0, -89.9931, 19.9962, -89.9986, 0, -89.9991,0];

Then 6 bezier curves are generated. For a bezier curve I need 4 control points.

p0 = cp
p1 = ..
p2 = ..
p3 = cp + 1

I have build a hermite spline with a start derivative and an end derivative and coverted it to bezier:

p0 = cp
p1 = cp + startDervivative / 3
p2 = (cp + 1) - startDervivative / 3
p3 = (cp + 1)

What I need to figure out is, which derivatives are used (how they are calculated)... I know that the start and end derivatives are dependent of the last bezier curve end point, next bezier curve end point and their curve lengths in X direction, but I didn´t found the correct calculation to reproduce the curve...

I have experimented with the start and end derivatives by guesing them. I can generate an acurate curve.

Let me give you an example (I thinks its self explaining): curve

$\endgroup$
  • $\begingroup$ Spline packages calculate the missing derivatives by assuming that second derivatives are continuous at each join. This gives you a set of linear equations that you can solve. But there's nothing magic about this approach, and there are other ways to estimate derivatives that might work for you. Look up Catmull-Rom splines, or cubic Bessel methods, for example. folk.uio.no/in329/nchap5.pdf $\endgroup$ – bubba Nov 9 '16 at 12:43
  • $\begingroup$ Try this library: github.com/retuxx/tinyspline $\endgroup$ – bubba Nov 9 '16 at 12:47
  • $\begingroup$ Hey, thanks... Did worked for me... $\endgroup$ – Vertices Nov 11 '16 at 7:45
-2
$\begingroup$

Lagrange interpolation theorem states that (in programming parlance) given two arrays of numbers of equal length $n$ there is a polynomial function of degree $n$ or less, such that applying that function to arguments from the first array outputs the second array.

$\endgroup$
  • $\begingroup$ To the anonymous/silent downvoter: Given any two finite set of $x$-values and $y$-values there is always a polynomial curve that passes through them. OP has the discrete datapoints connected in a particular way that only she/he knows why. I have said it is always possible to fit a polynomial curve (not me, Lagrange). $\endgroup$ – P Vanchinathan Nov 6 '16 at 11:10
  • $\begingroup$ @P Vanchinathan I say at once I am not the downvoter. But Lagrange interpolation is almost only a theoretical tool. Numerically it is known to generate very large oscillations (math.stackexchange.com/q/1577735) $\endgroup$ – Jean Marie Nov 6 '16 at 13:21
  • $\begingroup$ @JeanMarie: thanks for your helpful pointer. I have seen the word cubic spline, but did not know what it was. The oscillation problem of Lagrange are news to me and definitely something I am starting to learn today. $\endgroup$ – P Vanchinathan Nov 6 '16 at 13:38
  • $\begingroup$ I wasn't the down-voter, either, but I did consider down-voting. Reasons are: (1) Lagrange interpolation with more than 4 or 5 points will often produce wiggles, unless it's done properly (and you didn't say how) (2) From looking at it, it's clear (to me) that the curve is not a polynomial; it's a piecewise cubic. (3) Your numbers are off by one -- to interpolate $n$ points, you only need a polynomial of degree $n-1$. $\endgroup$ – bubba Nov 12 '16 at 3:35

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.