自由研究

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

MagicaVoxelでUnity用の人間モデルを作ろう(東北ずん子配布もあるよ)

もくじ1 概要1.1 目標1.2 手順1.3 作成モデル2 MagicaVoxel2.1 パーツ分割2.2 出力3 Blender3.1 インポート3.2 モデルの初期調整3.2.1 重複する頂点の削 …

no image

あみだくじはどれぐらいランダムか

あみだくじ。 紙とペンがあればすぐに作ることができるお手軽な抽選方法として知られています。 なにか物事を決めたいとき、あみだくじを使うという人も多いのではないでしょうか。 ふと思ったんですが、あみだく …

no image

MagicaVoxelとDMM.makeでオリジナルフィギュアを作ろう

もくじ1 読まなくても良い前書き2 概要3 MagicaVoxel3.1 フィギュアの自立の有無3.1.1 基本的に自立しません3.1.2 どうしても自立させたいなら3.2 折れる可能性を考慮する3. …

no image

FIDOについてなるべく平易にまとめてみる

この記事は情報系の学生ぐらいの知識を想定しています。なるべく平易に書きますが、わからないことがあったら自分で調べながら読んでください。 話の枕 こないだ、Pixel 3aというGoogle製のスマホを …

no image

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

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