問題タブ [quadtree]

平面配置を検出したい非常に大きな点群（> 100000ポイント）があります。八分木を使用して点を非常に小さな平面クラスターに分割し、同一平面上にある隣接するクラスターをマージすることにしました。点群を小さな平面クラスターにすばやく分割するコードをC++で記述しましたが、それらを効果的にマージする方法はわかりません...

私のOctree実装では、ポインター構造を使用しています。子ノードへのポインターを含むOctreeNode配列を持つsがあり、リーフノードの場合はすべてのポインターがあります。OctreeNode* children[8]NULL

私が最初に考えたのは、各OctreeNodeオブジェクトで、オブジェクトへのポインターを保持するPlaneことでした。ポイントを最初に分割した後、八分木の各リーフは、リーフにPlane含まれるすべてのポイントに適合する最小二乗を表すを取得します。次に、ツリー内のすべてのリーフノードを反復処理します。リーフノードごとに、隣接するリーフノードのそれぞれをチェックします。隣接するリーフの平面を現在のリーフの平面とマージする必要がある場合はPlane* newPlane = Plane::mergePlanes(this->plane, neighbor->plane);、両方のノードのポイントを表す新しい平面を作成するために呼び出します。

ここで問題が発生しました...最初は、両方のプレーンを新しいプレーンに置き換えるだけでよいと思いました。つまりplane = newPlane; neighbor->plane = newPlane;、完了しました（メモリリークは別として、実際のコードで処理しました）。残念ながら、これは実際には機能しません。OctreeNode複数の平面をマージした後、単一のを指すいくつかの異なるが存在する可能性がありPlane、単にポインタを置き換えるだけで、古い平面を指すすべてのポインタを置き換えるわけではthis->planeありません。neighbor->plane

私が最初にそれを思いついたときでさえ、解決策はハックのように見えました、そして今、その欠陥はさらに明白です。誰かが私が思いついたマージ方法を修正する方法を考えたり、より良い方法を考えたりできますか？

ありがとうございました

こんにちは、Android 用の非常に大きな gpx トラックで問題が発生しています。トラックの小さな部分を四分木に追加したいのですが、この小さな部分だけがディスプレイに描画されます。私の本当の問題は、この問題に対して適切な四分木構造をどのように実装するかです。ありがとうございます。言語の間違いをお詫び申し上げます。私は英語が苦手です。

全て、

Pythonを使用してクアッドツリーを実装する例はいくつかありますが、私の質問は、プロジェクトに簡単に含めることができる単一の.pyファイルのように純粋なPythonで記述されたクラスを知っている人はいますか？最も人気のある3つのパッケージがここにリストされています。これらのクアッドツリーライブラリのいずれかが良いですか？しかし、それらを実行するために必要なすべての依存関係のために、私はそれらを使用することに運がありませんでした。私は本当に軽量で比較的使いやすいものを探しています。地球全体の境界を渡してスクリプトを呼び出し、そこから作業を進めたいと思います。myMethod((-180,-90,180,90))

ありがとう、アダム

Mathematicaで四分木を実装しました。Mathematica のような関数型プログラミング言語でコーディングするのは初めてで、これを改善したり、パターンをより適切に使用してよりコンパクトにしたりできないかと考えていました。

(未使用のノードを剪定することでツリーを最適化できる可能性があることを理解しています。また、kd ツリーのような空間分解のためのより良いデータ構造があるかもしれません。)

また、新しいポイントが追加されるたびにツリー/式全体をコピーするという考えにはまだ満足していません。しかし、私の理解では、部分を変更せずに式全体を操作することが関数型プログラミングの方法です。この点について説明をいただければ幸いです。

MV

コード

使用法

出力

私は100から200ポイント（x、y）のセットを持っています。どれが他の特定の距離内にあるかを確認する必要があります。特定の距離は、プログラム全体で固定されています。たとえば、50です。ポイント1がポイント5、7、25、90、96、105などの範囲内にあるとします。同様に、ポイント2は23、45などの範囲内にあります... x、y座標で位置を特定するためのオブジェクトの保存

