Linear interpolation of two vector arrays with different lengths

Question

I have two curves. One handdrawn and one is a smoothed version of the handdrawn. The data of each curve is stored in 2 seperate vector arrays. Time Delta is also stored in the handdrawn curve vector, so i can replay the drawing process and so that it looks natural.

Now i need to transfer the Time Delta from Curve 1 (Raw input) to Curve 2 (already smoothed curve).

Sometimes the size of the first vector is larger and sometimes smaller than the second vector.
(Depends on the input draw speed)

So my question is: How do i fill vector PenSmoot.time with the correct values?

Case 1: Input vector is larger

PenInput.time[0] = 0         PenSmoot.time[0] = 0
PenInput.time[1] = 5         PenSmoot.time[1] = ?
PenInput.time[2] = 12        PenSmoot.time[2] = ?
PenInput.time[3] = 2         PenSmoot.time[3] = ?
PenInput.time[4] = 50        PenSmoot.time[4] = ?
PenInput.time[5] = 100
PenInput.time[6] = 20
PenInput.time[7] = 3
PenInput.time[8] = 9
PenInput.time[9] = 33

Case 2: Input vector is smaller

PenInput.time[0] = 0         PenSmoot.time[0] = 0
PenInput.time[1] = 5         PenSmoot.time[1] = ?
PenInput.time[2] = 12        PenSmoot.time[2] = ?
PenInput.time[3] = 2         PenSmoot.time[3] = ?
PenInput.time[4] = 50        PenSmoot.time[4] = ?
                             PenSmoot.time[5] = ?
                             PenSmoot.time[6] = ?
                             PenSmoot.time[7] = ?
                             PenSmoot.time[8] = ?
                             PenSmoot.time[9] = ?

Simplyfied representation:

PenInput holds the whole data of a drawn curve (Raw Input)

PenInput.x         // X coordinate)
PenInput.y         // Y coordinate)
PenInput.pressure  // The pressure of the pen)
PenInput.timetotl  // Total elapsed time)
PenInput.timepart  // Time fragments)

PenSmoot holds the data of the massaged (smoothed,evenly distributed) curve of PenInput

PenSmoot.x         // X coordinate)
PenSmoot.y         // Y coordinate)
PenSmoot.pressure  // Unknown - The pressure of the pen)
PenSmoot.timetotl  // Unknown - Total elapsed time)
PenSmoot.timepart  // Unknown - Time fragments)

This is the struct that i have.

struct Pencil 
{
    sf::VertexArray vertices;
    std::vector<int> pressure;
    std::vector<sf::Int32> timetotl;
    std::vector<sf::Int32> timepart;
};

Answer 1

[This answer has been extensively revised based on editing to the question.]

Okay, it seems to me that you just about need to interpolate the time stamps in parallel with the points.

I'm going to guess that the incoming data is something on the order of an array of points (e.g., X, Y coordinates) and an array of time deltas with the same number of each, so time-delta N tells you the time it took to get from point N-1 to point N.

When you interpolate the points, you're probably going to want to do it intelligently. For example, in the shape shown in the question, we have what look like two nearly straight lines, one with positive slope, and the other with negative slope. According to the picture, that's composed of 263 points. We could reduce that to three points and still have a fairly reasonable representation of the original shape by choosing the two end-points plus one point where the two lines meet.

We probably don't need to go quite that far though. Especially taking time into account, we'd probably want to use at least 7 points for the output--one for each end-point of each colored segment. That would give us 6 straight line segments. Let's say those are at points 0, 30, 140, 180, 200, 250, and 263.

We'd then use exactly the same segmentation on the time deltas. Add up the deltas from 0 to 30 to get an average speed for the first segment. Add up the deltas for 31 through 140 to get an average speed for the second segment (and so on to the end).

Increasing the number of points works out roughly the same way. We need to look at exactly which input points were used to create a pair of output points. For a simplistic example, let's assume we produced output that was precisely double the number of input points. We'd then interpolate time deltas exactly halfway between each pair of input points.

In the case shown in the question, we start with unevenly distributed inputs, but produce evenly distributed outputs. So the second output point might be an average of the first four input points. The next output point might be an average of three input points (and so on). In many cases, it's likely that neither end-point of a segment in the output corresponds precisely to any point in the input.

That's fine too. We interpolate between two points of the input to figure out the time hack for the starting point of the output segment. Likewise for the ending point. Then we can compute the total time it should have taken to travel between them based on the time delta between the points.

If you want to get fancy, you could use a higher order interpolation instead of linear. That does require more input points per interpolation, but it looks like you probably have plenty to do something like a quadratic or cubic interpolation (in most cases). This is likely to make the most differences at transitions--places the "pen" was accelerating or decelerating quickly. In such an place, linear interpolation can give somewhat misleading results (though, given the number of points you seem to be working with, it may not make enough difference to notice).

As an illustration, let's consider a straight line. We're going to start from 5 input points, and produce 7 output points.

So, the input points are [0, 2, 7, 10, 15], and the associated time deltas are [0, 1, 4, 8, 3].

So, out total distance traveled is 16, and we want our output points to be evenly distributed. So, the distance between output points will be 16/7 = (roughly) 2.29.

So, obviously the first output point and time are both 0. The second output point is 2.29. To compute the output time, we take the entirety of the time to the first input point (0->2), plus .29 / (7-2) * (4-1). That interpolated section gives 1.37, so our first output time delta is 2.37.

The next output point should be at a distance of 4.58. Since the second input segment goes from 2 to 7, our entire second output segment will lie within the second input segment. So, we take 2.29 / (7-2), telling use that this output segment occupies .458 of the input segment. We then multiply that by the time for the second input segment to get the time delta for the second output segment: .458 * (4-1) = 1.374.

[...and it continues on the same way until we reach the end.]