Non-uniform bi-linear interpolation

In summary, the speaker is trying to find a solution for interpolating velocity data on a non-uniform grid, specifically using tri-cubic interpolation. They discuss different methods for interpolation, including RBFs and bicubic/cubic spline. They mention the challenge of finding nearest neighbors and creating a Delaunay triangulation for 3D interpolation. They also mention a solution they found for the bi-linear problem, using "inverse bi-linear interpolation/transformation" to determine ratios for interpolation.
  • #1
ponjavic
225
0
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.
 

Attachments

  • interp.JPG
    interp.JPG
    5.7 KB · Views: 573
Physics news on Phys.org
  • #2
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
 
  • #3
0xDEADBEEF said:
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.
 

1. What is non-uniform bi-linear interpolation?

Non-uniform bi-linear interpolation is a method of interpolating data points in a non-uniform grid, where the spacing between data points is not constant. It uses a mathematical algorithm to estimate values at points that lie between known data points, based on the values of the surrounding data points.

2. How does non-uniform bi-linear interpolation differ from regular bi-linear interpolation?

In regular bi-linear interpolation, the grid is uniform, meaning that the spacing between data points is constant. Non-uniform bi-linear interpolation takes into account the varying spacing between data points in a non-uniform grid, resulting in a more accurate interpolation of values.

3. What are some common applications of non-uniform bi-linear interpolation?

Non-uniform bi-linear interpolation is commonly used in image processing, computer graphics, and numerical analysis. It can also be applied in various scientific fields such as meteorology, geology, and fluid dynamics.

4. How is non-uniform bi-linear interpolation calculated?

The calculation for non-uniform bi-linear interpolation involves using a weighted average of the surrounding data points to estimate the value at the desired point. The weights are determined based on the distance between the data points and the desired point.

5. What are the advantages of using non-uniform bi-linear interpolation?

Non-uniform bi-linear interpolation allows for more accurate estimation of values in a non-uniform grid compared to other interpolation methods. It also takes into account the varying spacing between data points, making it a more versatile method that can be applied to a wide range of datasets.

Similar threads

  • Programming and Computer Science
Replies
1
Views
9K
  • Linear and Abstract Algebra
Replies
4
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
  • Programming and Computer Science
Replies
6
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
4K
  • Topology and Analysis
Replies
2
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
1K
  • MATLAB, Maple, Mathematica, LaTeX
Replies
2
Views
2K
  • Special and General Relativity
Replies
1
Views
1K
Replies
3
Views
622
Back
Top