問題タブ [quadtree]

QuadTree のバッキング構造として HashMap を使用することを検討しています。モートン シーケンスを使用して、関心のある領域の各正方形を一意に識別できると思います。私の QuadTree の高さは最大で 16 であることはわかっています。私の計算では、65,536 x 65,536 のマトリックスになり、最大で 4,294,967,296 個のセルが得られるはずです。HashMap の要素が多すぎるかどうかは誰にもわかりませんか? Tree を使用して常に QuadTree を作成できましたが、HashMap を使用するとパフォーマンスが向上すると考えました。

高さ 1 == (2x2) == 4 のモートン シーケンス

高さ 2 のモートン シーケンス == (4x4) == 16

高さ 3 のモートン シーケンス == (8x8) == 64

最大高さ 3 の木の Morton Sequencing の例。

これが私が知っていることです：

• 既知の長方形の領域で緯度/経度でデータを取得します。
• データはエリア全体を完全にカバーするわけではなく、そのエリアのどこかでチャンクに統合される可能性があります。(さらに悪いケースは、4,294,967,296 セルすべてのデータです)
• データの解像度は、領域を 65k x 65k の長方形に分割することになります。
• また、データの挿入/更新のために 10 対 1 のクエリが発生する可能性が高いこともわかっています。

ノードにオブジェクトを配置することで細分化できる QuadTree があります。また、クアッド スフィアの形で OpenGL で作成された惑星もあります。問題は、それらを組み合わせる方法がわからないことです。QuadTree は地球に関する情報をどのように保存しますか? 葉の Quad Tree ノードに頂点を保存しますか? もしそうなら、テクスチャリングと法線を損なうことなく、頂点データを 4 つのセットに分割するにはどうすればよいですか。この場合、代わりにインデックスを使用しますか?

要するに、私の質問は本当に次のとおりです。

頂点データをクアッド ツリーに保存して、惑星の地形を分割して、惑星が近距離でより詳細になるようにするにはどうすればよいですか。これは、ノードを分割するオブジェクトとしてカメラを使用することによって行われると想定しています。

私は多くの記事を読みましたが、それらのほとんどはこれをカバーしていません。Quadtree は、多くの惑星を同時にレンダリングできると同時に、陸上でも良好な解像度を得ることができるため、私のアプリケーションにとって最も重要なものの 1 つです。私の惑星のきれいな写真とそれは HD 太陽です:

惑星のビデオもここで見つけることができます。

平らな面に単純な四分木を実装することができましたが、位置が間違っていると思うので、大きな穴ができ続けています。ここでの最後の投稿です - http://www.gamedev.net/topic/637956-opengl-procedural-planet-generation-quadtrees-and-geomipmapping/で、src も取得できます。それを修正する方法はありますか？

「n」個の領域のどれに点「p」が含まれているかを見つけることをサポートするデータ構造を探しています。Quadtree と R-tree を見ていましたが、探しているものにぴったり合っているとは思いません。

本質的に、このツリーにいくつかの 3 次元の長方形の領域を追加し、このツリーに対して 3 次元の点をテストして、どの領域が最も厳密に点を拘束しているかを返すことができるようにしたいと考えています。境界が重なる領域はありません。

私が現在使用している素朴なアルゴリズムは、各長方形領域の各次元に対して点「p」を単純にテストすることです。

これは O(n) 時間で実行されます。n はリージョンの数です。Quadtree が 2 次元の点を見つけるために行う点として、検索で O(log n) を取得したいと思います。

私は最近、セグメント ツリーと呼ばれる新しいデータ構造に出会い、2 次元にも拡張できることを読みましたが、その実装やその他の詳細について読むための適切な情報源を見つけることができませんでした。グラフィックの分野ではなく、プログラミングコンテストで使用するという観点から学びたいと思います。それを使用して解決できるいくつかの問題も役立ちます。誰かがそれについて読むための良い情報源を教えてくれませんか? ありがとう

私は、すべてのループを更新する何千もの潜在的な何百万ものオブジェクトを処理できる必要があるシミュレーションに取り組んでいます。すべてのオブジェクトには、（AI）と呼ばれる論理関数が必要です。ただし、オブジェクトの場所に応じて、ロジックの詳細度が決まります。例えば：

[100個のオブジェクトを操作してシンプルに保つ]

• すべてのオブジェクトには場所（x、y）があります
• 20オブジェクトは、「関心のあるポイント」の場所から500ポイント離れています。
• 50オブジェクトは、オブジェクトから500ポイント離れてい20ます（1000ポイント離れています）。
• 30オブジェクトは、対象のポイントから100ポイント以内にあります。

これは、オブジェクトが仮想市民である詳細な都市シミュレーションであるとしましょう。午後6時に、全員が仕事から家に帰って寝る時間です。

ですから、私たちはすべての市民を繰り返しますが、私は彼らに異なることをしてもらいたいと思っています。

• 最も遠い物体（50）仕事から家に帰り、朝まで眠ります。
• 近くの物（20）仕事から家に帰り、一口食べてから朝まで寝ます。
• 最も近い物（30）仕事から家に帰り、一口食べて、歯を磨き、朝まで寝ます。

ご覧のとおり、関心のあるポイントに近づくほど、ロジックはより詳細になります。

