経路情報に空間インデックスを張る手法をもうちょっと真剣に考えたい。

やりたいこと

前回は "Plus Code矩形" ごとにディレクトリを用意し、その矩形に属するサンプルを1つの.jsonファイルに纏める方向性とした。ただ、これだと徒歩みたいに移動速度が遅いケースでも、ファイルがかなり細切れになってしまうという問題があった。

また、地図をズームアップした際に、サンプリング点が一切画面に入っていないケースでは航跡が描画されないという問題もある。

Plus Code矩形

Google maps等で利用されるPlus Codeは地球表面の座標に文字列を割り当てている。この文字列 https://plus.codes/8Q7XJRCQ+QM8 が表現する領域の矩形をここではPlus Code矩形と呼ぶ。

このサイトでグリッド表示をOnにすると概念がわかりやすいかもしれない。

航跡を固定長のセグメントに分割する。こうすることでファイルの数は単純に時間に比例することになり、移動速度に依存しなくなる。
使うPlus Codeを可変長にする。Plus Codeは付近が前方一致するようにデザインされているため、"見えている範囲にマッチ" するためには単純な前方一致検索で良い。このため、インデックスに使用するPlus Codeを固定長にする必要性はない。
サンプル間を適当に補完し、セグメント内で参照されるPlus Code矩形を連続させる。

このためにはアルゴリズムを2つ考える必要がある。

... というか、まず "適切なPlus Code矩形サイズ" を定義する必要があるのか。

Plus Code は 20進数の数列の数字をアルファベットに置き換えたもの となっている。

で、エンコーディングは先頭10ケタと残りで異なっているが、とりあえずここでは先頭10ケタのみ考える。実用上は10ケタで表現できるサイズ(1/8000度、十数メートル四方)よりも地図をズームインするケースはあまり存在しないと考えられるため。

先頭10ケタについては、 UuUuUuUuUu のようなコードだった場合、 UUUUU が経度(longitude、北を上にした場合の縦) uuuuu が緯度(latitude、横) となる。

例えば、日本付近のコードを横方向に見ると 8J 8M 8P 8Q ... のようになる。先頭は経度であるため、横方向に移動しても値は変わらない。

動的サイジングの恩恵が得られるケースがあまり無さそうなので、一旦インデックス対象のPlus Codeを固定長にすることを考える。こうすることで、問題は:

となる。この場合は単に直線を引くだけだから算数の問題になる。現在のGPS航跡の記録間隔は1sだから、時速90kmで移動すると90000メートル/60/60 = 25メートル。これは10ケタのPlus Code矩形としても数個だから許容範囲なのではないか。

アルゴリズムは簡単、かつ隣接判定も不要となる。