プログラミング

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

C言語のポインタに関する補足説明

前回、C言語のポインタに関する解説記事を書きまして、そこそこの反響を貰うとともにいくつかの指摘を受けました。 前回の記事では幾つか「ウソではないけど真実と違う」記述がありまして、その点を補足としていく …

no image

ロリポップでSQLite3を使うときはpythonでpysqlite3-binaryだ

このブログはロリポップで運用しています。 公式にSQLite3の使用も許可されていて、モジュール叩けば動くんですがいかんせんバージョンが低い。 確認するとバージョンが3.7.17。なかなかに古いです。 …

no image

“API”をなるべく分かりやすく説明してみる

“API”という言葉が一般にもよく使われ始めています。 しかし、非エンジニアにとっては馴染みのない言葉で、しかも謎の英略語なので、一部の人々からは「APIがなくなった」(=AP …

GeoJSONで市町村境界をマージして都道府県境界にしたい(実践編)

前々回と前回で問題を整理して、ようやく実践編です。 まず実物のリンク貼りましょう。GitHubに上げました。 今回はGo言語で書いてますが、ポイントがいくつかあります。 ちなみに言語としてGoを選択し …

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

GeoJSONのPolygonをマージしたい第2回です。 前回、純粋な多角形の統合ではなくて、領域が被らない多角形の統合になるのでグラフ問題として解くことができるという説明をしました。 今回はどうやっ …