如何找到最接近网格值的点 [英] How to find closest point to grid values

问题描述

我正试图在距函数最近的邻居的一个点上插值一个函数.

我在网格[x_grid,y_grid,z_grid] = np.meshgrid(x_range,y_range,z_range)上指定了f，我想为其寻找随机点p_rand = (x_rand, y_rand, z_rand)的近似值.找到该最近的网格点的索引并对其值进行插值的有效方法是什么?以3D格式显示-最接近的立方体或四面体的点就可以了.

解决方案

要扩展@hpaulj和我的评论...您要查找的类是 scipy.spatial.cKDTree . cKDTree类实现 k维空间分区树或"kd树" "的数据结构，它需要花费构造时间和空间来进行快速搜索.

要使用scipy.interpolate.NearestNDInterpolator，请初始化一个实例，例如

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

创建interpolator后，用它来评估random_point处的内插值

interpolant = interpolator(random_point)

创建后，interpolator可以重新用于不同的输入点，这是一件好事(tm).您还可以通过将所有点传递到调用中来评估多个点的插值. [1]

如果您查看来源，您将发现如何使用cKDTree实现插值器.

[1]实际上存在潜在的优化:如果您需要对许多点进行向量化"评估，则底层cKDTree的query()方法

---

编辑:

哦，所以您打算使用最近邻居进行线性插值?

非常抱歉，我误解了您的问题！

但是，您有两种选择.

1. 如果网格足够规则，并且其构造(在所有维度上您都知道起始值/结束值/步骤)，则编写函数findneighbor()可以很容易地找到给定查询的邻居点的坐标.然后您进行香草线性插值.

2. 如果您的网格"不是很规则，并且您只有很多研磨点坐标(可能不位于矩形晶格上)，您仍然可以使用scipy.spatial.cKDTree来找到N最近的邻居(可能是N = 1 + (dimension of the grid)).之后，您在N点上进行插值.

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_range,z_range), for which I'd like to find an approximate value of a random point p_rand = (x_rand, y_rand, z_rand). What is an efficient way to find the indices of that nearest grid points and interpolate it's value? It's in 3D - nearest cube or tetrahedron of points would be fine.

解决方案

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 import NearestNDInterpolator
interpolator = 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.

这篇关于如何找到最接近网格值的点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！