Bicubic Interpolation for Non-regular grids?

Question

I am working on a project where I have a set of known measurements (x,y,z,a) and an input (z,a). I need to be able to interpolate the (x,y,z) so that I can get a list of possible (x,y) coordinates from a given z.

I was looking at bicubic interpolation, but I can only find examples pertaining to regular grids, and my (x,y) pairs are most certainly not regular.

Basically I am looking for some guidance on algorithms/models to achieve this goal. I am considering a triangulated irregular network, which is attractive because it breaks down into planes which are easy to determine the (x,y) from a given Z. But I would like a little more finesse.

I know it sounds like homework, its not.

Efficiency is not a concern.

Thanks!

Answer 1

I actually ended up using Delauney Triangulation to break down the fields into 3 dimensional X,Y,Z surfaces with an Identifier. Then given a set of (Identity,Z) pairs I form a field line from each surface, and from these lines compute the polygon formed from the shortest edges between lines. This gives me an area of potential x,y coordinates.

Answer 2

Take a look at Kd-tree. These first take a set of scattered points in 2d or 3d or 10d, then answers queries like "find the 3 points nearest P".

Are your queries z a pairs ? For example, given a bunch of colored pins on a map, a table of x y size color, one could put all the [x y] in a kd tree, then ask for pins near a given x0 y0.
Or, one could put all the [size color[ in a tree, then ask for pins with a similar size and color. (Note that most kd-tree implementations use the Euclidean metric, so sqrt( (size - size2)^2 + (color - color2)^2 ) should make sense.)

In Python, I highly recommend scipy.spatial.cKDTree.

See also SO questions/tagged/kdtree .