搜索相鄰點

我有一堆包含在三個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

回答

相關問題