問題タブ [quadtree]

これは私が過去数時間考えていたものです。これはマインドエクササイズです。

だから私は今日の八分木が何であるかを学びました！とても興味深い！ボクセルに解決される八分木を実装する方法を考えてきました。

今、頭を抱えることができない最大の問題は、八分木の位置を参照することです。

免責事項：最初に、問題を視覚化するために2D平面で四分木を使用します。第二に、私はここで正しい専門用語を理解していません。親である八分木の細分化は「ブランチ」であり、子のみである細分化（この場合はボクセルに解決されます）は葉"。第三に、四分木の枝の各スペースに、左から右に上から下に番号を付けます{1,2,3,4}

16x16のユニットスペースを定義する四分木があるとしましょう。場所[16,16]にボクセルを保存しています。

ここで、位置[4,4]にボクセルを追加するとします。（注：ゼロから開始します）

ここで、ボクセルが格納されているかどうかを確認するために[16,8]をチェックしたいとします。前の方法を使用して、これらのブランチを技術的にトラバースします。

ただし、4-> 1にはデータが割り当てられていないため、空です。（使用されていないため、細分化されません）。

私の質問はこれになります、どうすれば四分木をすばやく横断してボクセルを見つけることができますか？

私の最初で最も簡単な方法は、上記で使用した形式でブランチを移動することです。

ここでの問題は、voxelArray [16] [16]、voxelArray [4] [4]、またはvoxelArray[16][8]の方がはるかに高速であるということです。はるかに大きな四分木（256x256）を使用すると、深さが増加します（4から8）。ネストされた配列はまだ2つのメモリ操作です。（クアッドツリーの場合、実際には、アクセサーのようなものを使用して、子が条件付きロジックで存在することを確認することに注意してください）

私の2番目の考えは、四分木をボクセル自体として保存することでした。たとえば、2x2の配列があるとすると、空の場合は次のようになります。

位置[1,1]にボクセルを追加すると、次のようになります。

四分木を保存すると、次のようになります。

これを4x4にして

データに直接アクセスできるようになりましたが、クアッドツリーのメモリのコンパクトさが失われ、多くのロジック操作を実行できます。IMOこれは、0の大きな領域と1の小さなグループがある場合にのみうまく機能します。

ボクセルをquadtree/octreeに格納することにより、すべてをループするときにパフォーマンスが向上しますが、直接アクセスするとパフォーマンスが低下します。

四分木をトラバースしたい場合、寸法は2 ^ nである必要がありますか？そうでない場合、それを等しいサブクアドラントに分割できない場合はどうなりますか？たとえば、データを含む5x6テーブル。

QuadTreeに2つのオブジェクトを追加しましたが、リスト全体でオブジェクトを探すと、1つのオブジェクトしか見つかりません。これはなぜですか、それを修正するために何ができますか？

オブジェクトを挿入すると印刷されます

platform.Platformsオブジェクト（0x0236F950）platform.Platformsオブジェクト（0x0236F950プラットフォーム）.Platformsオブジェクト（0x0236F950プラットフォーム）.Platformsオブジェクト（0x0236F950プラットフォーム）.Platformsオブジェクト（0x0236FAB0）platform.Platformsオブジェクト（0x0236FAB0）platform.Platformsオブジェクト（0x0236FAB0）platform.Platformsオブジェクト（0x0）

これは良いことですが、可変ツリーに2つの異なるオブジェクトが必要ですが、それを呼び出すと、リストの2番目のオブジェクトしかありません。

だから私は関数を作りました

印刷する

platform.Platformsオブジェクト（0x02320A70 rect（350、630、110、110）プラットフォーム）.Platformsオブジェクト（0x02320A70 rect（350、630、110、110）プラットフォーム）.Platformsオブジェクト（0x02320A70 rect（350、630、110、110）プラットフォーム）プラットフォームは0x02320A70rect（350、630、110、110）でオブジェクト化されます

私はグーグルとアマゾンを検索してきましたが、四分木ベースのLOD地形でまともなソースを見つけることができませんでした。大まかな概念を説明したばかりの人もいますが、これは私がすでに知っていることであり、いくつかのコメントを含む例です。

ウェーブレット パケットの分解に関する質問があります。

