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

[Yoichi Kayama]

かやまです

以下のようなコードがありましたが、こういうことなのでしょうか？

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
>
-------------- next part --------------
HTMLの添付ファイルを保管しました...
URL: <http://lists.osgeo.org/pipermail/osgeojapan-discuss/attachments/20130915/02c9eb4d/attachment-0001.html>