I would like to do an interpolation in 3D. I looked in nr book and found the following comment in chapter 3.6. : "we will not here consider the problem of interpolating on a mesh that is not cartesian"...
And of course :D , I would like to interpolate my values on a not cartesian grid... In fact, I have a varying number of interpolation points that are placed "randomly"...
Where could I find an algorithm or a method that I could apply to my case ?
Thank you

As I see that my post has been read a lot of times and that nobody answered, I guest I have to give a more accurate description of my problem :
I have a set of N scattered points. These points are the value of a 3D electric field and they are defined on the grid point. Unfortunately, the grid is not regular, so a cell could be made of 8 to 24 points. Then I have a particle P which is inside one of the cells. I "just" would like to know the electric field value seen by the particle. It'a a kind of barycentre... I have seen on the net some sites speaking about several kinds of interpolations (Shepard interpolation : inverse weighted method, Kriging method, etc...). Most of these method are used in Geophysics to interpolate the altitude of points on a ground map... But most of the time it's in 2D (x,y + the altitude), and my problem is 3D (x,y,z + E). So I tried to use the Shepard method, but there is a problem of accuracy : if all your points are in a plane, the interpolated point is not in it... So I'm looking for a method that could at least be exact in the case of a plane. The most important thing is that this method has to be fast : I can't invert a Matrix, it's quite to slow.
So if somebody has heard about some information on this topic, please give me a tip, an url, or a book of reference.
Thank you

So, if I understand you correctly, when you have a point to which you want to interpolate the field, you also know which 8 to 24 surrounding points that you want to use in the interpolation.

I think that in virtually any possible method you're going to have to invert a matrix of the size of that number of surrounding points -- that is, between 8x8 and 24x24. The reason is the irregularity of the grid. Interpolation formulas on regular grids are obtained by analytically inverting a matrix (just once) to get the interpolation formulas. Here, it's a different set of formulas for each irregular cell configuration.

I've always been a fan of Kriging, which definitely does generalize to 3-D. (If you Google search for "Kriging 3D" you'll get lots of hits.) I'd try Kriging using just some number of nearest neighbors (not necessarily just the points bounding your irregular cells). The art in Kriging is to pick an assumed correlation function that gives reasonable results.

Yours is actually a hard problem. Good luck!

Thank you for your contribution to my problem... I think I will try a kriging method, but unfortunately, it will certainly be too long for me (I do it several millions of times)... Anyway, thank you

I would recommend using natural neighbour interpolation. It has the overhead of creating a Voronoi diagram but that only needs to be done once, and needs to be updated when you add/remove the point that you want to interpolate. The algorithm then uses the data values in neighbouring cells to calculate a weighted average. There is much information about natural neighbour interpolation on the web. Good luck!

While I am sure this answer is no longer of any use for the original question, I found that I had to do almost exactly the same thing described - to find that there is very little information on the internet to help.

To solve the problem proposed, I implemented three methods:

>Nearest Neighbor interpolation (i.e. no interpolation at all - pick the closest point).

>3D Kriging (attempting to fit a Variogram automatically).

>Natural Neighbour Interpolation.

My favorite is the Natural Neighbor Interpolator, which gives gives good results for almost all input data (with very little user interaction). The problem is that the implementation is difficult, requiring the generation of a 3D Delaunay Mesh, and then extracting the Voronoi Cells/volumes from the mesh.

My implementation is reasonably fast (will interpolate around 1e6 points in 8 minutes; for pointsets of around 1e4 points). It performs very well asymptotically, but has high constant factors involved (so it should extend to very large point sets, but be prepared to wait!).

The implementations of all three are available on Google Code, and probably through my uni webspace (if it's online) to be used for all non-profit reasons etc. etc. - but please contact me if you use any of it! :)

Natural Neighbour Interpolation in 3D. (http://code.google.com/p/interpolate3d/)

Other methods. (http://www.cs.bris.ac.uk/home/rh7223/)

I had thought of a possible brute force method. Given set N of 3D P values spaced irregularly on 3D X,Y,Z grid surface and a set M of 3D X,Y,Z values that will map congruently onto N but at possibly different grid locating points on the surface. What is sought is 'best' method to map P on N, into new P' on M. Possible solution (N by M) is to determine the nearest neighbors for every M by calulating distance of every point in N. Do a sort on resulting array for each point finding the three shortest distance. If shortest distance is zero then use P from N(X,Y,Z) else take three points and make simple equation of a plane and map local P on plane. Take M(X,Y,Z) and calculate P'. If computation becomes burdensome then initial simple sorting of N can be used to reduce the number of distances used to a subset of N. Any thoughts on using this?