Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
The end of your question looks cut off. –  Mario Carneiro Dec 19 '12 at 9:59
    
@Mario: Thanks, I added the rest of it. –  user53681 Dec 19 '12 at 10:18
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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