我正在实现一个碰撞检测算法,将所有对象之间的距离存储在一个八叉树节点中。例如,如果节点中有 4 个对象,则对象 1&2、1&3、1&4、2&3、2&4 和 3&4 之间存在距离。总对数的公式为 t = n * (n-1)/2,其中 t 是总对数,n 是节点中的对象数。
我的问题是,如何将列表中的一个位置转换为一对对象。例如,使用上面的对列表,3 将返回对 2&3。
为了节省内存空间,该列表只是距离的 float 列表,而不是包含距离和指向 2 个对象的指针。
我不确定如何在数学上将单个列表索引转换为一对数字。任何帮助都会很棒。我希望能够将其分解为 2 个函数,第一个返回对中的第一个对象,第二个返回第二个,这两个函数都采用 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。
一般来说,对于一对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 是 float 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;
}
}
关于c++ - 非冗余对列表中的对象索引,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13599842/