プログラミング

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つの多角形だったものがマージによって外の境界と穴に分かれたとき、「どちらが外か」を把握しなきゃいけない点です。

つづく

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

-プログラミング

執筆者:


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

  2. […] 前々回と前回で問題を整理して、ようやく実践編です。 […]

comment

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

関連記事

no image

Unityでメッシュをさわるノウハウ

ヒマなので覚書。ウラを取っていない経験則なので話半分で読んでください。 あと、3Dの基本概念とUnity固有の話の区別が付いていないのでごめんなさい。 もくじ1 Meshクラスの基本2 ポリゴンの読み …

no image

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

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

no image

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

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

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

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

no image

UnityのCompute Shaderに線分と三角形の衝突判定をさせる

はじめてCompute Shader使ってみた。でもあまり性能は出ないのでただの失敗の記録です。 まず元のアルゴリズムはコレ。 線分と三角形の当たり判定 – 富士見研究所 で、これをまず三角形の表裏問 …