2
$\begingroup$

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.

  • 0
    @Mario: Thanks, I added the rest of it.2012-12-19

1 Answers 1

0

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.