numpy-2d中的近点快速融合(没有for循环)

Question

我有一个问题类似于这里提出的问题: 融合几个关键点的简单方法.我想用它们的坐标平均值替换彼此靠近的点.细胞的接近程度由用户指定(我说的是欧几里德距离).

在我的情况下,我有很多积分(约100万).这种方法很有效,但是因为它使用了双循环,所以非常耗时.

是否有更快的方法来检测和融合numpy 2d阵列中的近点？

---

为了完整,我添加了一个例子:

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,则应融合这些点.

在熔丝功能的输出中,最后的点被融合.这看起来像:

#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树可能会更快scipy.spatial.cKDTree,然后查询它们比某个阈值更接近的点对:

import numpy as np
from scipy.spatial import cKDTree

tree = cKDTree(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]])

此方法的主要优点是您无需计算数据集中每对点之间的距离.