問題タブ [quadtree]

紹介として、私は個人的な学習目的で基本的な Quadtree エンジンを作成しています。このエンジンには、さまざまな種類の形状 (現在は円と四角形を使用しています) を処理する機能を持たせたいと考えています。これらの形状はすべてウィンドウ内を移動し、衝突が発生したときに何らかのアクションを実行します。

これまでに持っている形状オブジェクトは次のとおりです。

ここで私の質問は、List<T> QObjectList = new List<T>();C# で一般的なリスト ( ) を作成して、異なるプロパティを持つ可能性のあるこれらのさまざまな形状をすべて含む 1 つのリストを作成する方法です (たとえば、QCircle には「radius」プロパティがあり、QSquare には「sideLength」プロパティがあります)。 )? 実装例も参考になります。

この質問にはばかばかしいほど明白な答えがあることは知っていますが、とにかく助けていただければ幸いです。私は C# に戻ろうとしています。明らかに久しぶり…

紹介として、私は個人的な学習目的で基本的な Quadtree エンジンを作成しています。このエンジンには、さまざまな種類の形状 (現在は円と四角形を使用しています) を処理する機能を持たせたいと考えています。これらの形状はすべてウィンドウ内を移動し、衝突が発生したときに何らかのアクションを実行します。

以前にジェネリック リストのトピックについて質問した後、ポリモーフィズムにインターフェイスを使用することにしました。これに最適なインターフェイスVector2は、クアッドツリーに表示されるすべてのオブジェクトが x、y 位置を持ち、Vector2それをうまくカバーするという事実のために利用するインターフェイスです。現在の私のコードは次のとおりです。

したがって、最終的には、汎用リストを使用できるようになり、コードまたはその行に沿って何かList<ISpatialNode> QObjectList = new List<ISpatialNode>();を使用して形状を追加できるように機能するインターフェイスが必要になります (私がしたいことを覚えておいてください)線に沿って後で別の形状を追加します)。QObjectList.Add(new QCircle(50, 400, 300, "Red"));QObjectList.Add(new QSquare(100, 400, 300, "Blue"));

問題は、ここから呼び出すと、このコードが機能しないように見えることです (Initialize()は XNA メソッドです)。

だから私の質問には2つの部分があります：

1.このコードを実行すると、my クラスとクラスのset { position = value; }一部でスタック オーバーフロー エラーが発生するのはなぜですか?QCircleQSquare

2.これは、ポリモーフィズムのためにインターフェースを利用する効率的/効果的な方法ですか?

まとめ：

本来よりも多くのメモリを消費するアプリケーションがあります (予想量の約 250%) が、メモリ リークを見つけることができないようです。同じ関数 (多くの割り当てを行う) を呼び出すと、メモリ使用量がある程度増加し続け、その後は変化せず、そこにとどまります。

プログラムの詳細:

アプリケーションは、四分木データ構造を使用して「ポイント」を保存します。メモリに格納するポイントの最大数 (キャッシュ サイズ) を指定することができます。「ポイント」は「PointBuckets」(クワッドツリーのリーフ ノードにリンクされたポイントの配列) に格納され、クワッドツリー内のポイントの最大総数に達すると、シリアル化されて一時ファイルに保存され、次のときに取得されます。必要です。これはすべてうまくいくようです。

ファイルが読み込まれると、新しい Quadtree が作成され、古いものが存在する場合は削除され、ファイルからポイントが読み取られ、Quadtree に 1 つずつ挿入されます。ノード分割などでバケットが作成および削除されると、大量のメモリ割り当てが発生します。

症状：

300MB のメモリを 1 回使用すると予想されるファイルをロードすると、予想される量のメモリが消費されます。すべて良い。同じファイルを何度もロードし続けると、メモリ使用量が増加し続けます (Linux の一番上の RES 列を見ています) 約 700MB まで増加します。これは、メモリ リークを示している可能性があります。ただし、ファイルをロードし続けると、メモリ消費量は 700MB のままです。

別のこと: valgrind massif を使用してメモリ使用量を確認すると、常に予想される制限内に収まっています。たとえば、キャッシュ サイズを 1.5 GB に指定してプログラムを単独で実行すると、最終的に 4 GB のメモリが消費されます。Massif で実行すると、常に 2GB 未満に留まり、生成されたグラフでは、実際には予想される 1.5GB を超えて割り当てられていないことがわかります。私の素朴な仮定は、massif が何らかの方法で断片化を防止するカスタム メモリ プールを使用するために発生するということです。

それで、ここで何が起こっていると思いますか？メモリの断片化である場合、この問題を解決するにはどのような解決策を探す必要がありますか?

衝突検出を大幅に高速化するために、2Dシミュレーションで四分木を実装する方法を探していましたが、その概念を理解するのは非常に難しいと思います。衝突検出が完全にすべてのパーティクルを不必要に通過し、単純に愚かであるため、160〜180のパーティクルを通過すると、非常に遅くなるため、シムはうまく機能します。今のところ、それは画面全体で互いに衝突している束または円であり、マウスをクリックしてドラッグすることで、新しい速度と場所で新しい円を生成することができます。

