5

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

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

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

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

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

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

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

アップデート

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

4

6 に答える 6

6

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

要するに、空間ツリーは検索空間を切り詰めるのに役立ちます。

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

于 2008-11-19T20:35:25.443 に答える
3

この質問を参照してください。 Stony Brook Algorithm Repositoryには、C++ での KDTree の実装がいくつかありますが、それらは STL や Boost の一部ではありません。

于 2008-11-19T20:35:42.527 に答える
2

配列のソートには O( n log n ) の時間がかかります。各ポイントを (ソートせずに) 個別にチェックするだけでも、O( n ) 時間かかります。

したがって、各ポイントを調べて確認するだけで、並べ替えよりも高速です。また、四分木を構築するよりも高速です。

編集:チェックする長方形がたくさんある場合は、別の話です。しかし、少数の一定数の長方形のみをチェックする必要がある場合は、「明白な」方法で行ってください。

于 2008-11-19T21:11:31.767 に答える
1

四分木を使用すると、次の 3 種類の qtree ノードがあります。

  1. ノードが対象の四角形の外にあります: 無視します
  2. ノードはターゲット長方形の内側にあります: ノード内のすべての点を含めます
  3. ノードは部分的に四角形の外側にあります: ノード内のポイントの境界チェックを行います
于 2008-11-19T20:35:33.227 に答える
1

Yuval F のリンクをたどると、Range Searchが見つかりました。これは、まさにあなたが探しているものと思われます。そこからいくつかのリンクをたどったところ、範囲検索を実装するオープンソースの C++ ライブラリであるCGALが見つかりました。

于 2008-11-19T20:55:34.327 に答える
-1

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

于 2008-11-19T20:43:59.000 に答える