python - numpy-2d 中接近点的快速融合(矢量化)

Question

我有一个类似于此处提出的问题的问题: simple way of fusing a few close points .我想用坐标的平均值替换彼此靠近的点。单元格中的接近度由用户指定(我说的是欧氏距离)。

就我而言，我有很多积分(大约 100 万)。此方法有效，但很耗时，因为它使用双 for 循环。

有没有更快的方法来检测和融合 numpy 二维数组中的接近点？

---

为了完整，我添加了一个示例:

points=array([[  382.49056159,   640.1731949 ],
   [  496.44669161,   655.8583119 ],
   [ 1255.64762859,   672.99699399],
   [ 1070.16520917,   688.33538171],
   [  318.89390168,   718.05989421],
   [  259.7106383 ,   822.2       ],
   [  141.52574427,    28.68594436],
   [ 1061.13573287,    28.7094536 ],
   [  820.57417943,    84.27702407],
   [  806.71416007,   108.50307828]])

点的散点图如下所示。红色圆圈表示彼此靠近的点(在本例中，数组中最后两个点之间的距离为 27.91)。因此，如果用户指定最小距离为 30，则应融合这些点。

在 fuse 函数的输出中，最后一个 to 点被融合。这看起来像:

#output
array([[  382.49056159,   640.1731949 ],
   [  496.44669161,   655.8583119 ],
   [ 1255.64762859,   672.99699399],
   [ 1070.16520917,   688.33538171],
   [  318.89390168,   718.05989421],
   [  259.7106383 ,   822.2       ],
   [  141.52574427,    28.68594436],
   [ 1061.13573287,    28.7094536 ],
   [  813.64416975,    96.390051175]])

Answer 1

如果你有大量的点，那么构建一个 k-D tree 可能会更快使用 scipy.spatial.KDTree ，然后向它查询比某个阈值更近的点对:

import numpy as np
from scipy.spatial import KDTree

tree = KDTree(points)
rows_to_fuse = tree.query_pairs(r=30)    

print(repr(rows_to_fuse))
# {(8, 9)}

print(repr(points[list(rows_to_fuse)]))
# array([[ 820.57417943,   84.27702407],
#        [ 806.71416007,  108.50307828]])

这种方法的主要优点是您不需要计算数据集中每对点之间的距离。