分散タイルサーバを実現するTileManプロジェクトで、つかうため lua-nginx-osm ライブラリというのを、コアライブラリとして開発しています。

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

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

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

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

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

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

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

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

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

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

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

このような問題は、計算幾何学で研究されていて、素晴らしいライブラリがすでに提供されています。
例えば、アルゴリズム設計マニュアルの下巻には、第17章計算幾何学の中に、１７．１１多角形分割　として解説されており、CGALというライブラリがつかえることが記されている。また、上記の判定についても、17.7 点位置決定で詳細に書かれている。

そこで、CGALを用いて、ポリゴンを複数の多角形に変換し、LUAのプログラムを生成するようなユーティリティプログラムを書くことにしました。

$ 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が生成された複数の凸多角形のデータです。