python - 测量到最近的一组点的距离 - python

Question

我正在尝试测量每个点到最近的一组点的最短欧氏距离。使用下面，我在两个不同的时间点在 x,y 中显示了 6 个独特的点。我在 x_ref, y_ref 中记录了一个单独的 xy 点，我在其周围传递了一个半径。所以对于这个半径之外的每个点，我想找到到半径内任何点的最短距离。对于半径内的点，只需返回 0。

calculate_distances 测量每个特定点与其余点之间的距离。我希望将距离返回到半径内最近的点。

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
from scipy.spatial.distance import pdist, squareform

df = pd.DataFrame({        
    'Time' : [1,1,1,1,1,1,2,2,2,2,2,2],                               
    'Item' : ['A','B','C','D','E','F','A','B','C','D','E','F'],      
    'x' : [5,5,8,3,6,2,6,7,4,2,7,6],
    'y' : [-2,0,-2,0,0,4,-1,2,-3,4,-4,2],     
    'x_ref' : [4,4,4,4,4,4,4,4,4,4,4,4],
    'y_ref' : [-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2],                          
    })

# Determine square distance
square_dist = (df['x_ref'] - df['x']) ** 2 + (df['y_ref'] - df['y']) ** 2
              
# Return df of items within radius
inside_radius = df[square_dist <= 3 ** 2].copy()

def calculate_distances(df):

    id_distances = pd.DataFrame(
        squareform(pdist(df[['x','y']].to_numpy())),  
        columns = df['Item'],
        index = df['Item'],
    )

    return id_distances

df_distances = df.groupby(['Time']).apply(calculate_distances).reset_index()

预期输出:

    Time Item  x  y  x_ref  y_ref  distance
0      1    A  5 -2      3     -2  0.000000 # within radius 0
1      1    B  5  0      3     -2  0.000000 # within radius 0
2      1    C  8 -2      3     -2  2.828427 # nearest within radius is E
3      1    D  3  0      3     -2  0.000000 # within radius 0
4      1    E  6  0      3     -2  0.000000 # within radius 0
5      1    F  2  4      3     -2  4.123106 # nearest within radius is D
6      2    A  6 -1      4     -2  0.000000 # within radius 0
7      2    B  7  2      4     -2  3.162278 # nearest within radius is A
8      2    C  4 -3      4     -2  0.000000 # within radius 0
9      2    D  2  4      4     -2  6.403124 # nearest within radius is A
10     2    E  7 -4      4     -2  3.162278 # nearest within radius is C or A
11     2    F  6  2      4     -2  3.000000 # nearest within radius is A

Answer 1

这是一种使用scipy.spatial.KDTree的方法，这在您打算进行许多距离和邻居搜索时非常有用。

import numpy as np
import pandas as pd
from scipy.spatial import KDTree

def within_radius_dist(z, radius, closed=False):
    center = z[['x_ref', 'y_ref']].mean()  # they should all be same
    z = z[['x', 'y']]
    dist_ubound = radius * 1.0001 if closed else radius
    dist, idx = KDTree(z).query(
        center, k=None, distance_upper_bound=dist_ubound)
    if closed:
        idx = [i for d, i in zip(dist, idx) if d <= radius]
    if idx:
        within = z.iloc[idx]
        dist, _ = KDTree(within).query(z)
    else:
        dist = np.nan
    return pd.Series(dist, index=z.index)

应用程序(这里以你的df为例):

>>> df.assign(distance=df.groupby('Time', group_keys=False).apply(
...     within_radius_dist, radius=3, closed=True))
    Time Item  x  y  x_ref  y_ref  distance
0      1    A  5 -2      3     -2  0.000000
1      1    B  5  0      3     -2  0.000000
2      1    C  8 -2      3     -2  3.000000
3      1    D  3  0      3     -2  0.000000
4      1    E  6  0      3     -2  1.000000
5      1    F  2  4      3     -2  4.123106
6      2    A  6 -1      4     -2  0.000000
7      2    B  7  2      4     -2  3.162278
8      2    C  4 -3      4     -2  0.000000
9      2    D  2  4      4     -2  6.403124
10     2    E  7 -4      4     -2  3.162278
11     2    F  6  2      4     -2  3.000000

解释:

1. groupby('Time') 确保我们按时间将函数 within_radius_dist() 应用于每个组。
2. 在函数内部，第一个 KDTree 查询找到以 (x_ref, y_ref)。
3. 由于 distance_upper_bound 参数是独占的(即 KDTree 查询仅返回严格小于此的距离)，在我们想要的情况下在半径处包含点(当 closed=True 时)，那么我们需要做一些额外的处理:在半径上添加一小部分，然后裁剪。
4. 另请注意，默认情况下，使用 p=2 范数(欧几里德范数)，但您也可以使用其他范数。
5. within 是球体内的这些点。
6. (注意:如果没有这样的点，我们将对所有距离返回 NaN)。
7. 第二个 KDTree 查询查找我们所有的点(组内)到那些 within 点的最近距离。对于球体内的点(因为这是它们之间的距离)，这很方便地返回 0，对于其他点，返回到球内最近点的距离。这就是我们的结果。
8. 我们将结果作为 Series 返回，因此 pandas 知道如何正确地调整它的形状，最后将它分配给一个名为 'distance' 的列。

最后观察:原始问题中提供的预期结果似乎忽略了 x_ref, y_ref 并使用了单个 center=(4, -2)。在第一组(Time == 1)中，C 的正确距离是 3.0(到 A 的距离)，E 不在圆圈。

补充

如果您也有兴趣为每个点捕获哪个最近的邻居:

def within_radius_dist(z, radius, closed=False):
    center = z[['x_ref', 'y_ref']].mean()  # they should all be same
    z = z[['x', 'y']]
    dist_ubound = radius * 1.0001 if closed else radius
    dist, idx = KDTree(z).query(
        center, k=None, distance_upper_bound=dist_ubound)
    if closed:
        idx = [i for d, i in zip(dist, idx) if d <= radius]
    if idx:
        within = z.iloc[idx]
        dist, idx = KDTree(within).query(z)
        neigh_idx = within.index[idx]
    else:
        dist = np.nan
        neigh_idx = None
    return pd.DataFrame({'distance': dist, 'neighbor': neigh_idx}, index=z.index)

然后:

out = pd.concat([df, df.groupby('Time', group_keys=False).apply(
    within_radius_dist, radius=3, closed=True)], axis=1)
out.assign(neigh_item=out.loc[out.neighbor, 'Item'].values)

输出:

    Time Item  x  y  x_ref  y_ref  distance  neighbor neigh_item
0      1    A  5 -2      3     -2  0.000000         0          A
1      1    B  5  0      3     -2  0.000000         1          B
2      1    C  8 -2      3     -2  3.000000         0          A
3      1    D  3  0      3     -2  0.000000         3          D
4      1    E  6  0      3     -2  1.000000         1          B
5      1    F  2  4      3     -2  4.123106         3          D
6      2    A  6 -1      4     -2  0.000000         6          A
7      2    B  7  2      4     -2  3.162278         6          A
8      2    C  4 -3      4     -2  0.000000         8          C
9      2    D  2  4      4     -2  6.403124         6          A
10     2    E  7 -4      4     -2  3.162278         8          C
11     2    F  6  2      4     -2  3.000000         6          A