私は、すべてのオブジェクトを反復処理するための最良かつ最もパフォーマンス効率の高い方法を見つけようとしています。これは、オブジェクトでいっぱいの手で比較的簡単ですが、少なくとも500,000個のオブジェクトを効率的に処理する必要があるため、アドバイスが必要です。

また、ループごとにすべてのオブジェクトを反復処理する必要があるのか​​、ループごとに最も近いオブジェクトを反復処理する方がよいのか、10ループごとに遠くのオブジェクトを反復処理する方がよいのかわかりません。

オブジェクトが近くにある他のオブジェクト間で相互作用する必要があるという追加の要件があるため、これを行うための最善の方法は、オブジェクトを四分木に整理することかもしれないと考えていましたが、よくわかりません。四分木は静的コンテンツ用のようですが、前述のように、私が扱っているオブジェクトには場所があり、他の場所に移動する必要があります。私は正しい思考の道を進んでいますか？または「より良い」方法はありますか？

誰かがそれに関連すると思うなら、私もc++で働いています。

アドバイスをいただければ幸いです。

ノート：

1. 興味のあるポイントは定期的に変化します。それをカメラビューと考えてください。
2. オブジェクトは動的に作成および破棄されます

まず、次のように考えを述べさせてください。

指定したルートまでのユーザーの距離を確認したい。ルートは複数のロケーション ポイント (図では、ポイント a、b、c、d) で構成されています。隣接する 2 つの点がベクトルを表します (図の青い線 ab、bc、cd)

次に、アプリケーションに移動します（特にアンドロイドですが、それはこの質問の一部ではありません）ユーザーがルートに沿って移動している間、ユーザーの位置が追跡されます。私が確認したいすべての新しい場所で、ユーザーがまだルート上にいる (または X の距離内にある) かどうかを確認します。

ルートに沿って 3 つの可能な場所を描きました。

• 場所 1 は問題ありません。ポイント 1 からベクトル ab に垂線を下ろします。これにより、このベクトル上の位置ポイントが得られ、2 つのポイント間の距離を計算できます (android: を使用Location.distanceTo()) 。

• 場所 2 ベクトルを扱っているため、開始も終了もありません。黒い線は、ベクトル ab の射影です。最も近い距離を計算すると、ベクトル ab までの距離は近いが、ベクトル bc からは遠い距離になります。実際、bc までの距離を計算する必要があります。これがルートの進行方法だからです。しかし、距離を計算するためにどのベクトルを選択する必要があるかをアルゴリズムで知るにはどうすればよいでしょうか?

• 場所 3 は、ベクトル ab または bc で計算する可能性を与えてくれます。どちらもほぼ同じくらい近いです。どちらを選択するかを知る方法は？

これを切り上げるには：

私は位置点を持つ配列を持っています:

私のアプリケーションは、ユーザーの位置を追跡しています。新しい場所を配列内のこのトラックと比較したいと思います。

誰かが問題をカバーしているアルゴリズムを知っていますか、または誰かがアルゴリズムで私を助けてくれますか? (疑似コードで十分です)

//編集: Quadtree アルゴリズムについて読みました。おそらくそれは、Soonts の実装に加えてオプションです。

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

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

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

次のように:

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

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

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

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

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

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

ありがとう！

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

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

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

定期的に多くの人からGPS位置を収集するHerokuのWebサービスを設計しようとしています。特定の瞬間に各人の位置を追跡するだけでなく、特定の範囲/半径内にいる人を照会できるようにしたいと思います。

四分木を使用してこれを行う方法は考えていますが、車輪の再発明を行わないように、これをすでに行っているアドオンサービスがないことを確認したいと思います。

どんな助けでもいただければ幸いです！

ありがとう！

私の現在のエンティティ エンジンは、すべてのエンティティ (配列) をループしてから、すべてのエンティティが持つ libgdx Rectangle インスタンスを使用して衝突をチェックする quadtree を使用します。

私のQuadTree（かなり長いので、IDをリンクするだけだと思いました）

Entity クラスには、placeFree メソッドがあります。

screen.placeFree メソッド:

プリエンプティブな衝突を確認するには、次のようにします。

基本的に、placeFree() は実際に現在のヒットボックスのコピーを新しい位置に配置し、そこで衝突が発生するかどうかを確認します。私がやりたいことは、左に移動する前に、プレーヤーの左側の領域に衝突がないかどうかを確認することです。

私の現在の問題は、「Solid」(エンティティのサブクラス) の 3 つのインスタンスを追加すると、追加された最初のエンティティでのみ機能することです。なぜこれが起こるのですか?どうすれば修正できますか?

ということです（赤枠は通常の当たり判定、緑は先制当たり判定）。

この写真では、プリエンプティブな hitBox が通過するだけであることがわかります。

しかし、これではできません。最初にそのブロックを追加したからです (緑色のボックスをより明確に表示するために placeFree(x,y-100) を使用しました):

Quadtreeのコピーコンストラクターに取り組んでいます。これが私がこれまでに持っているものです：

どこが間違っているのかわかりませんが、メモリリークが発生し、Valgrindは初期化されていない値があることを指摘しています。助けてください？

添付されているのは、buildTree関数です。実際にツリーを作成します。私はここで何か間違ったことをしているのでしょうか？