完全な (フル) ツリー (quad-tree) から最適なツリー (基底) を計算する必要があります。これは、MATLAB の関数besttreeによって実行できます。残念ながら、私のプログラムでは m ファイルを使用できません。

pythonでプログラムを書いていてpywtが気になったのですが、このモジュールにはベストツリーを計算する機能がありません。C++/C または python で計算された最良のツリー ウェーブレット パケット分解 (四分木) のモジュール、ライブラリ、またはいくつかの例はありますか? m ファイルを C++/C または python に変換する可能性はありますか?

KDTree のテンプレート化された実装を作成します。これは今のところ、BarnesHut 実装の Quadtree または Octree としてのみ機能するはずです。

ここで重要な点は設計です。ツリーが定義されている次元の数をテンプレート パラメーターとして指定し、いくつかの一般的なメソッドを宣言するだけで、自動的に正しい方法で動作します (テンプレートの特殊化が必要だと思います)。

2^2 (quadtree) または 2^3 (octree) ノードを持つために、テンプレートを特殊化したいと考えています。

誰かがいくつかのデザインのアイデアを持っていますか? 静的割り当てではなく動的メモリ割り当てを行うように制約されるため、継承を避けたいと思います。

ここで、N は 2 または 3 です

もう 1 つの問題は、quadtree には 4 つのノードがありますが 2 次元であり、octree には 8 つのノードがありますが 3 次元です。つまり、ノードの数は です2^dimension。これをテンプレート メタプログラミングで指定できますか? ループアンローラーが高速になるように、番号 4 と 8 を維持したいと思います。

ありがとうございました！

このウィキペディアの記事で説明されている手法を使用して四分木を構築しています。座標を 2 次元または 3 次元配列に格納しています。

Z オーダーで次のボックスの座標を計算するメソッドが必要です。デインターリーブよりも、ビットをインターリーブして 1 ずつ増やすことで機能しますが、これは非常に複雑になります。ビットをインターリーブせずに機能する記事の cmp_zorder(...) メトンに似た実装があることを願っています。

四分木の細分化で隣接するセルを見つける方法はありますか? 任意のレベルで選択したセルに隣接するすべてのセルを意味しますか?

チャンクされた QuadTree 地形を作成しており、2 つのノード間で詳細レベルの違いが 1 レベルを超えないようにしようとしています。コンストラクターの現在のコードは次のとおりです。

そして、それはうまくいきます。しかし、2 つの隣接ノード間の差を 1 レベル以下にするために、これをコンストラクターの最後に追加しようとしています。

しかし、そのスタックはオーバーフローします。私が考える理由の 1 つは、Children[iii] = new QuadNode(GetRect(iii), this, Root);ステートメントの代入部分が実行FindNeighbour()されず、子が適切な隣人を見つけるように設定する必要があるためです。しかし、コードが実際に2neighbour = FindNeighbour(direction);行目に到達することはなく、何が原因なのかわからないため、それが唯一の問題ではないと思います。

ツリーのベース作成後に新しい関数でその 2 番目のコード スニペットを実行すると、多かれ少なかれ機能しますが、新しく作成されたノード自体がレベル差 > 1 を作成しないようにするために複数のパスが必要です。可能であれば、コンストラクターにこのコードを含めることをお勧めします。誰でもこれを達成する方法を考えることができますか?

QuadrantNeedsChild(int quadrant)レベルが8を超えないようにするのに役立つ場合に備えて、クラスに関するいくつかのメモ。Subdivide()単純Children[iii] = new QuadNode(GetRect(iii), this, Root);にすべての象限で実行されます。FindNeighbour(int direction)親または祖先を返すことができます。たとえば、D が北隣を探している場合、B が次のように分割されていなければ、その祖父母 (ダイアグラム全体) を取得します。

サブディバイド機能は、範囲外のクアドラントが指定されている場合、特定のクアドラントまたはすべてのクアドラントをサブディバイドします。

コードに四分木に似た構造があり、gnuplotで視覚化したいと思います。これは、長方形のサブディビジョンを見たいことを意味します。これをgnuplotに入れたいのは、このアウトライン上に2次元関数をプロットして、細分割の量と関数値の相関関係を示したいからです。

ayoneはこれを行う方法についてのアイデアを持っていますか？