[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