How Can I Use Reverse Linear Interpolation in My Computer Simulation?

[sciwizeh]

I've run into a problem programming a computer simulation. I have a discrete grid of values and a point an the middle with a value and I need to take the value and put it into the grid. I've been working on the 1 dimensional problem, and I can't get it. I know it's something simple I'm missing.

In order to go the other direction it's easy, val = (1-t)x+(t)y (t<=1) and I'm looking for the way to get x and y knowing t and val I believe Calc 1 and 2 pushed the algebra right out of my head. As I said i know I'm missing something really simple here.

Can anyone point out the simplicity that I am actually missing here.

 

[Filip Larsen]

In principle, you need some kind of model for your (uneven) sample data.

In the one-dimensional case for instance, you can perhaps assume that the value varies linearly between your samples, so that the value at a grid point is the linear interpolation between the first sample "to the left" and first sample "to the right". If the grid extends beyond the sample data you have to evaluate if some kind of extrapolation [2] will make sense for your data.

In the two-dimensional case one can make a similar linear model ending up with bi-linear interpolation [2], but depending on the density of your samples there may be some special cases you need to handle.


[1] http://en.wikipedia.org/wiki/Extrapolation
[2] http://en.wikipedia.org/wiki/Bilinear_interpolation

 

[sciwizeh]

Thanks for the fast reply, I'm not sure that is what I need, I do intend to use a linear variation. I have the continuous value from between two discrete points, and i want to know what the discrete points should be based on the value

here is the situation assuming that there is a linear gradient between x and y, if we know x,y, and a we can easily calculate val with val=(1-a)x+ay

I am interested in finding values for x and y knowing only val and a, again assuming a linear gradient between x and y

Is it even possible? I could swear that this should be easy but I'm just missing something simple.

 

[Filip Larsen]

Without any further knowledge of your data it is almost meaningless to extrapolate a single value to x and y. If all your data is represented by a single value between x and y and there are no other values left of x or right of y, then you may as well assume that values are constants so that the value at x and y is val since it surely does not make sense to make a linear extrapolation of a single point.

Perhaps if you described a bit more of what your data values represent it may turn up some hints of what kind of model that would fit your value(s).

 

[Filip Larsen]

That certainly helps explains the background for your problem.

If you are trying to implement the "accumulating forward advection" scheme that the author illustrates with figure 3, then the value S advected from P to P' is linearly distributed to the four points based on the rectangular distances. If we assume the grid length is one and that P' projected onto AB is x from A (and therefore 1-x from B) and likewise P' projected onto AC is called y, you can find the contribution to the value at A as S_A = x*y*S, at B as S_B = (1-x)*y*S, at C as S_C = x*(1-y)*S, and finally at D as S_D = (1-x)*(1-y)*S. You can check that S_A+S_B+S_C+S_D = S as it should when you have a conserved value ("mass conserving" as the author calls it). Notice, that the author then goes on to modify this scheme further to account for advection of scalar fields that does not have negative values.

Also note, that the method the author describes is, in his own words, meant to be visually pleasing simulation of fluid motions in games and similar. If your simulation need to have any physical accuracy to it you most likely have to resort to more advanced methods (like those used as part of Computational Fluid Dynamics).

 

[sciwizeh]

Thank you for the explanation, that is exactly what i needed. about your notes, i am aware that it is meant to be visually appealing for games, in fact I'm trying to make a simple sandbox game with wind, and i think that this will be a good starting point. i hope to make something similar to: http://dan-ball.jp/en/javagame/dust/ which may very well use a similar method