5

ポリゴンである一連のリージョン (ジオフェンス) があります。このデータ セットは固定されています。したがって、データの挿入と削除の必要はありません。クエリ ポイント (経度、緯度) が含まれる地域を検索するために使用できるデータ構造はどれですか?

注: ポイントのセットに対して KD ツリー (実際には 2D ツリー) を正常に実装しました。しかし、この問題にはうまくいきません。次に、R ツリーを実装しました。それは問題を解決しますが、遅いです（または私の実装はひどいです）。

ありがとうございました

注: R ツリーの実装に取り​​組んでおり、現在は正常に動作しています。

4

2 に答える 2

2

この問題にはR-Treeデータ構造を使用できます。

于 2011-11-16T22:21:38.123 に答える
2

挿入/削除を行っておらず、おそらくデータを前処理するのに十分な時間があるため、追加のメモリを使用して計算を高速化できます。前処理の基本的な考え方:

  1. すべてのポリゴン ポイントを取得し、それらすべてを含む最小の軸に沿った外接する四角形を決定します。基本的に、これは X と Y の最小値と最大値です。
  2. 検索グリッドの作成に使用する分割係数 dX と dY を選択します。分割係数に 2 の累乗を選択すると、後で計算を少し速くすることができます。
  3. 境界四角形の最小値が (0,0) と一致するようにポリゴン データを変換し、各次元の分割係数の整数倍になるように四角形を拡張します。
  4. 各グリッドの正方形を検討し、正方形と交差する多角形のリストを作成します。このリストを各グリッド スクエアに保存します。データの性質 (正方形と交差すると予想されるポリゴンの数) に応じて、ストレージ スペースまたは速度のいずれかを最適化するさまざまな方法があります。

ここで、点を含む領域を見つけたい場合:

  1. 前に定義した原点を使用して点を平行移動し、点を含むグリッド スクエアを決定します (2 のべき乗を使用した場合、これはシフト操作です。それ以外の場合は除算です)。
  2. グリッドスクエアのリストを見てください。空の場合、含まれるポリゴンはありません。そうでない場合は、リスト内の各ポリゴンを考慮して交差を検索する必要があります。

これは、広がり、ほとんど交差しないポリゴンに適しています。特に、1 平方あたり数ポリゴンしか存在しないように十分細かいグリッド サイズを選択できる場合に有効です。交差するポリゴンがたくさんある正方形に当たると遅くなります。追加の最適化の 1 つは、正方形が完全に多角形内に含まれていることを示すために、正方形にリストされている各多角形にフラグを設定することです。これにより、多くの場合、ポリゴン エントリごとに 1 ビットの犠牲を払って低速の封じ込めテストを回避できます。これは、ポリゴン サイズに比べてグリッド間隔が細かい場合に特に役立ちます。ほとんどの正方形は交差点やエッジにないためです。

さらに速度が必要な場合は、ポリゴン参照を使用して各正方形にエッジ情報を保存し始めることができます。正方形の領域と実際に交差するポリゴン エッジに対してのみテストする必要があります。これにより、労力をポリゴンごとにほんの一握りのエッジ テストに減らすことができます。

于 2011-11-08T17:25:10.160 に答える