[SciPy-User] Interpolate based on three closest points

Tom Foutz tom.foutz at gmail.com
Wed Apr 21 10:04:56 EDT 2010


Hi everybody,
I have an irregular mesh of ~1e5 data points, with unreliable connection
data.  I am trying to interpolate based on these points.  My current method,
in pseudocode, is roughly the following:


> Matrix of data is a numpy array with X,Y,Z as columns



point of interest is x,y,z



Find distance from point of interest to all points by ~ numpy.sqrt((X-x)**2
> + (Y-y)**2 + (Z-z)**2)

tri=[]; area=[]

N=3

while True:

     for each triangle that can be made by N closest points:

        if triangle contains point of interest:

            area.append(area of triangle)

            tri.append(three triangle vertices)

     if tri: break

     N+=1



Do a linear interpolation based on triangle with smallest area


This method works great, but is super slow.  I do this for ~1e6 points.  I
was thinking there might be a faster way to find the closest points, perhaps
by doing some sort of binary tree structure?  Or perhaps I can build a
better mesh, and trace mesh connections to the closest points?

Any ideas would be appreciated.
-- Tom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.scipy.org/pipermail/scipy-user/attachments/20100421/3b807536/attachment.html>


More information about the SciPy-User mailing list