在空間中找到比某個值更接近的點

在我開發的python應用程序中，我有一個3D點陣列（大小在2到100000之間），我必須找到距離每個點一定距離內的點其他（比如在兩個值之間，比如0.1和0.2）。我需要這個圖形應用程序，這個搜索應該是非常快的（對於10000點的樣本，約爲1/10秒）在空間中找到比某個值更接近的點

作爲第一個實驗，我嘗試使用scipy.spatial.KDTree.query_pairs實現，並且5000點的樣本需要5秒才能返回索引。你知道任何可能適用於這個特定案例的方法嗎？

更多關於應用程序A位：

這些點代表原子座標和距離搜索是非常有用的確定原子之間的鍵。債券不一定是固定的，但可能在每一步都會發生變化，例如氫鍵。

2013-03-20 pygabriel

您是否看到https://github.com/scipy/scipy/pull/262？看起來cKDTree要快得多，並且查詢對函數應該可以在SciPy的開發版本中使用。 – rici 2013-03-20 04:23:30

我沒有看到，謝謝你指出這一點！看來新版本的cKDTree對於我的目的來說足夠快，我可以嘗試在我的應用程序中支持... – pygabriel 2013-03-20 05:52:21

偉大的問題！這裏是我的建議：

用你的「epsilon」值0.1/0.2 /任意分隔每個座標，並將結果四捨五入爲整數。這將使用距離公式確定距離不再需要確定的點的「商空間」，而只需比較每個點的整數座標即可。如果所有座標都相同，那麼原始點就在彼此近似三倍epsilon的平方根之內（例如）。這個過程是O（n），需要0.001秒或更少。

（注：你會想增加原點與此劃分而產生，並四捨五入，這樣你就不會失去精確座標的另外三個整數。）

排序按數字順序點使用字典式規則並將座標中的三個整數視爲字母中的字母。這個過程是O（n * log（n）），並且當然應該少於你的1/10秒要求。

現在，您只需簡單地瀏覽這個排序列表，並將每個點的整數座標與前面和後面的點進行比較。如果所有的座標匹配，那麼兩個匹配點都可以移動到您的「保留」點列表中，其他所有座標點都可以標記爲「丟棄」。這是一個O（n）過程，應該花費很少的時間。

結果將成爲所有原始點的子集，其中只包含可能涉及任何債券的點，債券被定義爲與原始集合中的某個其他點相差大約小於等於ε。

這個過程在數學上並不準確，但我認爲它絕對快速並且適合您的目的。

2013-03-20 03:40:04

+1。好的解決方案我沒有看到它，然後鍵入我的帖子。我認爲我的方法是一樣的，但你更好地制定你的答案。 – 2013-03-20 03:53:13

謝謝！這種方法看起來很聰明！我試圖實現這一點，看看它在我的情況下是否正常工作。 – pygabriel 2013-03-20 05:50:06

我也發現了一個類似的方法來提及你也可以工作（在你點排序後，你可以檢查鄰居「單元格」中的鍵）http://en.wikipedia.org/wiki/ Cell_lists – pygabriel 2013-03-25 17:53:29

我想到的第一件事是：如果我們計算集合中每兩個原子之間的距離，它將是O（N^2）運算。它非常緩慢。如何引入具有某些單元大小的靜態正交網格（例如接近您感興趣的距離）然後確定屬於網格的每個單元的原子（它需要O（N）操作）在完成此過程之後，可以減少搜索鄰居的時間。

2013-03-20 03:47:58

回答