How To Find Closest Point To Grid Values

I'm trying to interpolate the value of a function at a single point from it's nearest neighbors. I have f specified on a meshgrid, [x_grid,y_grid,z_grid] = np.meshgrid(x_range,y_ra

Solution 1:

To expand on the comments of @hpaulj and mine... The class you're looking for is scipy.interpolate.NearestNDInterpolator

This class is based on scipy's own scipy.spatial.cKDTree. The cKDTree class implements the k-dimensional space-partition tree, or "k-d tree" data structure, which trades construction time and space for fast search.

To use scipy.interpolate.NearestNDInterpolator, you initialise an instance like

from scipy.interpolate importNearestNDInterpolatorinterpolator= NearestNDInterpolator(your_points, your_values_on_the_points)

After creating interpolator, use it to evaluate the interpolant value at random_point by

interpolant = interpolator(random_point)

Once created, interpolator can be reused for different input points, which is a Good Thing (tm). You can also evaluate the interpolant value for multiple points by passing all of them into the call. [1]

If you look at the source, you'll discover how the interpolator is implemented using cKDTree.

[1] Actually there's a potential optimisation: if you need "vectorised" evaluation for many points, the underlying cKDTree's query() method supports parallelisation, done in native C code running in threads. Although scipy's own implementation of NearestNDInterpolator doesn't use this feature, probably catering to greatest common divisor, you can override this by making your own subclass that uses parallelisation with a suitable choice of n_jobs parameter.

Note: the really good thing about using a k-d tree based interpolator is that its application can be extended to a "grid" in arbitrary shape (not necessarily rectangular).

---

EDIT:

Oh, so you meant to use the nearest neighbors for linear interpolation?

Then very sorry, I misread your question!

But then, you have two choices.

1. If your grid is sufficiently regular, and its construction (starting value / ending value / step known to you in all dimensions), it is not hard to write a function findneighbor() that locates the neighbors given the query point's coordinates. Then you do the vanilla linear interpolation.

2. If your "grid" is not very regular, and you just have a lot of grind point coordinates (which may not lie on rectangular lattices), you can still use scipy.spatial.cKDTree to locate N nearest neighbors (possibly N = 1 + (dimension of the grid)). After that, you interpolate on that N points.