搜索相邻点

我有一堆包含在三个numpy阵列坐标：xarr，yarr和zarr（对应每个阵列中的位置属于相同的点 - 即第一点是在xarr[0]，yarr[0]，zarr[0]）。在P(x,y,z)的空间给定另一点，我想找到距离r的P(x,y,z)内的所有点。搜索相邻点

我这样做的方法是简单地遍历并计算到每个点的距离，看看它是否在的P(x,y,z)的之内。然而，我想使用SciPy的k-d树算法来做到这一点，但我并不确定如何开始实现它（我对Python很陌生）。我真的很感激，如果有人可以简要地概述一些代码，说明如何设置一个k-d树给我的格式的数据。

我知道SciPy documentation of its k-d tree implementation，我看过了，但我仍然对如何给予我已经（np.mgrid和ravel()被称为格式的数据创建树迷茫，我不明白为什么）。

谢谢！

来源

2016-05-03 billbert

如果我理解正确，你有一个* single * Nx3点的数组，并且对于该数组中的每个点，您想要计算其中某个半径范围内的其他点的数量？ –

@ali_m它们有3个独立的数组，每个坐标一个，他们想要在所描述的点中找到接近新点的点。 – gboffi

我不知道这是否对这个特定问题有用，我对kd树不是很大（尽管我可能应该），但是我发现这是一个有用的库：https：//networkx.github。 io/ –

省略进口的......我没有你的数据，所以我有伪造一些...

In [40]: x = np.random.random(100) 
In [41]: y = np.random.random(100)  
In [42]: z = np.random.random(100)  
In [43]: p = np.random.random(3)  
In [44]: p 
Out[44]: array([ 0.60515083, 0.39263392, 0.36129813])

即坐标三个阵列和一个点，我将搜索邻居。

接下来，我们来看看如何构造一个数组，其行数与不同的数据点和三个柱体一样多......

In [45]: np.vstack((x,y,z)).T.shape 
Out[45]: (100, 3)

好吧，它是正确的。

我们从scipy.spatial

In [46]: tree = KDTree(np.vstack((x,y,z)).T)

建立使用KDTree的kd树，然后我们用的树中，恰当地命名.query_ball_point()，其中一种方法找到点的指数接近p

In [47]: indices = tree.query_ball_point(p, 0.33)

其中我已经使用了任意半径等于1/3的半径。

最后，我们希望看到这些邻居，所以我会用树的.data属性和我刚刚计算这样

In [48]: tree.data[indices] 
Out[48]: 
array([[ 0.4117843 , 0.21440852, 0.3352732 ], 
     [ 0.48921727, 0.13855976, 0.43331816], 
     [ 0.71598133, 0.32270361, 0.20292187], 
     [ 0.71761991, 0.27309708, 0.12670474], 
     [ 0.6282775 , 0.13752325, 0.4143872 ], 
     [ 0.55995847, 0.31302848, 0.2780926 ], 
     [ 0.75896359, 0.16043536, 0.33530071], 
     [ 0.81138529, 0.64635994, 0.33819097], 
     [ 0.43537193, 0.5353203 , 0.52095431], 
     [ 0.66996807, 0.48346547, 0.52761835], 
     [ 0.69426851, 0.24725511, 0.57650329], 
     [ 0.5350322 , 0.23155768, 0.62545958], 
     [ 0.51228139, 0.38078056, 0.61246054]])

指数，这一切......

来源

2016-05-03 10:15:56 gboffi

这太棒了！非常感谢你，这正是我所期待的。 – billbert

这里是在SciPy的文档所提供的示例的解释：既然你已经有你的X，Y，Z坐标，你是

from scipy import spatial 
x, y = np.mgrid[0:4, 0:4]

np.mgrid从0到4创建一个网格X，Y要跳过这一步。

points = zip(x.ravel(), y.ravel()) 
points = zip(xarr.ravel(), yarr.ravel(), zarr.ravel()) #in your case 
points = zip(xarr, yarr, zarr) # if x,y,z are already 1-d

zip创建包含每个X，Y点对（准一起坐标为每个点）元组的列表。 ravel展平x，y网格网格（将n-d数组转换为1-d），以便可以使用zip。在你的情况下，如果xarr,yarr,zarr不是1-d，那么你将只使用ravel。

tree = spatial.KDTree(points)

创建索引点以提供快速邻居查找。

tree.query_ball_point([2, 0], 1)

内的点希望这有助于的[2,0]

r=1查找点。

来源

2016-05-03 09:30:12 SpicyBaguette

回答

相关问题