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$ Dec 19, 2012 at 9:59
  • $\begingroup$ @Mario: Thanks, I added the rest of it. $\endgroup$
    – user53681
    Dec 19, 2012 at 10:18

1 Answer 1


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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .