問題タブ [quadtree]

QuadTree でナビゲーション/A* を実行したい。

私はすでに QuadTree を実装しているか、少なくとも私が QuadTree だと思っているものを実装しています。一方、内部ノードにも要素が含まれている場所をいくつか見てきました。私の場合、内部ノードはその子にのみリンクし、要素はリーフ ノードのコレクションに格納されます。各ノードはその親にリンクしていますが、(現在) 隣接ノードへのリンクはなく、兄弟も他のブランチのノードもありません。要素は領域であり、点だけではありません。

また、グリッドで A* をかなりの時間見たり、QuadTree でデモを見たりしましたが、これには詳細がありませんでした。

主な問題は、どうすればすぐに隣人にたどり着くことができるかということだと思います。

葉を互いにリンクしたままにしておくべきかどうかはわかりません。しかし、要素が位置を更新するにつれてツリーが動的になるため、これは大変な作業になります。また、ノードのサイズによっては、大きなリーフが一方向 (東など) に多くの小さなリーフを持つ可能性があるため、リンクの動的コレクションの王様も必要になります。これを更新するための努力は非常に大きなものに思えますが、現在はどうすればよいかわかりません。

Thx n rgds

Javascript で2 次元のkd ツリーを実装し ( GitHub で確認してください)、 D3と一緒に最近傍検索に使用しています。

D3 にquadtree の実装があることを知りましたが、API ドキュメントがまばらで、Google 検索が役に立たないことも発見しました。可能であれば、自分で再発明した車輪よりも、よく旅行されたライブラリを使用したいと思います。

D3 の quadtree を使用して最近傍検索を実行するにはどうすればよいですか? 最近傍とは、つまり次のことを意味します。

• 四分木に 2 次元の点を設定する
• 四分木に必ずしも存在しない新しいポイントに最も近い四分木に含まれるポイントを検索します

ポイントを格納するためのデータ構造として四分木を使用します。特定の領域内のすべてのポイントをすばやく見つける必要があるため。

ただし、ポイントを移動する必要があります。私のC++プログラムで。移動はすべてのポイントで発生しますが、すべてのポイントで異なる方向に移動するため、現在、クアッドツリーを破棄して再構築しているため、多くの割り当てと削除が発生します。

したがって、私の質問は、この種の問題のためのより良いデータ構造はありますか?

次の要件があります: n ポイントを持っています。

特定のエリア内のすべてのポイントをすばやく取得する必要があります。私の四分木では、これは約O（log（n））です。ただし、この操作は m > n の場合に m 回呼び出されるため、約 O(m*log(n)) になります。

すべてのポイントを移動する必要があります。現時点では、これは約 O(n*logn) で実行されます。このメソッドは、すべての m に対して 1 回だけ呼び出されます。

しかし、現時点ではこの解決策は不十分だと思います。私は常に四分木を破棄して再構築するため、割り当てによるオーバーヘッドが発生します。

更新: ポイントは均一に分散されていません。密集している場所と点数が少ない場所があります。

ここにいくつかの単純化されたコードがあります。格納されているポインターのコードは次のとおりです。

ここにクワッドツリーのインターフェースがあります

ここでは、Point がどのように格納されるかを示す get メソッドと put メソッドの実装を備えた QuadTreeNode のインターフェイスを示します。

C ++で簡単な四分木を作成したかったのですが、関数内で構造体の値を変更すると、値が元に戻ることがわかりました。また、再帰関数内で、作成されたデータの一部がグローバルになることはありません。どうすればよいですか？

quadtree と kd-tree の主な違いは何ですか? ポイントが多くの次元で分割されていることは理解していますが、なぜ一方を他方に使用するのかわかりません。特定の領域にあるポイント (2D ポイント) の数をカウントできる構造が必要です。基本的に、ポイントのクラスターを検出しようとしています。

クワッドツリー内の子ノードのセットを親に再帰的に折りたたむのに問題があります。追加、削除、および細分割は問題なく機能しますが、ツリーから十分な要素が削除されても、ツリーは満杯に満たないノードを親に折りたたんでから削除することはありません。

ありがとう。

[編集]

問題が解決しました。これが最終的なコードです。みんなありがとう。

リージョンが交差するノードに含まれるクワッドツリー内のすべての要素を検査できるようにしたいと思います。Queryただし、問題は、高さが2しかないほど小さいセクションを呼び出すと、スタックオーバーフローが発生することです。

次のことを行うためのより効率的な（そして間違いの少ない）方法は何ですか？

ノード間の衝突を実装するd3.jsでグラフを描画しようとしています。次のcodigoを試してみました。Peroが機能しません。

衝突検出の描画を削除したが、ノードが重複している場合..。

衝突検出を削除すると機能しますが、ノードが重複しています。私は助けが必要です ：（

四分木または kd ツリーの分割とマンデルブロ集合について読んだことがありますが、最初の分割前の四角形とフレームがマンデルブロ集合にあるか、反復深度が同じで、アルゴリズムがタイリングから戻った場合はどうなりますか? 長方形が大きすぎる場合、長方形の塗りつぶしを強制的にスキップするにはどうすればよいですか?

ワールド座標でマウスの位置を見つけようとしていますが、正しいコードを見つけるのに苦労しています。現時点では、これを使用して光線を決定します。

これにより、光線の原点と方向がわかります。

しかし...

カスタム メッシュ (directX のものではない) を高さマップと共に使用し、クアッドツリーに分割しましたが、ロジックが正しいかどうかわかりません。フラスタムを使用して、クアッドツリー内のどのノードが表示されているかを判断し、チェックを行いました。これらのノードでのみ三角形の交差、これがこのコードです:

注* m_mousepos はベクトルです。

このコードは正しいですか？もしそうなら、私の問題は四分木に関連しているに違いありません。

ありがとう！