最近邻搜索：Python的

我有一个2维阵列：最近邻搜索：Python的

MyArray = array([6588252.24, 1933573.3, 212.79, 0, 0], 
       [6588253.79, 1933602.89, 212.66, 0, 0], 
       etc...)

前两个元素MyArray[0]和MyArray[1]是点的X和ÿ坐标。

对于数组中的每一个元素，我想找到最快方式在X单位半径返回其单近邻。我们假设这是2D空间。

让我们举这个例子X = 6。

我已经通过比较每个元素与其他元素来解决了这个问题，但是当列表长度为22k时，这需要15分钟左右。我们希望最终能在约3000万分的名单上运行。

我已经阅读了有关K-d树的知识并理解了基本概念，但是很难理解如何编写它们。

来源

2012-10-16 Dlinet

什么是“Kt树”？你的意思是“k-d树”？对于二维点，您只需要[四叉树]（http://en.wikipedia.org/wiki/Quadtree）。有一个早期的问题寻找Python中的四叉树实现：http://stackoverflow.com/questions/6060302/pure-python-quadtree-implementation –

谢谢！我的意思是一棵K-D树。我会查找一个四叉树。 – Dlinet

['scipy.spatial']（http://docs.scipy.org/doc/scipy/reference/spatial.html）模块中有k-d树实现 –

感谢John Vinyard建议scipy。一些很好的研究和测试后，这里是解决这个问题：

先决条件：安装numpy的和SciPy的

导入SciPy的和numpy的模块

制作的5人副本二维数组包括只是的X和Y值。内6个单位作为这样

YourTreeName = scipy.spatial.cKDTree(YourArray, leafsize=100) 
#Play with the leafsize to get the fastest result for your dataset

查询的cKDTree为最近邻：每个项目在YourArray

for item in YourArray: 
    TheResult = YourTreeName.query(item, k=1, distance_upper_bound=6)

，TheResult将

创建cKDTree的实例作为这样是两点之间距离的元组，以及点的位置索引YourArray。

希望这可以帮助任何与KD树混淆的人！

来源

2012-10-26 00:07:55 Dlinet

从最近的某一点开始，而不是一个集合呢？ –

@SteveYeago [query_ball_point]（http://docs.scipy.org/doc/scipy-0.15.1/reference/generated/scipy.spatial.cKDTree.query_ball_point.html#scipy.spatial.cKDTree.query_ball_point）似乎是可用于此。 – ldavid

最近邻搜索：Python的

回答

相关问题