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

Question

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

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

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

解释：

groupby('Time') 确保我们按时间将函数 within_radius_dist() 应用到每个组。
在函数内部，第一个 KDTree 查询找到以 (x_ref, y_ref).
由于 distance_upper_bound 参数是 独占的 （即 KDTree 查询 returns 仅距离严格小于此），在这种情况下如果我们想在半径处包含点（当 closed=True 时），那么我们需要做一些额外的处理：将一小部分添加到半径，然后裁剪。
另请注意，默认情况下，使用 p=2 范数（欧几里德范数），但您也可以使用其他范数。
within 是球体内的这些点。
（注意：如果没有这个点，我们对所有距离return NaN）。
第二个 KDTree 查询查找我们所有点（组内）与那些 within 点的最近距离。这方便地 returns 0 对于球体内的点（因为那是它们之间的距离）和其他点到球内最近点的距离。这就是我们的结果。
我们 return 结果为 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

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

measure distance to nearest group of points - python

python

pandas

spatial

kdtree