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.

  • $\begingroup$ The end of your question looks cut off. $\endgroup$ – Mario Carneiro Dec 19 '12 at 9:59
  • $\begingroup$ @Mario: Thanks, I added the rest of it. $\endgroup$ – user53681 Dec 19 '12 at 10:18

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

Gousie, M. B. Contours to Digital Elevation Models: Grid-Based Surface Reconstruction Methods. PhD thesis, Rensselaer Polytechnic Institute, 1998

See http://cs.wheatonma.edu/~mgousie/research.html.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.