edit1：

さて、画像でわかるように、今はツリーを作成できたと思います

私の四分木画像：http：//i.stack.imgur.com/c4WNz.jpg

だから今の問題は、衝突検出にどのように役立つようにするかです...

チェックするたびにゼロからツリー全体を作成する必要がありますか？

私が待っている間に私がやろうとしていること、それが何らかの形で正しいことを願っています：P

1_各ノードにボールがあるかどうかを確認し、ボールがない場合はそのノードを除外します。2_葉のレベルに達するまで交差をチェックし続け、それらの交差するボールを葉のノードに追加します。3_続行する前にリーフノードでボールを衝突させますか？

これが私のQuadTreeNodeクラスです。

octree または quad を反復する方法を把握するのに苦労しています。そして、それは、私が反復のさまざまな神話を経験していないためかもしれません. しかし、float x,y,z; を保持する四分木を作成したとしましょう。ワードカラー。ここで、このノードは一度に 4 つの子しか生成できないとしましょう (そして、これらの子は両方とも 4 つの子を生成することができます)。兄弟/姉妹はできる)、作成された 4 つの子すべてが同じ dword カラーである (繰り返しますが、その場合、その兄弟/姉妹はまだ作成できます)、または作成されたノードの合計は 87380 です。容器。そして、プロセスは続きます。

現在、ノードを保持するこのコンテナーは (たとえば) 7 レベルの深さであり、子の子のすべての子はすべて異なる x、y、z、および色です。私が抱えている問題は、このコンテナをどのように反復処理するか、すべての子供、姉妹をどのように処理できるかということです。ルートは 4 つの子につながり、それらの 4 つの子には 4 つの子があるため、等々: 4^1+4^2....+4^7. 複雑な if ステートメントを記述したり、ノード全体を (ルートから開始して) 反復したりせずに、必要なノードを見つけるにはどうすればよいですか? コンテナー (ノードを生成するコンテナー) には、このプロセスを単純にするための追加のコードが必要ですか?

質問が一般的な場合は申し訳ありません。

ユーザーがサイズ1000x750のJFrameに頂点とエッジを描画できるようにするプログラムがあります。次に、単一の象限にある頂点の数に応じて、クアッドツリーを使用して入力グラフを分割する必要があります。誰かがこれを達成する方法について正しい方向に私を向けることができれば、私は本当に感謝しますか？

追加情報：ソース（頂点）、ターゲット（頂点）、および重みを格納するEdgeクラスがあります。name、x座標、y座標、およびEdge[]隣接リストを格納するVertexクラスがあります。また、エッジと頂点の2つのArrayListを格納するGraphクラスもあります。

meshgrid または 2D quadtree (C++、OpenCV) の描画方法を教えてください。四分木内の交点ごとにポイントを定義して、影響を受ける領域のフィードバックまたは出力を得る必要があります。したがって、出力は、任意の形状について、ポイントの最大範囲を教えてくれるはずです。

それは可能ですか？

どうも！

私は、惑星のクワッド ツリー構造を書いています。これは、クワッドから遠く離れて受容的に近づくと、詳細が減少したり増加したりします。ただし、非常に深刻で迷惑なバグに遭遇しています。

クワッド ツリーのサイズ (QUAD_WIDTH と QUAD_HEIGHT) を決定する 2 つのプリプロセッサ定義定数があり、値を 32 以外 (たとえば 16 または 64) に変更すると、ブルー スクリーンが表示されます。IDE として code::blocks を使用しています。もう 1 つ: code::blocks でプログラムをデバッグしようとすると、ブルー スクリーンが表示されます (定数が 32 であるかどうかは関係ありません)。

これはなぜですか？そして、どうすれば修正できますか。 PQuad.cpp

2 次元の世界に動的なオブジェクトがたくさんあるとしましょう。たとえば、キャラクター、投射物、パワーアップなど、ゲームでよく見られるものです。それらのすべてが動いています。それらの間の衝突を検出したいと考えています。それを行う良い方法は何ですか？

四分木を見てきましたが、動的に移動するオブジェクト間の衝突を検出するようです。フレームごとに四分木を再作成する必要があります (オブジェクトはフレームごとに位置が変わるため)。これはコストのかかる操作のように見えます。

四分木以外に、この問題に対する他のアプローチはありますか? 四分木アプローチを改善する方法はありますか? 結局のところ、すべてのフレームでツリーを再作成することはそれほどコストがかからないのでしょうか?

初めてここに来ました、皆さんが助けてくれることを願っています。

そこで、i=1:4 の座標 (localmaplon[i],localmaplat[i]) を指定して、4 つの quadtree ノードを検索して返す quadtree 関数を作成したので、localmap がどの quadtree にあるかを確認できます。

私が抱えている問題は、最初の解決策の後で、四分木ノードをルート ノードではなく検索する四分木として設定することです。

私のカウトは次のようになります。

私が間違っていることを理解するのを手伝ってくれませんか！ここに2つの機能があります。これは solveLocalBuckets 関数です。

これは getQuadTree 関数です。