I have to generate a path from a dataset of n points. I am plotting a cubic spline through the points in this dataset. The generated path must contain an exact number of projected path-points.

My problem is not with the plotting of the curve but rather with the distribution of the path-points along the x-axis to yield a path that is made up of an exact number of path-points. This is why I have reduced the following example to a one dimensional array of points through which a straight line should be plotted. Each point in the dataset should represent the beginning of a curve segment (even though the curve is really a line because of the simplification).

My current naive approach is not exact ie it does not yield a path that contains the specified number of points (it's off by 4-5 points depending on the density of the dataset and the specified targetLength).

I think I'll have to use linear interpolation to get an exact result but I don't know how. Can anyone help or point me in the right direction?

Naive approach (javascript):

// Array with floating point values constrained between 0 - 1
// Think of each value as the beginning of a line segment.
const dataset = [0, 0.123, 0.3432, 0.454, 0.56, 0.8334, 0.987, 1];

// Path should have this many points
const targetLength = 1024;

// Step distance between points
const delta = 1 / targetLength;

// The path array we're generating
const path = [];

// For each point (segment)
for (let i = 0; i < dataset.length - 1; i++) {

  const x1 = dataset[i]; // current point
  const x2 = dataset[i + 1]; // next point
  const xd = x2 - x1 - delta; // dist between current and next point(-delta)

  // For each step in the segment generate a path-point
  for (let k = 0; k <= xd; k += delta) {
    // For this example we're only pushing the x-value onto the array.
    // In the real implementation I'm calculating a y-value to plot a curve
    // and push an array of [x, y] onto the dataset.
    path.push(dataset[i] + k);


// expect: path.length === targetLength

In the above example I expect path.length to equal targetLength (1024). I could take the generated path as a whole and interpolate the entire array but I think I'm looking for a smarter way to generate the path in the first place. Any help is greatly appreciated!

1 Answers

Matt Timmermans On

It really looks like what you want is just this:

for (let i=0; i<targetLength; ++i) {
    path.push(i / (targetLength-1));

... because this is what you are approximating, and it actually makes sense for some kinds of cubic spline interpolation. You wouldn't normally need to store these path points, however, because they are so easy to calculate.