# C++ Linear interpolation of two vector arrays with different lenghts

## Recommended Posts

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 (the 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 the whole vector PenSmoot.time with the correct interpolated 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] = ?

##### Share on other sites

If I understand correctly, you have parametric descriptions of curves ("time" is the parameter), where you know the position for certain set of parameter values, and you want to interpolate between two such descriptions.

I would start by taking the union of the sets of parameter values. Describe both curves using this extended set of parameter value and then interpolate the values at each point.

Does that make sense?

Never mind. I think I misunderstood the question.

Edited by alvaro

##### Share on other sites
Hello, thanks for trying.
I need to transfer the Time Deltas (milliseconds it took from one point to the next) from the Raw input curve to the smoothed curve.

##### Share on other sites

I don't believe you need to inerpolate, functionalize this information?

##### Share on other sites

I'm probably also not understanding the question, but:

Since you can switch back and forth between delta times and absolute times easily enough, it seems like you could assign each of the points of the left-hand curve an absolute time.

For each of the points on the right-hand curve, you can find the closest point on the left-hand curve, using the segments between the points on the left-hand curve and a 'closest point on segment' function. One you have a segment and a closest point, you can compute an interpolation value between the endpoints of the segment. Then you can use that interpolation value to compute an absolute time for the right-hand point in question. Once you have absolute times, you can of course derive the deltas if needed.

Again, I suspect I'm also misunderstanding and that the above solution may be irrelevant or naively incorrect, but maybe it can at least help advance the discussion.

##### Share on other sites

I think I now understand the problem, and I know how to solve it using dynamic programming. I'll post something this evening.

##### Share on other sites
@JohnnyCode You mean instead of interpolate it shoud be functionalized? What does this mean?

@Zakwayda I actually record the absolute times and calculate the deltatimes after mouse release. So i have both times already.
I think you understand exactly what i mean. Just one thing that i want to point out is that the size/lenght of the curves vectors can and will be different
based on the input draw speed. So sometimes the handdrawn vertex array is larger than the smoothed one and sometimes vice versa.

I store the data in a struct like this and i use SFML
struct Pencil
{
sf::VertexArray vertices;
std::vector<int> pressure;
std::vector<sf::Int32> timeAbslt;
std::vector<sf::Int32> timeDelta;
};

@alvaro Dynamic programming. I didnt know about that but what i have found out it sounds like what Zakwayda said. Splitting the problem into sections and solving them one by one.

Thank you all for your help!

##### Share on other sites
13 minutes ago, C3D_ said:
I think you understand exactly what i mean. Just one thing that i want to point out is that the size/lenght of the curves vectors can and will be different
based on the input draw speed. So sometimes the handdrawn vertex array is larger than the smoothed one and sometimes vice versa.

alvaro may have something different in mind for you, but for what it's worth, the solution I proposed is intended to account for differing numbers of points between the two curves. The idea is that for each point on the second curve, you find the closest point on the first curve (treating the first curve as a series of line segments), and then use interpolation to find the absolute times based on that. With this approach, the first curve could have 3 points and the second curve 300, or vice versa, and it should still work.

It it's not clear what I'm describing, I'll be happy to elaborate. (Or maybe alvaro will offer a better solution in the meantime.)

##### Share on other sites

Hello,

Iam still integrating it into my program and testing it.
But just so everybody knows.

@Zakwayda Okay. I understand. Thank you very much. I will test paddy's code and then catch up.

##### Share on other sites

I looked at the demo code you linked to. I'm not entirely sure it addresses your problem. Among other things, it performs no resampling if the point sets have the same number of points, which doesn't seem to fit your use case.

I'm not saying the demo isn't what you want (I didn't analyze it that carefully), but if you find you're still not getting the behavior you want, you could post back. (I'll also mention that it's possible a solution - not necessarily the solution in the demo, but any solution - could give you results that maybe look correct, at least for certain input, but aren't actually correct.)

[Edit: Thinking about it a bit more, I'm pretty sure that code is not what you're after. I'm not saying that with certainty - I could be wrong 🙂 But it's my initial impression.]

Edited by Zakwayda

## Create an account

Register a new account

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 11
• 23
• 36
• 16
• 75