プログラミング

GeoJSONで市町村境界をマージして都道府県境界にしたい(その1)

投稿日:2019年10月4日 更新日:

前回の続きで、国土地理院の「国土数値情報」っていうオープンデータで遊んでいます。独立した記事なので前回のは読まなくても良いです。

やりたいこと

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

問題の整理

「市町村の境界を統合して、都道府県の境界にする」ことです。
ここでたとえば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つの多角形だったものがマージによって外の境界と穴に分かれたとき、「どちらが外か」を把握しなきゃいけない点です。

つづく

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

-プログラミング

執筆者:

関連記事

no image

Google Apps Script(GAS)で自宅サーバーの死活監視をする

前置き 自宅サーバー使ってますか? 最近もう流行らないかな、と思ったらRaspberry Piの流行で機器も電気代も安価に組めるようになったりして、地味に持っている人も多いんじゃないかな、と思ってます …

no image

[C言語]スペースを大量に入れるとバグが直るコードを書いてみた

↓こういうツイートがバズっていたので、実際に組んでみた。 修士の頃、授業の課題でC言語書いてる時にどうしても謎のエラーが出て困っていた。それを見たSE経験(金融系)がある社会人大学院生の同期の女性が「 …

国土地理院の地図データをUnityで読みたい(願望)

なんかgoogleのAdSense通ったんで有益な情報載せないとなって。 国土地理院のオープンデータ 国土地理院が公開している(正確には国土地理院のデータを利用して国土交通省国土政策局国土情報課が公開 …

no image

例え話をしないC言語のポインタの説明

もくじ1 まえおき2 Hello, Worldより簡単に2.1 サンプルコード2.2 変数の置き場所2.3 変数が入っているところを見てみる3 C言語とメモリ3.1 変数cの「まわり」を見てみる3.2 …

no image

プログラミングとアルゴリズムのはなし

みんなー!小学校でプログラミングの授業がはじまるよー!! プログラミングってなんだろう? プログラミングって、コンピューターに「○○をしなさい」って命令して、なにかの問題を解いたり、ゲームをつくったり …