我正在实现一个碰撞检测算法,存储单个八叉树节点中所有对象之间的距离。例如,如果节点中有4个对象,则对象1和2,1和3,1和4,2和3,2和4以及3和4之间存在距离。总对数的公式是t = n *(n-1)/ 2,其中t是对的总数,n是节点中对象的数量。
我的问题是,如何从列表中的位置转换为一对对象。例如,使用上面的对列表,3将返回对2和3。
为了节省内存空间,列表只是距离的浮点列表,而不是包含距离和指向2个对象的指针。
我不确定如何在数学上将单个列表索引转换为一对数字。任何帮助都会很棒。我希望能够将其分解为2个函数,第一个返回第一个对象,第二个返回第二个,两个函数都采用2个变量,一个是索引,另一个是整个对象。节点。如果可能的话,我想创建一个没有任何循环或具有递归函数的函数,因为这将为我的碰撞检测算法实时运行。
根据我对这个问题的理解,从索引(从0开始,在你的例子中为3)和对象数n(在你的例子中为4)中获得一对a&b(在你的例子中为1,2和3)的一种方法是:
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;
可以在Calculate Combination based on position和http://saliu.com/bbs/messages/348.html找到广义算法(对于元组而不是对),但它们似乎涉及在循环中计算组合。
编辑:一个更好的公式(来自同一来源):
a = n - floor(0.5 + sqrt(2 * (t - index)));
我建议使用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。
通常,对于a&b对,索引将是b(b-1)/ 2 + a。
int index_from_pair(int a, int b) {
return b*(b - 1)/2 + a;
}
将单个索引i转换回一对数字的一种方法是增加b直到b(b + 1)/ 2> i,即b的下一个值将导致索引大于i的情况。然后你可以找到a作为差异a = i-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 = i解释为二次方程式,您可以使用平方根求解。你需要的实际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;
}
}