3

この質問で用語を誤って使用して申し訳ありませんが、基本的には、次のようにバイナリ インデックスを利用する QuadTree を作成することを検討しています。

ここに画像の説明を入力 ここに画像の説明を入力

上の 2 つの図でわかるように、各セルにバイナリ ID (例: 1010、1011) が与えられている場合、すべてのODDバイナリ インデックスが X オフセットを制御し、すべてのEVENバイナリ インデックスが Y オフセットを制御します。

たとえば、レベル 2グリッド (16 セル) の場合、1010 (セル #10) は4 番目と2 番目のインデックスに 1 があると言えます。したがって、これらは 2 つの Y オフセットを実行します。最初の '1###' (一番左側) は 1 セルの高さのオフセットを示し、2 番目の '##1#' はさらにセルの高さの 2 倍のオフセットを示します。

次のように:

// If Cell Height = 64pixels
  1### = 64 pixels
+ ##1# = 128 pixels
__________________
  1#1# = 192 pixels

X 軸にも同じことが適用できますが、代わりに奇数を使用するだけです (例: #1#1)。

ここで、QuadTree を初期化するときに、すべてのセルとすべての深さが使用された場合に含まれる可能性のある最大ノードの計算を開始しました。これを、 4 の各深さのべき乗の合計で計算しました。

_totalNodes =   0;

var t:int=0, tLen:int=_maxLevels;
for (; t<tLen; t++) {
    _totalNodes += Math.pow(4, t); //Adds 1, 4, 16, 64, 256, etc...
}

次に、ノードをインスタンス化し、長い配列に格納する別のループ ( 0 から _totalNodes まで繰り返す) を作成します。現在の反復整数を Nodeコンストラクターに渡し、それをindexとして格納します。

これまでのところ、インデックスの最上位ビットを把握することで、ノードが格納される深さ (別名:レベル) を判断できました。

public static function MSB( pValue:uint ):int {
    var bits:int =      0;

    while ( pValue >>= 1) {
        bits++;
    }

    return bits;
}

しかし今、インデックスをバイナリ形式から実際のセル X および Y 位置に変換する方法を見つけようとして立ち往生しています。上で述べたように、各セルの次元が見つかります。インデックス全体に対していくつかの論理演算を実行するだけの問題です（または「ビットコード」は、コードで参照する名前です）

論理演算 (バイナリ レベル) を使用してバイナリ インデックス値を X および Y 位置に変換する良い例を知っている場合は、ここにリンクまたは説明を投稿していただけますか?

ありがとう！

これは、私がこのアイデアを得たリファレンスです（注：異なるプログラミング言語）：

L. Spiro エンジン - http://lspiroengine.com/?p=530

しかし、私はその記事で使用されている言語に精通していないので、実際にそれに従って、簡単に ActionScript 3.0 に変換することはできません。

4

1 に答える 1

1

あなたの仕事は Hannan Samet によって説明されています。これは、最初にクワッドツリーを構築し、次に対応するモートン コードを各クワッド セルに割り当てることによって機能します。(ビットインターリーブコード)。
コードを取得したら、それをクワッド内のオブジェクトに割り当てます。その後、四分木を削除できます。次に、座標を対応するモートン コードに変換して検索し、モートン インデックスでビン検索を実行できます。モートン (z オーダーとも呼ばれます) の代わりに、ヒルベルトまたはグレイ コードを使用できます。

于 2013-04-13T03:03:36.920 に答える