根据每个点的最近邻距离在最佳网格上插入非结构化 X、Y、Z 数据

Question

这个问题是在我使用的显示最终解决方案的答案之后编辑的

我有来自不同来源的非结构化二维数据集，例如：这些数据集是3numpy.ndarray（X、Y坐标和Z值）。

我的最终目标是将这些数据插入网格以转换为 image/matrix。所以，我需要找到 "best grid" 来插入这些数据。而且，为此我需要找到该网格像素之间的最佳 X 和 Y 步长。

根据点间欧氏距离确定步长：

使用每个点与其最近邻点之间的欧氏距离的平均值。

使用 scipy.spacial 中的 KDTree/cKDTree 构建 X、Y 数据树。
使用 query 方法和 k=2 获取距离（如果 k=1，距离仅为零，因为对每个点的查询找到了它自己）。



    # Generate KD Tree
    xy = np.c_[x, y]  # X,Y data converted for use with KDTree
    tree = scipy.spacial.cKDTree(xy)  # Create KDtree for X,Y coordinates.

    # Calculate step
    distances, points = tree.query(xy, k=2)  # Query distances for X,Y points
    distances = distances[:, 1:]  # Remove k=1 zero distances
    step = numpy.mean(distances)  # Result

性能调整：

使用 scipy.spatial.cKDTree 而不是 scipy.spatial.KDTree 因为它确实更快。
将 balanced_tree=False 与 scipy.spatial.cKDTree 结合使用：在我的情况下速度大大加快，但可能并非对所有数据都是如此。
使用 n_jobs=-1 和 cKDTree.query 以使用多线程。
将 p=1 与 cKDTree.query 结合使用以使用曼哈顿距离代替欧几里得距离 (p=2)：更快但可能不太准确。
仅查询点的随机子样本的距离：使用大型数据集可加快速度，但可能不太准确且可重复性较低。

网格上的插值点：

使用计算的步骤在网格上插入数据集点。



    # Generate grid
    def interval(axe):
        '''Return numpy.linspace Interval for specified axe'''
        cent = axe.min() + axe.ptp() / 2  # Interval center
        nbs = np.ceil(axe.ptp() / step)  # Number of step in interval
        hwid = nbs * step / 2  # Half interval width 
        return np.linspace(cent - hwid, cent + hwid, nbs)  # linspace

    xg, yg = np.meshgrid(interval(x), interval(y))  # Generate grid

    # Interpolate X,Y,Z datas on grid
    zg = scipy.interpolate.griddata((x, y), z, (xg, yg))

如果像素距离初始点太远，则设置 NaN：

将 NaN 设置为网格中距离初始 X、Y、Z 数据的点太远（距离 > 步长）的像素。使用之前生成的KDTree。



    # Calculate pixel to X,Y,Z data distances
    dist, _ = tree.query(np.c_[xg.ravel(), yg.ravel()])
    dist = dist.reshape(xg.shape)

    # Set NaN value for too far pixels
    zg[dist > step] = np.nan

Answer 1

我建议你选择 KDTree.query。

您正在搜索特征距离来缩放分箱：我建议您只取 点的随机子集 ，并使用 Manhattan distance，因为 KDTree.query 非常慢（但它是 n*log(n) 复杂度）。

这是我的代码：

# CreateTree
tree=scipy.spatial.KDTree(numpy.array(points)) # better give it a copy?
# Create random subsample of points
n_repr=1000
shuffled_points=numpy.array(points)
numpy.random.shuffle(shuffled_points)
shuffled_points=shuffled_points[:n_repr]
# Query the tree
(dists,points)=tree.query(shuffled_points,k=2,p=1)
# Get _extimate_ of average distance:
avg_dists=numpy.average(dists)
print('average distance Manhattan with nearest neighbour is:',avg_dists)

我建议您使用曼哈顿距离 (https://en.wikipedia.org/wiki/Taxicab_geometry)，因为它的计算速度比欧氏距离快。并且由于您只需要平均距离的估算器就足够了。

Answer 2

您要解决的问题叫做"all-nearest-neighbors problem"。例如，参见这篇文章：http://link.springer.com/article/10.1007/BF02187718

我相信这个问题的解决方案是 O(N log N)，因此与 KDTree.query 的顺序相同，但实际上比一堆单独的查询快得多。抱歉，我不知道 python 的实现方式。

根据每个点的最近邻距离在最佳网格上插入非结构化 X、Y、Z 数据

Interpolate unstructured X,Y,Z data on best grid based on nearest neighbour distance for each points

python

numpy

scipy

nearest-neighbor

spatial-interpolation