Screenshot instructions:
Windows
Mac
Red Hat Linux
Ubuntu
Click URL instructions:
Rightclick on ad, choose "Copy Link", then paste here →
(This may not be possible with some types of ads)
From: Robert Kern <robert.kern@gm...>  20090714 17:18:26

On 20090713 13:20, Robert Cimrman wrote: > Hi all, > > I would like to use griddata() to interpolate a function given at > specified points of a bunch of other points. While the method works > well, it slows down considerably as the number of points to interpolate > to increases. > > The dependence of time/(number of points) is nonlinear (see the > attachment)  it seems that while the Delaunay trinagulation itself is > fast, I wonder how to speedup the interpolation. The docstring says, > that it is based on "natural neighbor interpolation"  how are the > neighbors searched? Using the Delaunay triangulation. The "natural neighbors" of an interpolation point are those points participating in triangles in the Delaunay triangulation whose circumcircles include the interpolation point. The triangle that encloses the interpolation point is found by a standard walking procedure, then the neighboring triangles (natural or otherwise) are explored in a breadthfirst search around the starting triangle to find the natural neighbors. Unfortunately, griddata() uses the unstructuredinterpolationpoints API rather than the more efficient gridinterpolationpoints API. In the former, each interpolation point uses the lastfound enclosing triangle as the start of the walking search. This works well where adjacent interpolation points are close to each other. This is not the case at the ends of the grid rows. The latter API is smarter and starts a new row of the grid with the triangle from the triangle from the *start* of the previous row rather than the end. I suspect this is largely the cause of the poor performance. > Does it use the kdtrees like scipy.spatial? I have > a very good experience with scipy.spatial performance. > > Also, is there a way of reusing the triangulation when interpolating > several times using the same grid? One would construct a Triangulation() object with the (x,y) data points, get a new NNInterpolator() object using the .nn_interpolator(z) method for each new z data set, and then interpolate your grid on the NNInterpolator.  Robert Kern "I have come to believe that the whole world is an enigma, a harmless enigma that is made terrible by our own mad attempt to interpret it as though it had an underlying truth."  Umberto Eco 