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

Question

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

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

我的最终目标是在网格上插入这些数据以转换为图像/矩阵。所以，我需要找到插入这些数据的“最佳网格”。而且，为此我需要找到该网格像素之间的最佳 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

您要解决的问题称为“所有最近邻问题”。例如，请参阅本文:http://link.springer.com/article/10.1007/BF02187718

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