Curve interpolation - creating a path from control points (interp1 can't reflect a circle)

Question

Kuba 2016-5-25

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/285810-curve-interpolation-creating-a-path-from-control-points-interp1-can-t-reflect-a-circle

编辑： Kuba 2016-5-26

Hello,

I try to create a smooth path through a set of control points. It is a part of optimisation procedure at path planning algorithm, so it can't be too slow and the result must be feasible. What are the methods to achieve this?

Currently I am using interp1() function. As the path may have vertical segments (various y values for a single x coordinate), I am interpolating x and y axis separately, like this:

xPoints = interp1( 1:PointsNumber, Points(:,1), 1:1/Resolution:PointsNumber, Method );

yPoints = interp1( 1:PointsNumber, Points(:,2), 1:1/Resolution:PointsNumber, Method );

Testing it on a quater-circle path, I would expect the interpolated curve to have a constant radius throughout the whole section. However it doesn't work so! Spline has a smooth radius changes, but does a 'snake-run' all the time. Pchip seems to keep the right shape, but numerical analysis shown huge jumps in local radii (ex. from 500 to 20), what is unacceptable in my case (makes a bottleneck for maximum speed allowed). V5cubic is somewhere between those two.

What are the other ways I could use? Especially, how would you interpolate a circle to reflect the constant radius?

This an example of what I want to do, control points marked with asterix symbol. You won't notice a difference between various interpolation methods without a zoom-in, but it is huge in terms of overall time calculation, basing on speed profile restricted by local radius and acceleration limits.

2 个评论
显示无隐藏无

dpb 2016-5-25

Is the locus of the circle constant with just varying radius or do both change during the process?

Kuba 2016-5-26

编辑：Kuba 2016-5-26

Do you mean a locally oscullating circles? Their centres are changing as well, take a look at this plot which shows normal lines to each pair of interpolated points and their intersection points with the next pair (scatter circles). This is regarding the PCHIP method.

As you can see, most of them intersect somewhere near the real arc centre, but there are a few which are moved to a much shorter radius. This is what disturbs me, as I'm doing a car speed profile for this path and such small local radius makes the vehicle decelerate for a long distance before even reaching this point.

Interpolated path resolution is kept low here for clarity purpouses, but I think it should keep a constant radius regardless. It is less significant with high resolution, but I don't want to make it too high due to increased computation time.

Now, this is how local radii look like if I apply this method only to the control points and this is what I would expect from a good interpolation method:

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

John D'Errico 2016-5-26

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/285810-curve-interpolation-creating-a-path-from-control-points-interp1-can-t-reflect-a-circle#answer_223507

编辑：John D'Errico 2016-5-26

I would suggest those interpolations did remarkably well. Did you expect some spline interpolant to magically intuit that this is a circular arc, and then a direct transition into a straight line? You have knowledge of the process that created those points. A spline interpolant sees nothing but a set of numbers, in x and y independently.

Even worse, then you fit those points as a function of point index, as the "independent" variable. I would point out that they are not even equally spaced in the (x,y) plane, but that you have chosen an equally spaced index as the parameter t. In effect, that introduces a potential problem because you introduced an artificial derivative singularity.

So, not only do you expect magical intuition on the part of a computer program, but you want it to be fast too. Sorry for the sarcasm, but if the shoe fits...

Splines are not perfect. They did a decent job as far as I can see. Splines tend to have problems at the end points, because less information is essentially available to them. Splines have problems at transitions from non-flat regions into perfectly flat regions. In fact, splines can be thought of as what I call a metaphorical model. A classical interpolating spline is actually a mathematical model of a physical system, that you are then applying as a model to your own system without any good reason, except that the spline will do a decent job in general. So, a metaphor in mathematics. As well, splines are at least reasonably fast to compute. (Yes, they are, compared to some random scheme.)

So splines tend to produce oscillations in flat regions, because of their nature. (Pchip is not a classical spline, but a close cousin thereof. It does handle those transitions to flat regions better, is fast, but is effectively a little less accurate in general.) Splines abhor singularities since they are based on polynomial segments, so you need to do the trick with a parametric fit, so (x(t),y(t)), but that too has issues.

An interpolation tool (such as a spline) is designed to produce a fit that is as acceptably smooth as possible to some set of data where it does not know the underlying model. Just some arbitrary set of points. Another day, another curve. Millions of curves - its a living. :)

If you demand better results on circular arcs as well as purely linear segments, you would need to use a tool that can recognize them as such. No, I'm not going to offer such a tool, as I don't have one on hand. I'd need to write such a code, and it would then surely fail to perform perfectly when you threw some other simple shape at it, a parabolic arc for example. (How could I know what you might do?)

And, no, a higher order spline is not a terribly good choice here. (I expect you might ask that question next.) The curve you have shown has an internal singularity, at the transition from a curved region into a flat line. A higher order spline will hit a spot like that, and do nasty (oscillatory) things between the points.

Don't even think of throwing some interpolating polynomial at this either. Polynomials abhor singularities too, and they do very nasty things to you, even on non-singular problems.

Could you write some code that would use locally circular arcs to fit to your curve? Of course, but making that code intelligent, producing smoothly varying circular arcs will be an interesting task, especially when those circular arcs sometimes transition into a region with an effectively infinite radius of curvature.

