有沒有一種有效的方法來確定距離？

這個問題更多的是關於算法和功能的正確使用，而不是實際的代碼。有沒有一種有效的方法來確定距離？

在我的代碼中，我使用map來模擬盒子。地圖元素由作爲鍵的vector<int>和作爲值的set<shared_ptr<foo> >組成。

我做一個嵌套循環去了所有的箱子：

mit1 = boxes.begin(); //mit1 is an appropriate iterator 
int edge = 10;//represnd periodic boundary conditions 
while (mit1 != boxes.end()){ 
    vector<t> = mit1->first; 
    mit2 = mit1++; 
    while (mit2 != boxes.end()){ 
    vector<int> u = (mit2++)->first; 
    bool good = true; 
    for (int i = 0; i < 3 && good; i++){ 
     u[i] = (int)fabs(u[i] - t[i]); 
     good = u[i] == 0 || u[i] == 1 || u[i] == edge; 
    } 
    if (!good) continue; 
    } 
}

我所關注的是整個循環嵌套還有for循環。你認爲用函數來計算所有相鄰的盒子會更有效嗎？你知道任何更好的方法來做循環測試嗎？

來源

2011-09-18 Yotam

肯定有一個更好的辦法！ – Arunmu

你想要計算什麼？你確定你沒有在mit2和u之間混淆（或換句話說 - 你在第二次沒有無限循環）？ – Ofir

謝謝，我已經改變了循環，現在應該沒問題了......我想消除所有情況，其中兩個盒子都是這樣，因此盒子內的粒子沒有機會互動。箱子的大小固定爲這樣的距離，但我剩下箱子的距離計算 – Yotam

與每次碰撞檢測相同的建議：使用一些算法或數據結構，允許您根據空間距離對環路的候選進行預過濾，並允許在O（n）中執行預過濾。想到四叉樹或粗粒度的空間映射。

編輯：爲了讓整個想法更清楚一點，請考慮以下算法：在3D空間中有N個粒子，並且想要找出哪個粒子比距離D更近。您可以構建一個3D陣列，每個倉代表您的目標空間的立方體積，並且每個體積的大小必須至少爲D.要查找所有可能比D更接近給定粒子X的粒子，請確定陣列單元格其中X是當前的Ax，並選擇Ax和周圍所有單元格中的所有粒子。你只需要檢查這個小子集的衝突。

當使用M個陣列單元時，整個距離檢查的平均計算複雜度現在是O（N * N/M）而不是O（N^2），然而以O（M^2 ）空間。

如果您的目標空間不受限制，請使用四叉樹（2D）或八叉樹（3D）。

來源

2011-09-18 13:20:01 thiton

這就是箱子在那裏的原因。每個盒子都包含粒子，盒子是過濾器。但是，我仍然想找到一種既易於理解又高效的方法... – Yotam

閱讀您的編輯......這正是我正在做的。唯一的區別是，音量正在變化，我不能簡單地創建一個表格，在那裏我寫下所有的音符對。此外，大部分數量都是空的，並且它不會有效地覆蓋所有的盒子... – Yotam

a）四/八叉樹對於這樣的空卷是非常好的。 b）與比較所有物體之間的距離相比，檢查26個空箱子是非常便宜的。 c）再次，隨着音量的變化，使用八叉樹來達到同樣的效果。 – thiton

取決於你的程序在做...

但它是可以計算的距離，當一個框移動。然後它優化一些如果不是所有的盒子都在移動。

來源

2011-09-18 13:15:50 Nir

這是一般碰撞/心智問題的簡化版本。當你有一堆物體時，這些問題會變得特別討厭，每個物體都被許多多邊形面所描述。沒有一個適合所有這些問題的解決方案。有很多啓發式方法可以幫助解決這個問題。其中幾個：

使用邊界球以及邊界框。一對球體之間的距離比一對球體之間的距離更容易計算，並且一對球體之間的距離不會超過一對邊界框之間的距離。這可以讓您快速排除大量計算。
使用對象的層次結構。如果對象A，B，C和D總是彼此靠近，創建一個包含A，B，C和D的元對象通常很有用。如果您可以排除將此元對象視爲候選對象，只是排除考慮任何內部對象作爲候選人。
如果物體移動緩慢，下一步最近的鄰居通常是當前步驟中最近的鄰居。從第一次猜測開始，然後搜索其他附近的物體，然後再向外走。最終（通常早於晚）你將排除所有剩餘的物體。

來源

2011-09-18 14:25:40

有沒有一種有效的方法來確定距離？

回答

相關問題