根据每个点的最近邻距离在最佳网格上插入非结构化 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

nearest-neighbor

scipy

spatial-interpolation