指標的非冗餘對

Question

我實現碰撞檢測算法存儲所有物體之間的距離在一個單一的八叉樹節點的列表。例如，如果有在節點4個目的，是1 & 3,1 & 4,2 & 3,2 & 4和3 & 4.對象1 & 2之間的距離，對總數的公式T = N *（N-1）/ 2，其中t是巴黎的總數，n是在一個節點中的對象的數量。

我的問題是，我如何從列表中的位置轉換爲一對對象。例如，使用上面的對列表，3將返回對2 & 3.

爲了節省內存中的空間，列表只是一個距離浮點數列表，而不是包含距離和指向2個對象的指針。

我不確定如何將單一列表索引數學轉換爲一對數字。任何幫助都會很棒。我希望能夠打破這種降到2個函數，第一個返回所述對中的第一對象和所述第二返回第二，兩者的功能取2個變量，一個是索引，而另一個是在總的對象節點。如果可能的話，我想創建一個沒有任何循環或遞歸函數的函數，因爲這將對我的碰撞檢測算法實時運行。

Answer 1

根據我的問題的理解，一個辦法讓一對& B（1型，2 & 3在你的榜樣）從索引（從0開始，在實施例3）和對象的數目n（在實施例4）是：

t = n * (n - 1)/2; 
a = n - floor((1 + sqrt(1 + 8 * (t - index - 1)))/2); 
b = index + (n - a) * (n - a + 1)/2 - t + a + 1; 

一些信用http://oeis.org/A002024

可以在Calculate Combination based on position和http://saliu.com/bbs/messages/348.html找到廣義算法（用於元組而非成對），但它們似乎涉及在循環中計算組合。

編輯：了一個更好的公式（來自同一來源）：

a = n - floor(0.5 + sqrt(2 * (t - index))); 

Answer 2

更好訂貨

我建議使用colexicographical order，在這種情況下，你不會有供應對象的總數。訂購您對這樣的：

0: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: … 
0&1, 0&2, 1&2, 0&3, 1&3, 2&3, 0&4, 1&4, 2&4, 3&4, 0&5, 1&5, 2&5, 3&5, … 

你已經能夠這個名單擴大到無限長，這樣你就可以知道任一對指數不知道的項目數。這樣做，當你添加新的項目，你的數據結構，你只需要添加到您的陣列，而不是重新定位現有項目的效益。我已經調整的指數，以從零開始，當你標記你的問題C++，所以我假設你將使用從零開始的索引。我所有的答案都假設了這個順序。

您也可以可視化的colex排序是這樣的：

a: 0 1 2 3 4 5 … 
b: 
1 0 
2 1 2  index of 
3 3 4 5  a&b 
4 6 7 8 9 
5 10 11 12 13 14 
6 15 16 17 18 19 20 
⋮ ⋮     ⋱ 

對單指數

讓我們首先把一對成一個單一的指標。訣竅是，對於每一對，你看第二個位置，並想象在該位置具有較少數字的所有對。因此，例如，對於2&4對，您首先計算第二個數小於4的所有對。這是從一組4個（即數字0到3）中選擇兩個項的可能方式的數量，所以您可以將其表示爲二項式係數4C2。如果你評估它，你會得到4（4-1）/ 2 = 6。要添加第一個數字，因爲這是索引較低但第二個數字相同的對的數目。對於2&4這是2，因此2&4的總體索引是4（4-1）/ 2 + 2 = 8。

一般來說，對於一對一個 & b索引將是 b（ b -1）/ 2 + 一個。

int index_from_pair(int a, int b) { 
    return b*(b - 1)/2 + a; 
} 

單指數配對

一種方式把單個索引我回一對數字將增加 b直到 b（ b +1）/ 2 >我，即，情況會導致指數比我較大的 b下一個值。然後，你可以找到一個作爲差一個 = 我 - b（ b -1）/ 2。通過遞增 b這種方法一次涉及使用循環。

pair<int, int> pair_from_index(int i) { 
    int a, b; 
    for (b = 0; b*(b + 1)/2 <= i; ++b) 
    /* empty loop body */; 
    a = i - b*(b - 1)/2; 
    return make_pair(a, b); 
} 

你也可以解釋 b（ b -1）/ 2 = 我作爲二次方程，它可以解決使用平方根。你需要的是真實的 b浮點數 b你會得到這個二次方程的正解。由於此方法中由於舍入誤差可能會遇到問題，因此您可能需要檢查是否存在 b（ b +1）/ 2> i。如果不是這種情況，就像在循環方法中那樣增加 b。一旦你有 b， a的計算保持不變。

pair<int, int> pair_from_index(int i) { 
    int b = (int)floor((sqrt(8*i + 1) + 1)*0.5); 
    if (b*(b + 1)/2 <= i) ++b; // handle possible rounding error 
    int a = i - b*(b - 1)/2; 
    return make_pair(a, b); 
} 

順序存取

請注意，您只需要打開指數回對隨機訪問到您的列表。在遍歷所有對時，一組嵌套循環更容易。因此，而不是

for (int = 0; i < n*(n - 1)/2; ++i) { 
    pair<int, int> ab = pair_from_index(i); 
    int a = ab.first, b = ab.second; 
    // do stuff 
} 

你最好是寫

for (int i = 0, b = 1; b != n; ++b) { 
    for (int a = 0; a != b; ++a) { 
    // do stuff 
    ++i; 
    } 
}