CODEWITHSUNDEEP
algorithmmathcurve-fittingspline
Tiger
Tiger

Reputation: 43

Dividing cubic spline computation

I have n points (20k to 30k) in 3D, I want to interpolate them using cubic spline. The problem here is that I will not have all of these points at the same time, they will be sent to me. so I don't want to wait until receive all of them to start the interpolation.

As a result, I choose to split these points into subsets, interpolate the first subset of points ,use it, and by the time start interpolate the next subset of points and so on

(split these points into subsets of hundreds points n1,n2,... and find the splines for each subset so that the result is identical to the result of the n point splines curves.)

I thought that overlapping these subset during computation is enough to do that but it seems not. what do you suggest to solve this?

Upvotes: 1

Views: 447

Answers (2)

user1196549
user1196549

Reputation:

You can start the interpolation at any time, using the available points (presumably in the correct order !). Cubic spline interpolation is a very stable process and when you add more points, most of the curve remains unchanged.

If your concern is that you want to avoid redoing the whole computation several times, I guess that it is enough to work on several sections with some overlap (say 20 points) and discard the results of the 10 extreme points of all sections.

Upvotes: 1

MBo
MBo

Reputation: 80187

Calculation of interpolation splines is performed over the whole point sequence, and results for two separate halves with overlapping would be slightly different. Note, for example, that border condition for the last point of the first spline might include predefined bias or zero curvature, while the same part of the second spline is calculated to provide continuity.

You can try to calculate some kind of smooth transition for overlapping region.

Edit After question update - I don't see relation between parallel treatment and your problem.

Instead you can connect subranges with C1-continuity:

Calculate splines interpolation for the first set of point. Use free-end condition - zero curvature. Remember bias (linear coefficient) in the terminal point.

For the every next set calculate spline interpolation using predefined starting bias - from the last set, and ending zero curvature condition again.

BTW, spline interpolation for thousands of points should work very fast (it is linear algorithm). Is it really bottleneck?

Upvotes: 1

Related Questions