ここではQuadTreeが提案されていますが、これを使用して、外接する長方形内のすべてのポイントを取得できます。しかし、境界円内のすべてのポイントを取得するにはどうすればよいですか？最大距離内で緯度/経度に最も近いポイントを返す方法がありますが、距離内のすべてのポイントを取得するにはどうすればよいですか？ http://openmap.bbn.com/doc/api/com/bbn/openmap/util/quadtree/QuadTree.html#QuadTree(float、float、float、float、int）

1つの方法は、ツリーから各ポイントを取得したときに削除し、nullになるまで、最も近いポイントを再度クエリすることです。それが唯一の方法ですか？

四分木と、ビデオゲーム コードの衝突検出におけるその使用法について研究しています。

ただし、これまでのすべての実装は、C++、C#、javascript、および Lua のオブジェクト指向機能に依存してすべてのノードを実行しており、それを生の C に変換する方法がまったくわかりません。

目的は、複数のオブジェクト (ショット) をアクター (常に移動) と地形 (静的) に対してテストすることです。次に、地形を持つ俳優。「純粋な」C 用語 (つまり、メソッドや自己参照オブジェクトを使用しない) で読むことができる例を見つけることができないため、それをコーディングする方法の基本的な考え方さえ把握できませんが、その背後にある考え方は理解しています。アルゴリズム。設定方法、参照方法、使用するデータ型など、まったくわかりません。私は C++ についてまったく何も知らないので、C に翻訳することは不可能です。

また、地形にはタイルマップを使用する予定で、完全な正方形ではなく、縦長または横長のマップなどを作成したいと考えています。四分木はそのようなマップでも機能しますか?

また、多くの移動要素があり、地形は唯一の静的な部分です (移動するブロックやドアなどの要素は別のエンティティです)。更新が頻繁に必要になる場合、四分木を使用する価値はありますか? グローバルデータにする必要さえありますか？(一部の関数内で偽造され、衝突が有効になったときに渡される可能性もあります)。そのような場合、メモリを割り当てる必要がありますか?

四分木は、ゲームなどでエンティティの空間編成を最適化するために使用されますhttp://en.wikipedia.org/wiki/Quadtree。

HTML5 Canvas でクアッドツリーが使用されている例はありますか?

私のアプリケーションは、マップ ファイルから最大 10 万個のアイテム (四角形) のコレクションを読み込み、高速検索用のインデックスとして MX-CIF 四分木を構築します。四分木は起動時に構築され、その内容は実行時に変更されません。

(MX-CIF 四分木では、アイテムはそれを完全に含む最小のノードによって格納されます... 内部ノードとリーフ ノードの両方にアイテムが含まれる場合があります)

最初のパスでは、コレクションの外側のエクステントを見つけるので、ルート ノードの大きさがわかります。

2 番目のパスでは、各項目を完全に含む最小のノードに追加します。ノードが特定の数の項目を通過すると、ノードは分割され、子は新しい親ノードと 4 つの子ノードの間で再分配されます。

前もってすべてのアイテムを持っていることを考えると、ツリーをより効率的に構築するにはどうすればよいでしょうか?

このアルゴリズムが既知のものであるかどうかを知る必要があります。

これは、SURFアルゴリズムの結果を比較します。

1. これは最近傍アルゴリズムですか？これは、funcがすべてのポイントの最も近いポイントを検索しているように見えます。
2. Quadtreeまたはkd-treeを使用して同じことを行うことはできますか？
3. 画像ポイントと比較して、それらが同じか類似しているかを知るためのより良いアルゴリズムがありますか？
4. できれば、それらをmysqlに保存し、kdツリーを構築して1つの画像をすべての画像で比較したいのですが、それは可能ですか？
5. RANSACは、このタスクで何かに役立ちますか？
6. 誤検知をキャッチする方法はありますか？

円形のオブジェクトがあるとしましょう。各オブジェクトの直径は64ピクセルです。

私の四分木のセルは、たとえば96x96ピクセルです。

円が存在するセルとそのすべての隣接セルからの衝突を確認すると、すべてが正常に機能します。

しかし、直径が512ピクセルの円が1つある場合はどうなりますか？これは多くのセルをカバーするため、隣接セルのみをチェックする場合に問題になります。しかし、はるかに大きなオブジェクトがツリーに挿入されるたびに、クワッドツリーグリッドのサイズを変更することはできません...