[SciPy-User] ND interpolation with Qhull

[Wolfgang Kerzendorf]

Dear all,

I'm interested in learning  how the LinearNDInterpolator actually works. 
So I read up on qhull, convex hulls and delauney triangulation:
I understand that one can use qhull to construct the convex hull in a 
d-dimensional space.
If I want the delauney triangulation of n points in d dimensions I just 
need to project these points on a paraboloid in d+1 dimensional space 
build the convex hull and reproject this onto d-dimensions.
So now that I have the triangles I just need to find the triangle 
containing the point to be interpolated. And that is where I'm a little 
bit unclear: How do I find the point?

I know that in the barycentric coordinate system I have three 
coefficents and if the sum of two of them is less than 1 to reproduce my 
point, then I found my triangle. But this requires me to go through all 
triangles. I'm sure there is a faster way (which is probably used by scipy).

Once I have the triangle I just determine the two coefficients (in two 
dimensions) and add the vectors up to get the interpolation?

Help is much appreciated
     Wolfgang