計算每一組點之間的距離

Question

所以我正在模擬大量的n維粒子，我需要知道每對點之間的距離。考慮到一些錯誤，並且如果超過某個閾值，那麼距離是完全不相關的，那麼有沒有什麼好方法可以實現呢？我很確定如果我想要dist(A,C)並且已經知道dist(A,B)和dist(B,C)我可以將它綁定[dist(A,B)-dist(B,C) , dist(A,B)+dist(B,C)]，然後將結果存儲在排序數組中，但是如果有更好的東西，我不想重新發明輪子。

我不認爲維數應該大大影響邏輯，但也許對於某些解決方案來說。提前致謝。

Answer 1

如果超過某個閾值的距離不相關，並且此閾值不太大，則有一些常用技術可使此效率更高：使用空間分區數據結構限制搜索相鄰點。可能的選項有：

• 分檔。
• 樹木：quadtrees（2d），kd-trees。
• 與空間哈希分箱。

此外，由於從A點到B點的距離與從B點到A點的距離相同，因此只能計算一次該距離。因此，你應該使用下面的循環：

for point i from 0 to n-1: 
    for point j from i+1 to n: 
     distance(point i, point j) 

結合這兩種技術是N體模擬例如，當你有粒子相互影響，如果他們足夠接近非常普遍。下面是在2D一些有趣的例子：http://forum.openframeworks.cc/index.php?topic=2860.0

這裏的分級（和哈希）的解釋：http://www.cs.cornell.edu/~bindel/class/cs5220-f11/notes/spatial.pdf

Answer 2

如果問題只是有關計算所有對之間的距離，那麼這將是一個O(n^2)問題沒有任何更好的解決方案的機會。但是，您在說如果距離大於某個閾值D，那麼您對此不感興趣。這爲更好的算法提供了機會。

例如，在2D情況下，您可以使用掃描線技術。按照字典順序排列你的點，首先由y然後由x排序。然後用條紋掃描飛機，寬度爲D，從下到上。當條紋在飛機上移動時，新的點將通過其頂部邊緣進入條紋並通過其底部邊緣離開。活動點（即當前在條帶內的點）應該保存在一些按其x座標排序的增量可修改的線性數據結構中。

現在，每當一個新點進入條紋時，您都必須檢查左側和右側的當前活動點，而不是比D（沿着x軸測量）更遠。就這樣。

這個算法的目的（因爲它通常是與掃線方法的情況下）是從O(n^2)朝O(m)，其中m是交互的次數，我們真正感興趣的推動實踐的複雜性了。當然， ，最糟糕的表現將是O(n^2)。

以上適用於二維情況。對於n維情況，我會說你會用不同的技術更好。某種空間分區應該在這裏很好地工作，即利用這樣的事實：如果已知分區之間的距離大於D，則沒有理由考慮這些分區中的特定點相對於彼此。