問題タブ [quadtree]

動作するQuadTreeを実装しました。可能な限り最小のクワッド（最小領域まで）のバウンディングボックス（x、y、width、height）で識別されるアイテムを収容するために、2次元スペースを細分化します。

私のコードはこの実装に基づいています（私のコードはC＃ではなくLuaにあります）： http： //www.codeproject.com/KB/recipes/QuadTree.aspx

挿入と削除を正常に実装することができました。アイテムの位置と寸法は時間の経過とともに変化するため、update（）関数に注目します。

私の最初の実装は機能しますが、それは非常にナイーブです。

ええ、私は基本的に、移動するたびにすべてのアイテムを削除して再挿入します。

これは機能しますが、もう少し最適化したいと思います。結局のところ、ほとんどの場合、移動するアイテムは同じquadTreeノードに残ります。

この種の更新に対処するための標準的な方法はありますか？

それが役立つ場合は、私のコードはここにあります：https ://github.com/kikito/middleclass-ai/blob/master/QuadTree.lua

私はそれを実装してくれる人を探していません。（他の言語でも）既存の動作する実装へのポインターで十分です。

問題があります: 0 または 1 を含む配列 nxm がある場合、0 の値を四角形にグループ化する必要があります。最初は単純な四分木を使用しましたが、ツリーの同じレベルにある異なるノードは同じ値を持ちます。Rツリーが私の問題または別のデータ構造で機能するかどうかは完全にはわかりません。この構造を事前計算ステップで使用するだけなので、それだけです。

ps: 2D 画像を扱っています

PHPで四分木を作成するにはどうすればよいですか?

「グリッドのような」レイアウトが欲しいです。

したがって、各「ノード」には、北、南、東、西の 4 つの「出口」があります。

PHP専用のドキュメントが見つからなかったため、QuadtreeのサンプルPHPコードを持っている人はいますか:(

私はあなたの親友になります... (おそらくそこに担当者もいます)。

私は、ノードから構築され、ダウンではない整数ベースの四分木構造を書いています。これを行うには、すべての要素を含む次に大きいノードを見つける必要があります。既存のノードを定義している場合、そのノードの境界外にアイテムを追加しようとすると、両方を包含するように、より大きなノードを作成する必要があります。私は（私が賢いと思う）単一の点の周りのバウンディングボックスを見つけるためのコードを持っています：

[ポイント（0,0）の周りのボックスは、 すべて整数ベースであるため、場所（-.5、-。5）ではなく、場所（0,0）のサイズ（1,1）のボックスであることに注意してください]

これは常に（私が言えることから）ノードとして四分木に収まるボックスを返します。たとえば、new Rectangle(0,0,2,2)は受け入れられますがnew Rectangle(2,2,2,2)、受け入れられnew Rectangle(1,1,2,2)ません。

私の問題は、点ではなく長方形に対してこれを実現する方法がわからないことです。私が考えることができる唯一の解決策は、大きさが増すボックスをループすることですが、私が考えることができないいくつかのO（1）解決策が必要であると確信しています。

例：

実装：

私はjQueryで作業していて、javascriptのクアッドツリー用に次のコードが与えられました。

しかし、これは私には3D配列のように見えますが、私は愚かですか？^。^

緯度と経度の2万以上の都市のデータベースがあり、このデータセットに対して多くの最も近いポイントクエリ（特定の緯度と経度のポイントに最も近い都市）を作成する必要があります。

R-TreeまたはQuadTreeはこれに最適なデータ構造になると思いますが、機能するrubyの実装を見つけることができませんでした。何でも知ってますか？

私は現在、2D シューティング タイプのゲームに取り組んでおり、衝突検出にクワッド ツリーを使用しています。アクターをツリー内の属するノード/リーフに正しくプッシュする作業クワッド ツリーを作成しました。ただし、いくつかの問題があります。

まず、クアッドツリーを実際に使用して、オブジェクトが衝突をテストする必要がある他のオブジェクトを選択するにはどうすればよいですか? これがどのように行われるかはわかりません。

2 番目の質問が表示されます。別のノードの隣接ノードではないオブジェクトがノードにあるとしますが、そのオブジェクトがいくつかのノードにまたがるほど大きい場合、実際の衝突を確認するにはどうすればよいでしょうか。 「遠く離れた」ノードのオブジェクトと衝突するのに十分近いですか？ノードに完全に収まらないオブジェクトは、親ノードに保持する必要がありますか?

私のゲームでは、ほとんどのオブジェクトがさまざまなサイズで動き回っています。

四分木に関するかなりの数のブログ/記事を読みましたが、ほとんどは、実際に探しているものではないツリーを構築する方法を説明しているだけです。

ヘルプ/情報は大歓迎です。

四分木について説明し、挿入と検索のための簡単なコード（できればCで）を提供してください。

次のように定義された四分木を想像してください。

コンストラクターを使用すると、整形式ではない四分木を作成できます。bad1単純に C 255 である必要があり、bad2右下の四分木であるため有効ではありません (同じ理由で、Q (C 0) (C 255) (C 244) (C 64).

ここまでは順調ですね。その整形式をチェックすることは、単純に内部の四分木を再帰的にチェックすることです。基本的なケースは、すべての内側の四分木がリーフである場合です。これにより、すべての色がすべて等しくなるわけではありません。

質問:葉と四分木の考えられるすべての組み合わせに対して、すべての一致を入力することを避けることはできますか?

私の質問が非常に奇妙である場合は、しばらくお待ちください。

flipvリストの各要素に一度だけ適用して[se, sq, nw, ne]、結果を（もちろんリストとしてではなく）Qコンストラクターに渡すにはどうすればよいでしょうか。

編集：ポインタはNW NE SW SEである必要があるため、これは実際には間違っていることに注意してください。