[SciPy-User] Interpolate based on three closest points

Anne Archibald peridot.faceted@gmail....
Wed Apr 21 09:40:58 CDT 2010

```On 21 April 2010 10:04, Tom Foutz <tom.foutz@gmail.com> wrote:
> 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.

For the first problem, scipy.spatial includes efficient
nearest-neighbour searching that is well-suited to your task (fixed
set of potential neighbours, many query points, short list of
neighbours for any query, low dimensionality). You may find, if it's
fast enough, you want to do smarter interpolation; a simple
distance-weighted average of the n nearest neighbours for some n might
be fine, or you might look at scipy's radial basis function
interpolation (though I don't know how well this handles large numbers
of points).

If you really want to construct a mesh, I'm not sure what to suggest,
particularly if you care about preserving the topology (connectedness
and holes) of the original object; you might look into algorithms used
in 3D scanning, where the problem of constructing a mesh from a cloud
of points is dealt with.

Anne

> -- Tom
> _______________________________________________
> SciPy-User mailing list
> SciPy-User@scipy.org
> http://mail.scipy.org/mailman/listinfo/scipy-user
>
>
```