2

できればPHPで、ポリゴンのグループを分析してグループの外側の境界を検出する方法を探しています。

具体的には、これは地域をレンダリングする Google マップ v3 アプリケーション用です。領域内の各ポリゴンは郵便番号です。領土境界のみを検出して描画しようとしています。これが私が達成しようとしていることのモックアップです：

複雑な領域エッジ検出の前後の画像

この問題を解決するために私が直面する課題:

  1. 各地域内の郵便番号は連続していない可能性があります (多くの場合、連続していません) (上記の例の赤と緑の地域を参照してください)。
  2. 郵便番号は必ずしも凸型であるとは限らないため、凸包手法は機能しません (間違っているのでしょうか?)
  3. 上の画像ではそのように見えますが、頂点が ZIP 間で真に重複していることはめったにありません。各緯度/経度座標 (つまり、ポリゴンの各頂点) には、小数点以下 10 桁の精度があります。元の形状に似たクリーンなデータセットが生成されなかったため、丸め手法を既に試して拒否しました。

良い面としては、これらの領土は一度確立されると変わることはありません。したがって、このプロセスをオフラインで実行して、結果の領域ポリセットを計算および保存できます。

明確化: 私のデータは郵便番号レベルで保存されます。各郵便番号は、緯度/経度座標の 1 つ以上の大きなセットによって定義されます。各緯度/経度座標は、Google マップ ポリゴンの 1 つの頂点を定義します。より大きな地域と同様に、各郵便番号は凸状である場合とそうでない場合があり、単一の連続した多角形である場合とそうでない場合があります。より大きな地域は、単純に郵便番号のリストとして保存されます。テリトリーのポリゴン データは保存されません。これが、ここで解決しようとしている問題です。

正しい方向への指針を前もって感謝します。

4

1 に答える 1

1

どの郵便番号がどの地域に関連しているかのリストがあるようですね。郵便番号ごとに多角形もあります。

この場合、解決策はかなり簡単です。重要な観察/仮定は、国境を接する郵便番号は削除する必要があるエッジを共有する必要があるということです。これが当てはまらない場合、以下は論点です。

各地域について:

並べ替えられたエッジにキー付けされたディクショナリを作成します。そのアイテムは、そのエッジを持つポリゴンのリストです。次に、テリトリー内のポリゴンを調べて、辞書に記入します。Edge(A,B) が Edge(B,A) と同じであることを確認する必要があるため、これは注意が必要な場合があります。これは、エッジのポイントをソートすることで実行できます。

すべてのポリゴンを確認すると、基本的にエッジのテーブルと、それらが関連付けられているポリゴンが表示されます。このテーブルをグラフに変換し、2 つ以上の多角形にあるすべてのエッジを無視します。ただし、「複数」はおそらく不可能です。結果は無向巡回グラフであり、深さ優先探索と同様のアルゴリズムを使用してグラフから領域ポリゴンを抽出できるはずです。

パフォーマンスは O(N) である必要があります。ここで、N はエッジ/頂点の総数です。

于 2013-02-02T21:43:35.940 に答える