On 2009-07-14 12:52, Robert Cimrman wrote: > Robert Kern wrote: >> On 2009-07-13 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 speed-up 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 breadth-first >> search around the starting triangle to find the natural neighbors. > > I see, thanks for the explanation. The walking procedure is what is > described e.g. in [1], right? (summary; starting from a random triangle, > a line is made connecting that triangle with the interpolation point, > and triangles along that line are probed.) > > [1] http://www.geom.uiuc.edu/software/cglist/GeomDir/ptloc96.ps.gz
Yes. >>> Does it use the kd-trees 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. > > So if the above fails, I can bypass griddata() by using the delaunay > module directly, good. Yes. griddata is a fairly light wrapper that exists mainly to sanitize inputs and allow use of the natgrid implementation easily. -- 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 ------------------------------------------------------------------------------ Enter the BlackBerry Developer Challenge This is your chance to win up to $100,000 in prizes! For a limited time, vendors submitting new applications to BlackBerry App World(TM) will have the opportunity to enter the BlackBerry Developer Challenge. See full prize details at: http://p.sf.net/sfu/Challenge _______________________________________________ Matplotlib-users mailing list Matplotlib-users@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/matplotlib-users
