Non-uniform bi-linear interpolation

[ponjavic]

I have a non-uniform grid within which velocity data is known at each grid point. This velocity data is to be interpolated to allow for evaluation of velocity at an arbitrary point inside the grid.

I am wondering about the correct approach to this problem. In actuality I want to evaluate the velocity using tri-cubic interpolation but considering the grid is non-uniform I would start with basics.

In the image you can sort of see what the grid looks like. I have for example points [1 2 3 4] and I want to evaluate the velocity at point X (x, y). dx is constant but dy is different between (x) and (x+1) therefore two different dy exist to account for this; dy1 and dy2.

So bilinear interpolation:
interpolate normally between 1 and 2 using dy1, interpolate between 3 and 4 using dy2, here comes the problem. I assume simply interpolating between the two found values using dx is enough? Possibly dx could be extended by the fact that it is now somewhat tilted (simple trigonometry). But then again the same tilt would apply to the position of X, i.e. the distance it is in x from point 1 and 2.

What is the correct way of doing this? I suppose if I figure out this it should not be too hard to extend to tri-cubic.

 

[0xDEADBEEF]

I am not sure if you understand what tricubic means and I am not sure if I understand your grid.

I assume you have something like this, a set of coordinate points each consisting of three floating point numbers and a corresponding set of velocity vectors also consisting of three floating point numbers. We are talking about a velocity field, not the path of a single particle.

The first thing you do is splitting the interpolation into three parts one for each velocity component.

0) If it's physics alway try to fit a working theoretical model fist
otherwise:
1) I assume you have found the myriad of 1-d interpolation routines that are out there.
2) 2D is more tricky. And it depends a lot on your data. If your data is not really on any kind of grid, you can use RBFs radial basis functions, there are fit routines for that out there. They don't seem very popular.
You can force your data onto a grid. The grid is defined by the ticks on each axis. For that you can do some kind of nearest neighbor interpolation. Be warned: linear interpolation with nearest neighbors sucks. What you want to do is interpolation with natural neighbors. For that you need the Delaunay tesselation of the data. On a real grid you can then do bicubic b-splines or c-splines. There are routines for that.
3) Tricubic and n dimensional interpolation. It is very similar to 2d but this case is harder, because getting the nearest neighbors is harder, getting a Delaunay triangulation is much harder because some 2d tricks cannot be used. RBFs still work. I don't trust consecutive b-splining that much... but that is probably the way to go. I rolled my own cspline routine for this stuff about which I am not yet confident enough to share but it looks promising.

This might help:
http://www.scipy.org/Cookbook/Interpolation

 

[ponjavic]

I am not sure if you understand what tricubic means and I am not sure if I understand your grid.

I assume you have something like this, a set of coordinate points each consisting of three floating point numbers and a corresponding set of velocity vectors also consisting of three floating point numbers. We are talking about a velocity field, not the path of a single particle.

The first thing you do is splitting the interpolation into three parts one for each velocity component.

0) If it's physics alway try to fit a working theoretical model fist
otherwise:
1) I assume you have found the myriad of 1-d interpolation routines that are out there.
2) 2D is more tricky. And it depends a lot on your data. If your data is not really on any kind of grid, you can use RBFs radial basis functions, there are fit routines for that out there. They don't seem very popular.
You can force your data onto a grid. The grid is defined by the ticks on each axis. For that you can do some kind of nearest neighbor interpolation. Be warned: linear interpolation with nearest neighbors sucks. What you want to do is interpolation with natural neighbors. For that you need the Delaunay tesselation of the data. On a real grid you can then do bicubic b-splines or c-splines. There are routines for that.
3) Tricubic and n dimensional interpolation. It is very similar to 2d but this case is harder, because getting the nearest neighbors is harder, getting a Delaunay triangulation is much harder because some 2d tricks cannot be used. RBFs still work. I don't trust consecutive b-splining that much... but that is probably the way to go. I rolled my own cspline routine for this stuff about which I am not yet confident enough to share but it looks promising.

This might help:
http://www.scipy.org/Cookbook/Interpolation

I have a perfectly good understanding of tri-linear interpolation although my question might have seemed unclear. Here I was simply trying to find a solution for the bi-linear problem which I would the extrapolate to the tri-cubic one.

In any case I found a solution to the problem and it is "inverse bi-linear interpolation/transformation". This returns the ratios alpha and beta which describe how far along the x and y-axis respectively the point can be considered to be. Naturally these ratios can be used in place of the normal ratio (x_point-x_grid)/dx to conduct bi-linear interpolation.