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

[山手 規裕]

三浦様

山手と申します。

凸多角形かどうかを確認するだけでしたら、多角形の頂点を順に並べて、
全ての隣接する３点が同じ回り順（時計回りか反時計回り）であればいいのではないでしょうか。
的外れな回答でしたらご容赦ください。

山手　規裕
E-mail  ： arctic_tern ＠ mf-atelier.sakura.ne.jp
URL     ： http://mf-atelier.sakura.ne.jp/

On 2013/09/15, at 17:54, Yoichi Kayama wrote:

> かやまです
> 
> 以下のようなコードがありましたが、こういうことなのでしょうか？
> 
> http://www.prefield.com/algorithm/geometry/isconvex.html
> 
> 
> あとは全頂点を与えてConvexfulをかけてできたポリゴンと比較するとか.....
> ちょいと検証してる時間がないので、なんかみつけるきっかけにならんかという情報提供です
> 
> 
> 
> 
> 2013年9月15日 12:43 Hiroshi Miura(@osmf) <miurahr ＠ osmf.jp>:
> 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
> _______________________________________________
> OSGeoJapan-discuss mailing list
> OSGeoJapan-discuss ＠ lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/osgeojapan-discuss
> 
> _______________________________________________
> OSGeoJapan-discuss mailing list
> OSGeoJapan-discuss ＠ lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/osgeojapan-discuss