How to find the closest point to grid values

Question

I am trying to interpolate the value of a function at one point from the nearest neighbors.

I set f to meshgrid, [x_grid,y_grid,z_grid] = np.meshgrid(x_range,y_range,z_range) , for which I would like to find the approximate value of the random point p_rand = (x_rand, y_rand, z_rand) . What is an efficient way to find indices of the nearest grid points and interpolate its value? This is in 3D - the nearest cube or tetrahedron of points will be fine.

Answer 1

To expand on the comments of @hpaulj and my ... The class you are looking for is scipy.interpolate.NearestNDInterpolator

This class is based on scipy own scipy.spatial.cKDTree . The cKDTree class implements a k-dimensional spatial partition tree or the "kd tree" data structure, which trades time and construction space for quick searches.

To use scipy.interpolate.NearestNDInterpolator , you initialize an instance of type

 from scipy.interpolate import NearestNDInterpolator interpolator = NearestNDInterpolator(your_points, your_values_on_the_points) 

After creating the interpolator use it to estimate the interpolation value in random_point on

 interpolant = interpolator(random_point) 

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

If you look at the source , you will learn how the interpolator is implemented using cKDTree .

[1] Actually, there is a potential optimization: if you need a "vector" estimate for many points, the basic cKDTree query() method supports parallelization executed in native C code running in threads. Although scipy own implementation of NearestNDInterpolator does not use this function, perhaps serving the largest common factor, you can override this by creating your own subclass that uses parallelization with the appropriate choice of the n_jobs parameter.

Note: A very good idea about using the kd tree-based interpolator is that its application can be expanded to a “grid” in any shape (not necessarily rectangular).

---

EDIT

So you wanted to use the nearest neighbors for linear interpolation?

Then it is a pity, I read your question incorrectly !

But then you have two options.

• If your grid is regular enough and its construction (initial value / final value / step, known to you in all dimensions), it is easy to write the findneighbor() function, which finds point neighbors by query. Then you perform linear vanilla interpolation.

• If your "grid" is not very correct, and you just have a lot of coordinate coordinates (which may not lie on rectangular grids), you can use scipy.spatial.cKDTree to search for N nearest neighbors (perhaps N = 1 + (dimension of the grid) ). After that, you interpolate N to this point.