問い

かなりの分量とファイル数がある地理空間情報を独自のメッシュに切り分けたい。

第一回答: おやめなさい

独自のメッシュに切り分けたい、というのは、顧客が本当にやりたかったことではないことが多いです。

例えば、データを処理しやすい単位に分割したいということであれば、既存のよくできたツール、例えば Tippecanoe で、現在最良の知恵が反映された方法でベクトルタイルに分割するのが正しい答えになります。

ベクトルタイルというのは、いわばジュラルミンのようなものです。そういったものが既に市場で売られているわけです。それがある中で独自のメッシュに切り分けるというのは、ジュラルミンを隣に見ながら、布張りを始めるようなものです。

例えば、そのメッシュでデータを集計したいから切り分けるのだ、という場合には、もっと良い方法があります。ベクトルタイルに切り分けた上で、集計プログラムのほうにそのお望みのメッシュを持っておいて、集計の処理を行う中でメッシュでジオメトリを切るのです。

第二回答: やるなら MapReduce 的に

それでもどうしてもやりたい、やらなければならないのであれば、最良の方法は MapReduce です。

幾何をシリアルに読みながら、一つの幾何をメッシュで切ります。多分、１つのままだったり、4つにわかれたり、もっと多数に分割されたりするでしょう。その分割された幾何に対して、メッシュの識別子をキーとして振るのです。これが、MapReduce の Map 処理です。

Map されたデータの列が、キーによってソートされ、同じキーに対応する幾何がまとめられます。そのまとめられた塊が、メッシュごとのデータです。それを出力すれば終了。

自分の手で出力ファイルを開けたり閉じたりすると、データ量が小さい場合にはまあそれほど問題になりませんが、データ量が多い場合にはどんどん遅くなります。

騙されたと思って、汎用の MapReduce フレームワークのシンプルなやつを使うと良いです。

具体的に?

私だったら、いまならが言語処理系に Node.js を選定して、幾何データの切り分けをするのに turf.js を使うと思います。BBOX をとって、かかるメッシュを算出して、それぞれのメッシュごとにその幾何を切って、メッシュ番号と幾何のペアをアウトプットする。それが Map 処理になります。

MapReduce のフレームワークは、Node.js で選んだことはありませんが、2014年の私によると、次のいずれかを選ぶと思います。

UNIX の sort
Hadoop Streaming

第三回答: それ、ベクトルタイルでできるはず

第二回答のように、素直に MapReduce のコードを書き始めるのではなく、まずは Tippecanoe でベクトルタイルに変換した上で、タイルから地物を取り出してタスクを実行するという最もひねくれた方法です。

仕事の最終目的が仮に独自のメッシュに切り分けるということだった場合、それぞれのメッシュ番号ごとに、それが当たるタイルを適当な順番に取り出して、その中から地物を取り出して、メッシュ境界で切って、切れた地物を元どおりにして、出力ファイルに書き出すという方法です。

こうすると、あなたが書くコードは、タイルからファイルを書き出す部分だけになるので、MapReduce のような概念を理解する必要がありません。

考察

タイル分割というのは、処理の順番を間違えるとすごく時間がかかるのです。そういう面倒臭いことを全部引き受けてピカピカに磨き上げた Tippecanoe というツールがオープンソースで既に世の中にあります。車輪を再発明する必要はありません。

第二回答というのは、車輪をできるだけいい形で再発明する方法で、第三回答というのは既成の車輪を組み合わせて車輪を作る方法ですね。第三回答の方法が、もう少しよく試されるべきだと思います。

第三回答のアプローチが現実的になったのは、ogr2ogr が GeoJSONS をサポートするようになった Version 2.4.0 以降です。これから、だんだんとよくなっていくでしょう。

でも、本当に正しい回答は、第一回答である場合が多い気がします。

理屈は分かったしもういいから、君が結果をすぐに出してみろ、と言われたら、今ならどうするでしょう。多分、データが20GBを超えない程度であるのであれば、第二回答の MapReduce で、 MapReduce エンジンには UNIX の sort を使うと思います。 sort の底力を見てみたいと感じるからです。