MATLAB: Can querying “TriScatteredInterp” be as fast as “griddedInterpolant”

efficient interpolationgriddedinterpolanttriscatteredinterp

Hi, im wondering why querying the TriScatteredInterpolant is so much slower and so much more size dependent than griddedInterpolant. Is there a way to have the fast performance of the griddedinterpolant for scattered data interpolation?
For illustrative purpose consider this example, where i create a gridded and a scattered interpolant for a smaller grid and a larger grid
[x1 x2 x3]=ndgrid(1:30,1:30,1:30);
[y1 y2 y3]=ndgrid(1:100,1:100,1:100);
x4=(x1+x2+x3);
y4=(y1+y2+y3);
LLip1  = griddedInterpolant(x1,x2,x3,x4)  ;
LLip2  = griddedInterpolant(y1,y2,y3,y4)  ;
LLip4  = TriScatteredInterp(y1(:),y2(:),y3(:),y4(:))  ;
LLip3  = TriScatteredInterp(x1(:),x2(:),x3(:),x4(:))  ;
display('small gridded')
tic; for i=1:100; LLip(2.5,3.4,3.2); end; toc
display('large gridded')
tic; for i=1:100; LLip2(2.5,3.4,3.2); end; toc
display('small scattered')
tic; for i=1:100; LLip3(2.5,3.4,3.2); end; toc
display('large scattered')
tic; for i=1:100; LLip4(2.5,3.4,3.2); end; toc
Output (matlab 2012a64bit): small gridded Elapsed time is 0.002512 seconds. large gridded Elapsed time is 0.002306 seconds. small scattered Elapsed time is 0.281428 seconds. large scattered Elapsed time is 9.635930 seconds.
(In my application in fact, similaly to the example, my data is not properly scattered. It merely has ragged edges, like
3   2   1   NaN
2   1   NaN NaN
1   NaN NaN NaN
i thought about using the griddedinterpolant when possible and using the sctatteredInerpolant only for the edges, i.e. when the gridded would return NaN, but a fast triscatteredinterp would make things easier…)

Best Answer

Is there a way to have the fast performance of the griddedinterpolant for scattered data interpolation?
I doubt it. gridded interpolation is fundamentally easier because data neighbors that participate in interpolation at a given point are easy to find due to their plaid arrangement. Additionally, the interpolation operations are tensorially separable.
Conversely, with scattered interpolation, it's harder to figure out which neighbours should participate. E.g., TriScatteredInterp uses a Delaunay triangulation to determine this. Additionally, the interpolation is not tensorially separable in the scattered case.
Related Question