1

衝突検出アルゴリズムを実装して、すべてのオブジェクト間の距離を単一の octree ノードに格納します。たとえば、ノードに 4 つのオブジェクトがある場合、オブジェクト 1&2、1&3、1&4、2&3、2&4、3&4 の間に距離があります。ペアの総数の式は、t = n * (n-1) / 2 です。ここで、t はペアの総数、n はノード内のオブジェクトの数です。

私の質問は、リスト内の位置からオブジェクトのペアにどのように変換するかです。たとえば、上記のペアのリストを使用すると、3 はペア 2&3 を返します。

メモリのスペースを節約するために、リストは、距離と 2 つのオブジェクトへのポインタを含む代わりに、距離を表す float のリストにすぎません。

単一のリスト インデックスを数値のペアに数学的に変換する方法がわかりません。どんな助けでも素晴らしいでしょう。これを 2 つの関数に分割できるようにしたいと考えています。最初の関数はペアの最初のオブジェクトを返し、2 番目の関数は 2 番目のオブジェクトを返します。どちらの関数も 2 つの変数を取り、1 つはインデックスで、もう 1 つはオブジェクトの合計です。ノード。可能であれば、ループや再帰関数を使用せずに関数を作成したいと考えています。これは、衝突検出アルゴリズムのためにリアルタイムで実行されるためです。

4

2 に答える 2

2

質問の私の理解に基づいて、インデックス（例では0ベース、例では3）とオブジェクトの数n（例では4）からペアa&b（例では1ベース、例では2と3）を取得する1つの方法は：

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)));
于 2012-11-28T08:43:23.533 に答える