查找圍繞任意座標的半徑爲r的球體中的所有點

我正在尋找一種有效的算法，該算法針對已知高度，寬度和長度的空間，給定固定半徑R和點N的列表，在該空間中的三維座標將找到網格上任意點的固定半徑R內的所有點。這個查詢將用不同的點完成很多次，所以一個昂貴的預處理/排序步驟，以換取快速查詢可能是值得的。這是一個位應用程序的瓶頸工序的我的工作，所以任何時候我可以切斷它是有用的查找圍繞任意座標的半徑爲r的球體中的所有點

事情到目前爲止，我曾嘗試：

-The天真的算法，迭代所有點和計算距離

- 將空間劃分爲長度爲R的立方體的網格，並將這些點放入這些點。這樣，對於每個點，我只需要查詢直接相鄰的桶。這有一個顯着的加速

- 我試過使用曼哈頓距離作爲啓發式。也就是說，在桶內，在計算到任意點的距離之前，使用曼哈頓距離過濾那些不可能在半徑R範圍內的值（即曼哈頓距離爲< = sqrt（3）* R ）。我認爲這會提供一個加速，因爲它只需要加法而不是乘法，但它實際上減慢了程序的一點點

編輯：爲了比較距離，我使用平方距離來消除必須使用sqrt函數。

顯然，我可以加快這個速度有一些限制，但我現在可以嘗試使用任何建議。

不，它可能事項算法的水平，但我在C.

來源

2012-06-15 gms7777

'的sqrt（）'是一個昂貴的功能。加快你的速度，你應該只是對另一邊進行比較。 – corn3lius

我已經這樣做了。將編輯問題反映，謝謝。 – gms7777

我發現難以解析的問題陳述。你是否試圖在任意點的R中找到點的子集（在你稱爲N的列表中）？什麼是「元素」 - 來自N的點？ –

您可以通過以三維存儲您的積分在k-d tree中獲得速度優勢。這會讓你搜索O（log n）分期付款的時間。

來源

2012-06-15 15:37:19

kdtree球查詢需要O（n ^（1-1/d）），而不是O（log（n））。 – Mikola

工作不要半徑相比，在半徑的平方進行比較。原因是，如果兩點之間的距離小於R，則距離的平方小於R^2。

這樣，當你使用距離公式時，你不需要計算平方根，這是一個非常昂貴的操作。

來源

2012-06-15 15:35:10 tskuzzy

我會建議您使用K-d樹或Z形曲線： http://en.wikipedia.org/wiki/Z-order_%28curve%29

來源

2012-06-15 15:37:46

如何Binary Indexed Tree？（參考Topcoder教程）它可以擴展到n維，並且代碼更簡單。

來源

2012-06-15 16:22:08 Arvind

[我可能會誤解這個問題。我發現難以解析的問題陳述。]

在過去，設計這種類型的算法通常是很好的做法，用「早期出貨」進行測試以避免更昂貴的計算。在現代處理器中，分支預測的失敗通常非常昂貴，而那些早期測試實際上可能比完整計算更昂貴。（確切知道的唯一方法就是衡量。）

在這種情況下，計算是非常簡單的，所以它可能最好避免建立一個數據結構或做任何聰明的早期輸出的檢查，而是嘗試優化，矢量化和並行化獲得的吞吐量你需要。

對於點P（X，Y，Z）和一個球體S（X_S，Y_S，z_s，半徑），所述成員資格測試：

(x - x_s)^2 + (x - y_s)^2 + (z - z_s)^2 < radius^2

其中radius^2可以針對預先計算一次查詢中的所有點（避免任何平方根計算）。這些計算都是獨立的，您可以並行計算多個點。有了像SSE這樣的東西，你可以一次做四個。如果您有很多要測試的要點，您可以拆分列表並進一步將工作並行化到多個核心。

來源

2012-06-15 17:53:09

這當然有效。這就是我所說的樸素算法。我敢肯定，如果我只做1個查詢，那將是最快的。我遇到的問題是我正在做10k-100k查詢超過100k-1m點。即使在儘可能並行的情況下，這也會變成非常昂貴的一步。因此，如果有一種數據結構可以加快個別查詢速度，那麼即使最初的構建成本高昂，它也可能會更快。 – gms7777

我明白了。我對這個問題感到困惑。我認爲從查詢到查詢的點數是不一樣的。感謝澄清。 –

Nicolas Brodu's NEIGHAND庫完全符合您的要求，改進了bin-lattice算法。

更多細節可以在他的文章中找到：Query Sphere Indexing for Neighborhood Requests

來源

2012-06-29 13:34:52 Gigi

查找圍繞任意座標的半徑爲r的球體中的所有點

回答

相關問題