1

これは簡単な質問のように思えるかもしれませんが、現時点で他に取れるルートはありません。不必要な詳細を省きますが、一般的な概念は次のとおりです。

含まれている 3 次元空間内にエンティティ (粒子と考えてください) のインスタンスが多数あります。初期インスタンスの数は、10 から 1000 の粒子で変化する可能性があり、それぞれが識別番号と独自の x、y、および z 座標で初期化されます。パーティクルは時間の経過とともに移動する可能性があるため、ここでの目標は、任意の 2 つのパーティクルが互いに事前に設定された近接距離内 (任意の方向) にあるかどうかをできるだけ早く確認できるようにすることです。私が考えることができる最も単純な、しかし残念ながら洗練されていない/遅い方法は、次のように for ループに埋め込まれています。

    for(int i = 0; i < upper; i++)
    {
        for(int j = 0; j < upper; j++)
        {
            //If within proximity
            if(sqrt( ((entity1.x[i] - entity2.x[j])*(entity1.x[i] - entity2.x[j])) + ((entity1.y[i] - entity2.y[j])*(entity1.y[i] - entity2.y[j])) + ((entity1.z[i] - entity2.z[j])*(entity1.z[i] - entity2.z[j])) ) <= proximity )
            {
                //Perform function
            }
        }
    }

これは私のコードの実際のループです。3 次元で距離式を利用して、距離が事前定義された近接度よりも小さいかどうかを確認しています。それらがその距離内にある場合、私は機能を実行します。現在、文字通り何もしない機能があるので、ループ自体のタイミングだけを監視でき、内部のアルゴリズムを気にする必要はありません。時間はシステムごとに異なることはわかっていますが、私のシステムは少なくとも平均以上であり、このループは完了するまでに約 5 秒かかり、上限は 100 ループに設定されています。これを行うためのより高速なアルゴリズムはありますか? それとも、このループでひどく非効率的なことをしていますか? これは早ければ早いほどよい。

助けてくれてありがとう、DevenJ

4

4 に答える 4

3

ここで触れておくべきことの 1 つは、速度が重要な場合は計算に平方根を使用しないことです。より良い方法は、近接値を二乗して平方根を取り除くことです。

また、計算を繰り返さないようにする必要があります。たとえば、以下のアプローチについて考えてみてください。

for(int i = 0; i < upper; i++)
{
    for(int j = 0; j < upper; j++)
    {
        if(i < j)
        {
            //do stuff
        }
    }
}

しかし、より高度なアルゴリズムの知識が必要ですが、バイナリ octree の方が優れたソリューションです。

于 2013-04-25T03:16:31.677 に答える
2

設定することで、ループ内で sqrt() を使用する必要をなくすことができます

proximity = proximity * proximity;

ループ前。

于 2013-04-25T03:13:24.823 に答える
1

正の値の場合、 の場合a <= b、a^2 <= b^2.

平方根演算では、2 つの値の間の順序が保持されます。したがって、ループの前に近接度を 2 乗して、2 乗した大きさに一致させます。

于 2013-04-25T03:15:39.600 に答える
1

空間を分割するデータ構造にエンティティを格納すると、近接領域を含むパーティションに含まれていない粒子を排除できます。これには、バイナリ スペース パーティショニング、四分木、および八分木が役立ちます。

于 2013-04-25T03:14:11.887 に答える