GeoJSONのPolygonをマージしたい第2回です。

前回、純粋な多角形の統合ではなくて、領域が被らない多角形の統合になるのでグラフ問題として解くことができるという説明をしました。
今回はどうやって問題を解くか深く考えてみます。

二つの区域の統合

まずは2区域。
グラフの例はこうです。

対応するGeoJSON（の一部）の例はこう。

↓統合前

{
  "type": "Feature",
  "properties": { "name": "青市" },
  "geometry": {
    "type": "Polygon",
    "coordinates": [ 
      [①, ②, ③, ④, ⑤, ⑥, ①]
    ]
  }
},
{
  "type": "Feature",
  "properties": { "name": "緑市" },
  "geometry": {
    "type": "Polygon",
    "coordinates": [ 
      [⑦, ⑧, ⑨, ⑩, ⑥, ⑤, ⑪, ③, ②, ⑦]
    ]
  }
}

↓統合後

{
  "type": "Feature",
  "properties": { "name": "赤県" },
  "geometry": {
    "type": "Polygon",
    "coordinates": [ 
      [①, ②, ⑦, ⑧, ⑨, ⑩, ⑥, ①],
      [③, ④, ⑪, ③]
    ]
  }
}

必要な処理をまとめます。

1. 共通するエッジを削除する。（②-③, ④-⑤, ⑤-⑥）
2. 1によって不要となったノードを削除する。（⑤）
3. 残っているエッジを辿り、閉路を作る。
4. 閉路が2つ以上ある場合、coordinatesの順番は外の境界にあたる閉路が最初、穴にあたる閉路が2番目以降にする。

1～3までは特に問題無いと思います。問題は4番目の処理。
単にノード番号を見ても関係は分からないので、位置的な情報を用いる必要があります。
「エッジが時計回りになっている閉路が穴」になります。

エッジが時計回りかどうかは、凸になっている点を抽出して前後の線の角度がどちらを向いているかで判断できます。
凸になる点は、多角形に外接する長方形を考えて、長方形の辺上にある点を探せば良いです。具体的には、「上辺に接するもっとも左の点」とかを探せば良いです。角度の向きは外積で出せますね。

三つ以上の区域の統合

二つの区域を統合できれば、あとはそれを繰り返せばいくらでも統合できるんですが、一度に沢山の区域を統合しようとした場合、一気にやってしまうほうが高速です。
ただし、GeoJSONのPolygonは一つの多角形しか記述できないので、ある区域に離れ小島がある場合は、そもそも一つのFeatureになりません。
たとえば以下のような場合、統合したあともFeatureは二つになります。このとき、「穴」はそれぞれ適切なFeatureに定義しないといけません。

国土数値情報のデータの場合、島のある区域には同一のpropertiesを持つFeatureが複数定義されています。

そのため、複数の区域を一度に統合するには、以下の手順を踏むと良いと思います。

1. propertiesを一意に識別できるようにIDを割り振る
2. エッジを共有するIDを記録し、実際に統合できるIDの集合を作る
3. 2で作ったIDの集合ごとに1つのFeatureへ統合する

つづく

というところでそろそろ長くなってきたので実践編へ続きます。