2

ポリゴンの大きなリスト (サイズ 250,000 など) とポイントの大きなリスト (サイズ 100,000 など) があります。私がする必要があるのは、これらの各ポイントがどのポリゴンに属しているかを見つけることです。

ポリゴンは常に、最初と最後の点が同じ 5 つの点を持つ長方形/ダイヤモンドです。また、ポリゴンに関連付けられたおおよその中心点もあります。多角形の例は次のとおりです。 Polygon(a;b;c;d;a) = (3,1; 5,3; 3,5; 1,3; 3,1) および中心点 (x) = (3 、 3)。以下のサンプル図を参照してください。

          c (3,5)
         /\
        /  \
(1,3) d/    \b (5,3)
       \ x  /
        \  /
         \/
          a (3,1)

これは簡単な例です。これらのポイントのほとんどは、lat-lon/GIS 座標です。

ポイントの入力リストは、どのポリゴンとも一致しないか、ポリゴン リスト内の 1 つまたは複数のポリゴンと一致する可能性があります。

現在、ポイントとポリゴンを取得して、ポイントがポリゴン内にあるかどうかを確認する関数があります。ポイントがポリゴン内にあることを確認したいときはいつでも、ポリゴンの完全なリストを繰り返し処理して、一致するかどうかを確認する必要があります。また、ポイントが複数のポリゴンに含まれている可能性があるため、毎回完全なリストを反復処理する必要があります。これは非常に非効率的です。

私が探しているのは、ポリゴンの完全なリストではなく、ポイントごとにチェックする必要があるいくつかのポリゴンをすばやく取得できるように、これらのポリゴンを HashMap などに順序付けすることです。ポイントには x と y の両方のパラメーターがあるため、ポリゴンを並べ替える良い方法を見つけることができません。また、すべてのポリゴンには中心点があることに注意してください。簡単に検索できるように、これらの中心点をキーとしてポリゴンを並べ替える方法はありますか?

これに関する考え/アイデアはありますか？ありがとう！

4

2 に答える 2

2

スペースの効率的な分割である kd ツリーを使用する

http://en.wikipedia.org/wiki/K-d_tree

于 2013-02-19T17:02:25.403 に答える
0

セルと交差するポリゴンの各セル ストア リストに対して、2D 空間を正方形のセルに分割します。ポイントをチェックする必要がある場合は、まずセル ポイントが属するセルを見つけてから、このセルと交差するすべてのポリゴンを反復処理してテストします。セルあたりのポリゴン数が適切になるように、セル サイズを選択します。

ポリゴンの分布が不均一な場合は、正方形セルの代わりに四分木を使用することをお勧めします。

于 2013-02-19T16:20:26.343 に答える