I have 2D matrix of size like 512x512 or so. I also have a set of points with coordinates within bounds of the mentioned matrix ([0..512,0..512] in this case then) and each such point stores a property value (e.g.temperature).
The points usually lie on a curve or form a line or circle, so they are neither randomly nor uniformly distributed over the area. Also, they have float coordinates but making them integer values would not be a problem.
What I would like to obtain is the full matrix with interpolated data.
I tried to use inverse distance weighting method and it worked quite good except the computation time for such a grid (512x512) and, say, 1000 point is too high (like 10 seconds, but i would like to find the solution within one or two seconds; I am using C++ if it matters).
So I was wondering if someone had similiar problem and how it was solved.
One solution which I have used to interpolate heights in a grid from a set of contour lines is to use heat diffusion. Consider a sheet of metal initially at temperature 0 and make your curves of constant temperature. Now simulate heat diffusion using Laplace's equation with a discrete formulation. This reduces to a huge linear system. The key to performance is to use a multiresolution approach.
One reference is
See http://cs.wheatonma.edu/~mgousie/research.html.