Anyway, to achieve something closer to perfection, you need to decide what set of shapes you expect to fit. Essentially, you need to provide a model for the system. You need to provide the advance intelligence, in the form of a viable description of the curve. And then you need to provide the code, since your problem is not anything that is fit by any standard tools. Of course, custom code may not be that fast either, depending on what it does, how much intelligence you try to put into the code.

Or, you may need to accept that a spline fit is not perfect, but does a decent job, SOMETIMES.

4 个评论
显示 2更早的评论隐藏 2更早的评论

Kuba 2016-5-26

Thank you for an answer.

Do I claim an impossible? Maybe, I will have to dig into algorithms to see if this is the case. All I want is to get a shortest fluent line through a set of points, and it seems that a fluent line through a set of circular points is simply a circle.

As for the splines, of course I understand they will produce some oscillations. It's just that those little oscillations make them less useful for me, as I am next calculating the time needed to get through this path. Having lots of oscillations make the time less realistic, as no vehicle will track them.

I hoped 'PCHIP' would give better results, but as mentioned, a problem here are sudden and unexpected curvature changes. I have noticed this at a different path shapes (anything that optimisation procedure would give me), this one is used only for validation purpouses - I know the 'real' radius so it's just easy to check. THIS IS NOT THE ULTIMATE PATH TO BE INTERPOLATED, so there's no point in using specific algorithms for circular or straight lines, it has to be universal. But I thought that a reliable algorithm should do well at these extreme cases as well.

Here's an example of a real path that I might want to interpolate:

John D'Errico 2016-5-26

PCHIP has a lower order of continuity than a normal cubic spline, so it will have more bumps and jiggles in the curve. PCHIP does have the virtue that it can easily transition between flat and non-flat regions. It can also change direction without introducing extraneous extrema in the curve, so those oscillations go away. Those abilities come with a price though, effectively a less smooth approximation. But more smooth interpolants introduce those other problems.

You are implicitly trying to compute the curvature of a curve, so effectively the second derivative. Estimation of the derivatives of a function is one variation of an ill-posed problem. That means it is tough to do, and tough to do well. Estimation of the second derivatives is more difficult to do accurately than the first derivative. Again, you are implicitly looking at the second derivative, and hoping for magic to occur. Expecting a generic interpolant to solve a specific problem, and to do so highly accurately and to do it fast is asking a lot. Far too much in fact.

Worse, you have a curve that has singularities (jumps) in the derivatives. I said this before, but you seem not to have understood why I said that was a problem. Actually, it is in the second derivative is where that jump occurs.

You have a nice smooth circular arc, then a direct transition into a straight line. In fact, that circular arc has a roughly constant curvature. The line has also curvature that is constant, but the two constants are very different. Then you use a tool that is designed to interpolate a curve with derivatives that are assumed to be well-behaved. So a spline is a C2 function. (PCHIP is only C1, but it has its flaws as I said above.) Your curve is not C2. You need to understand the disconnect.

Feel free to write a more reliable algorithm. :) Don't expect it to be fast, and I'll be very surprised if you can make it more reliable on any completely generic ("universal") curve shape. You know what you want to see. The eye/brain are very good at things like this, especially when you have the advantage of knowing what you expect as a result.

You state that you want the shortest line through the points. In fact, you don't, as that would be a connect the dots function, piecewise linear. So in fact, you want the shortest curve that has the properties that you expect in some places, and other properties in other places. And you want the tool to intuit from your brain how the curve should act. How should it know that a second derivative discontinuity is fine in some places, but not others?

IF you KNOW that a break in the curvature happens at a specific point, then you could build that in, with the proper tool (csapi should do it, with limitations.) But you would then need to supply additional information to the process.

John D'Errico 2016-5-26

There are other options of course. For example, you might consider tools like tension splines - there are multiple variations thereof. But expect that code to run somewhat more slowly, and you also tell of the need for speed. And of course, you would need to write a tension spline code yourself, or find one someplace.

Kuba 2016-5-26

编辑：Kuba 2016-5-26

"You have a nice smooth circular arc, then a direct transition into a straight line."

Oh, I see it now! I know about second derivatives issue, but somehow didn't realise that the transition from circle to a straight is actually nothing but a sudden jump in the curvature...

"You state that you want the shortest line through the points. In fact, you don't, as that would be a connect the dots function, piecewise linear. " I stated that I want the shortest FLUENT path - I meant the one feasible for a real car with no unnececessary deviations.

But anyways, thanks for a help. I thought there might be some other ways of interpolation I didn't know about, but maybe it's a matter of approaching the topic differently.

请先登录，再进行评论。

Curve interpolation - creating a path from control points (interp1 can't reflect a circle)

2 个评论
显示无隐藏无

回答（1 个）

4 个评论
显示 2更早的评论隐藏 2更早的评论

另请参阅

类别

标签

Community Treasure Hunt

Curve interpolation - creating a path from control points (interp1 can't reflect a circle)

2 个评论 显示 无隐藏 无

回答（1 个）

4 个评论 显示 2更早的评论隐藏 2更早的评论

另请参阅

类别

标签

Community Treasure Hunt

2 个评论
显示无隐藏无

4 个评论
显示 2更早的评论隐藏 2更早的评论