[OSGeoJapan-discuss] ポリゴン処理の話題

[Hiroshi Miura(@osmf)]

OSMFJ　三浦です。


ちょっとした話題を提供すると共に、やりかたが正しいのかどうかの相談を
GISの専門の皆様にさせてほしいです


＜経緯＞
分散タイルサーバを実現するTileMan(*1)プロジェクトで、
 lua-nginx-osm ライブラリ(*2)というのを、コアライブラリとして開発しています。
TileManの機能については、State of the Map 2013(*3)のプレゼンを参照ください。
#関連URLは末尾にあります

この中で、次のような機能を実現しています。

１）　ポリゴン指定した地域をデータとして持っている。
２）　タイルサーバで、タイル要求されたX/Y/Zoomについて、
　　そのタイルが、（１）の地域に含まれているかどうかを判定する。
３）　含まれている場合、タイルを生成する。

地域データは、geofabrikのデータ(*4)を意識しています。

DBとして、特定の地域のデータだけPostGISに持っておいて、タイル要求がきたときに、
それがDBに入っていればレンダリング実施、そうでなければ、アップストリームの
tile.openstreetmap.orgへ要求、みたいな処理(*5)を実現しています。

これは、他の製品でもありそうな機能ですよね。


＜背景＞
さて、上記の処理を行うために、
is_inside_regionという関数(*6)を定義しました。計算速度を上げるために、
簡易なアルゴリズムを採用しました。ポイントは以下です

res = (y1 - y2) * nx + (x2 - x1) * ny + x1 * y2 - x2 * y1

(x1, y1) (x2, y2) は、地域を指定するポリゴンの一辺のベクトル
(nx, ny)は、判定するタイル要求の位置

上記は外積をとっており、全ての辺について判定して、すべて負でなければ、
すべての辺の内側に、判定するタイル要求の位置があることが分かります。

しかし、この判定ロジックには、弱点があり、比較するポリゴンは、かならず
convex polygon (凸多角形）である必要があるのです。


＜本題＞
そこで、たとえば japan.kml (*7)のような凹凸多角形(concave polygon)を凸多面体に分割することにしました。
単純なケースでは、手作業でも可能ですが、複雑になると、手作業では不可能になります。

このような問題は、計算幾何学で研究されていて、素晴らしいライブラリがすでに提供されています。
そこで、CGALを用いて、ポリゴンを複数の多角形に変換し、LUAのプログラムを生成するようなユーティリティプログラム
(*9)を書くことにしました。（GEOSには、該当機能がないみたいでした）

実際に触ってみたい方は、つぎのようにお願いします

$ git clone https://github.com/miurahr/lua-nginx-osm.git
$ cd lua-nginx-osm
$ apt-get install libcgal-dev cmake make
$ make

これでプログラムが生成されるはずです。実行は、

$ utils/poly2lua/poly2lua -t

ここで(-t)をつけると、テストモードで、内蔵の日本の定義データを元に、複数の多角形（緯度経度）を示すデータを生成します。
また、osm/data/*.kml が元データで、 osm/data/*.luaが生成された複数の凸多角形のデータです。

ライブラリがC++用なので、C++でサンプルプログラムを参考に書いたですが、
出来が悪いかもしれません。

☆
☆　で、ここで質問ですが、どうやったら、この生成されたデータが正しく凸多角形であることがわかるでしょうか？
☆

本件は、ブログにかきました(*11)
------------------
（＊１）https://github.com/osmfj/tileman
（＊2）https://github.com/miurahr/lua-nginx-osm
(*3) http://miurahr.github.io/2013-0908-tileman.html#/title
(*4)http://download.geofabrik.de/asia/japan.html
(*5)https://github.com/osmfj/tileman/blob/master/doc/typical_configuration.png
（＊６）https://github.com/miurahr/lua-nginx-osm/blob/master/osm /tile.lua#L81
(*7)https://github.com/miurahr/lua-nginx-osm/blob/master/osm/data/japan.kml
(*8) http://www.cgal.org/
(*9)https://github.com/miurahr/lua-nginx-osm/blob/master/utils/poly2lua.cpp
(*10)https://github.com/miurahr/lua-nginx-osm/blob/master/utils/kml2poly.py
(*11)http://blogs.da-cha.jp/momokuri.php/title-71