やりたいこと

国土数値情報で提供されている「行政区域データ」は、市町村の境界でデータが分かれていて、都道府県単位の境界が無いんですね。
市町村の境界を統合すれば都道府県の境界にできるよね？ということです。

問題の整理

「市町村の境界を統合して、都道府県の境界にする」ことです。
ここでたとえばA市とB市から成るZ県があるとして、以下のように統合したい。

で、単純に見ると多角形と多角形の統合のように感じるんですが、実は少し簡単。
多角形と多角形のマージだと領域が重複するケースを考慮しないといけないんですが、行政区域はぜったいに領域が重複しない。
つまり以下のようなパターンはありえない。

これで何が簡単になるかというと、ひとつは頂点が増えないって点で、さらにそれによって、問題をグラフ問題に落とし込めるって点です。

つまりやりたいことを整理すると以下のような感じになる。
入力：N個の多角形（それぞれV1～VN個の頂点を持つ）
入力の制約：多角形はそれぞれの領域が重複しない
出力：N個の多角形から重複した辺を排除して統合したM個の多角形（1≦M≦N）

というわけで、問題の第一のポイントは、いかにして重複した辺を探すかって点になります。

「穴」の考慮

重複した辺を探して消すことはあまり難しくないんですが、次に出てくるポイントは「穴が発生する」ってことです。
たとえば以下のような感じ。真ん中の部分は湖か何かだと思ってください。

さらにここでGeoJSONの仕様により、多角形は~~「左手系 (left-hand rule)」~~「右手系(right-hand rule)」で書かないといけない。（2019/10/14追記：右手と左手を取り違えてました。ごめんなさい）
つまり、多角形を頂点の配列で表現するんですが、頂点の順番に制約があって、外側の境界は反時計回り (counterclockwise)、穴の部分は時計回り (clockwise)で記述する必要があるんです。その上で、外の境界と穴の部分は同じ多次元配列に入れなきゃいけない。そして、配列の0番目が外の境界でないといけない。

つまり以下ような方向を保持しなきゃいけない。

マージ後のGeoJSONは以下のようになる。丸数字（①～⑪）は実際には[緯度,経度]ね。
（2019/10/7追記：始点と終点を同じにしなきゃいけないのを忘れてました。すんません。）


"geometry": {
  "type": "Polygon",
  "coordinates": [ 
    [①, ②, ③, ④, ⑤, ①],
    [⑥, ⑦, ⑧, ⑨, ⑩, ⑪, ⑥]
  ]
}

これの何が面倒かって言うと、有向グラフとして管理しなきゃいけないっていう点と、元々1つの多角形だったものがマージによって外の境界と穴に分かれたとき、「どちらが外か」を把握しなきゃいけない点です。

つづく

なんだか話がめんどくさくなっちゃったな、っていうところで今日はおしまいです。
実装とかは次回やりたいと思います。