2

一致するかどうかを判断するには、特定のポイント(lat、lon)を複数のポリゴンと一致させる必要があります。

最も簡単な方法は、各ポリゴンを反復処理してポイントインポリゴンチェックアルゴリズムを適用することですが、これは非常にコストがかかります。

私が行った次の最適化は、各ポリゴン(上限、下限)の境界矩形を定義し、各境界ボックスに対してポイントを繰り返しチェックすることでした(ポリゴン内のすべてのポイントをチェックする場合と比較して比較が少なくなります)。

他に可能な最適化はありますか?バインドされた長方形のポイントまたはジオハッシュの空間インデックスは役立ちますか?

4

1 に答える 1

2

さらなる最適化:

バウンディングボックスのアイデアは良いです。ポイントがバウンディングボックス内にあるかどうかのチェックは非常に高速です。

それでも速度が必要な場合は、次のように事前計算を行うことができます。

  1. 各polgonに対して、バウンディングボックスを作成します。
  2. マップをカバーする同じサイズの「タイル」を定義します。
  3. タイルごとに、重なるポリゴンのリストを作成します。これを行うには、最初にバウンディングボックスがタイルと重なっているかどうかを確認します。含まれている場合は、ポリゴンがタイルと重なっているかどうかを確認します。

検索するときは、次のようにします。

  1. あなたがいるタイルを決定します。それは速い操作です。
  2. これで、潜在的なポリゴンのリストができました。
  3. ポリゴンごとに、ポイントがバウンディングボックス内にあるかどうかを確認します。
    そうである場合は、前述のより高価なアルゴリズムを使用して、ポイントがポリゴン内にあるかどうかを確認します。

私はこのアルゴリズムを数回使用しましたが、非常に高速です。タイルサイズを変更することで、メモリフットプリントとパフォーマンスの適切なバランスを選択できます。

極端な場合を考えてみてください。

  • マップ全体をカバーする1つの巨大なタイル:マップ
    内のすべての要素の1つのリストを取得し、すべての境界ボックスをチェックする必要があります。

  • 非常に小さなタイル(国ごとにポリゴンしかないマップの場合は1x1 m):
    大量のタイルを取得します。すべてのポリゴンは多くのタイルに分割され、各タイルには1つのポリゴンしかありません。ただし、ポイントが(高速で)どのタイルにあるかがわかれば、チェックする必要のあるポリゴンが1つしかないことはほぼ100%確実です。

あなたはその中間にいる必要があります。これがたまにしか必要ない場合は、パフォーマンスよりもメモリフットプリントを低くすることをお勧めします。最適なタイルサイズは、ポリゴンサイズの均一性にも依存します。したがって、最適なタイルサイズを自動的に計算する方法はなく、正しくなるまで少し調整する必要があります。

于 2012-06-22T09:46:08.117 に答える