For a given 2D surface, I have some points, and I need to interpolate others. For example, in the following picture we have points (x,y,z), where z is represented with the colors you see.
The dots are the known points (where we know their x, y and z values). The ? represents any given point we want to interpolate (because we don't know their z).
For the ? point we know its (x,y) obviously, but we don't know z which needs to be interpolated.
Problem: What is the best way of interpolating a z for point ? from the surrounding points?
There are plenty of methods to interpolate the z value. One of the simplest is the interpolation using k nearest neighbors. For instance find the 3 neirest neighbors of the ? and then calculate the z values according to the z values of its neighbors. To be more specific z value is calculating using a weighted average of the neighbors, the further the neighbor is the smaller the weight. For implementation details check methods bilinear interpolation
I suggest you using the bilinear method since it might be slightly more difficult to implement but results in higher quality image.