2Dポイントを保存して、四角形内のポイントをすばやく取得します

Question

多数の2Dポイントがあり、特定の長方形にあるポイントをすばやく取得したい。 「。」と言いましょうは任意のポイントであり、「X」はTopLeftとして「T」、BottomRightポイントとして「B」を持つ長方形内で検索するポイントです。

. . . . . .
. T-----+ .
. | X X | .
. +-----B .
. . . . . .

私は、セットの先頭でTopLeftポイントをソートし、セットの最後でBottomRightをソートするソートファンクターでstd :: setを試しました。最初にX値でソートすると、次のポイントが見つかります。

. . . . . .
. T-----+ .
X | X X | X
. +-----B .
. . . . . .

これは、見つかった各ポイントが実際に長方形の内側にあるかどうかを確認する必要があることを意味します。あまり良くない。

これを行うためのより良い方法は何ですか？

私の言語はC ++（Windows）であり、STLとブーストを利用できます。

更新

これまでの回答を読んで、問題のすべてのパラメーターを説明していないことに気付きました。固定された長方形はありません。 長方形は、実行時にユーザーが設定できます。つまり、この更新の前にArteliusが提案したように、ポイントセットを並べ替えると、すべてのポイントを線形検索するよりも効率的であることが約束されます。 ただし、まだ試してみます！ユーザーが長方形を非常に頻繁に設定するとは思わない。そのため、実装の努力に関しては、私にとっては良い解決策となるかもしれません。

Answer 1

クアッドまたはrツリーを使用して、空間インデックスにポイントを格納できます。次に、長方形に重なるツリーのすべてのノードを見つけることができる場合、このサブセットの各ポイントを比較して、長方形に収まるかどうかを確認する必要があります。

本質的に、空間ツリーは検索スペースの整理に役立ちます。

範囲内のポイントを分割するなど、より単純なソリューションを使用できる場合があります。 xが1つの範囲として0,10から、別の範囲として11,20であるとします。サーチスペースを整理できるソリューションがあれば役立ちます。

Answer 2

この質問をご覧ください。 ストーニーブルックアルゴリズムリポジトリには、KDTreeの実装がいくつかあります。 C ++、 ただし、それらはSTLでもBoostでもありません。

Answer 3

配列のソートにはO（ n log n ）時間かかります。各ポイントを個別に（ソートせずに）単純にチェックするには、O（ n ）時間かかります。

Ergo、各ポイントを通過して確認するだけで、ソートよりも高速です。また、4分木を構築するよりも高速です。

編集：チェックする長方形がたくさんある場合、それは別の話です。ただし、少数の固定された数の長方形のみをチェックする必要がある場合は、「明白な」方法！

Answer 4

クアッドツリーを使用すると、3種類のqtreeノードがあります：

1. ノードはターゲット長方形の外側にあります：無視
2. ノードはターゲット長方形の内側にあります：ノード内にすべてのポイントを含めます
3. ノードは部分的に長方形の外側にあります：ノード内のポイントで境界チェックを行います

Answer 5

Yuval Fのリンクの後に、範囲検索、これはまさにあなたが探しているもののようです。そこからいくつかのリンクをたどると、 CGAL 、範囲検索を実装するオープンソースC ++ライブラリ、例こちら

Answer 6

並べ替え関数は、四角形の内側に追加されたポイントをチェックし、四角形の外側のすべてのポイントの前に四角形の内側のすべてのポイントを並べ替えることができます。それぞれがいくつあるかを追跡するか、検索時にカットオフポイントを見つけるためにセット全体でバイナリ検索を使用する必要があります。