[OSM-ja] 森林ポリゴン切断問題

Hiroshi Miura(@osmf) miurahr @ osmf.jp
2013年 12月 2日 (月) 12:14:03 UTC


三浦です。

数学チックな話題です。
(正確には、Computational Geography: 計算幾何学の話題です)

先日の赤羽マッピングパーティの際に、林さんから、次のような
相談をもらいました

以下の図のように、マルチポリゴンAがあった時に、それを
ポリゴンA、Bに分割したとします。

https://dl.dropboxusercontent.com/u/90779460/Forest_polygon.png

このときに、マルチポリゴンAのINNERであったCの部分がA,Bの
どちらに属しているかを、アルゴリズムで判定するにはどうしたらよいか、
というものです。

森林データが非常に大きい時に分割したいという動機からうまれた課題です。

参考書: 丸善出版 「アルゴリズム設計マニュアル(下)」
S.Sスキーナ著 平田富夫訳 ISBN 978-621-08511-0
246ページの 17章計算機科学 17.7 点位置決定の項目を参照しました。

質問点Q(ここでは、ポリゴンCの内部の一点を任意に選ぶことにします)から、
半直線を任意の方向に引きます。その半直線が、多角形Pの辺を何回横切るかを数えます。
  奇数: 内部にある
  0または、偶数: 外部にある
という判定をします。図の例では、
  ポリゴンAでは、1回ですから奇数、内部にある
  ポリゴンBでは、2回ですから偶数、外部である。
というように判定出来るようです。

さて、このような処理をいちから実装するのは大変です。
そこで、ライブラリが既に有ります。 CGAL(www.cgal.org)がつかえると書籍にもあります。

CGALを実際に使った事例としては、tileman のベースになっている
ライブラリ lua-nginx-osm (https://github.com/miurahr/lua-nginx-osm/)の
poly2luaというユーティリティを見ていただければと思います
https://github.com/miurahr/lua-nginx-osm/blob/master/utils/poly2lua.cpp

この事例では、日本や国々を囲むように設定されたポリゴン(凸凹有り)に対して、
角すべてが凸(0−90度)であるようなポリゴンに分割して返す、という処理を実施しています。
処理そのものは、ライブラリがおこなっているので、呼び出し方の
参考にしてください、という意味です。

林さんや みなさんの参考になればと思います。

三浦



Talk-ja メーリングリストの案内