# [SciPy-User] Interpolate based on three closest points

Tom Foutz tom.foutz@gmail....
Wed Apr 21 09:04:56 CDT 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
```