背景
ある場所にAR/MRオブジェクトを置きたい場合、画像処理で特徴点とマッチングさせるなどの方法もあるが、シンプルに緯度経度と組み合わせることを考えます。（実装が簡単、バックエンドのデータベースも既存の考え方で作れる、データの持ち方もシンプルなど、PoCとして作成してみる場合やりやすい。）
この場合、どういうデータ構造にしておくと便利かを考えてみます。
階層構造と検索容易性
世界規模での展開を考えた場合、DNSの階層構造のように、地域ごとに分散できるとよいのではないかと考えると、検索のためのKeyに相当するものに階層構造を持たせたいです。また、単純な一致検索で高速・低コストに検索できるものがよいと思われます。
地理空間インデックスを参考にする
多次元座標の検索を高速にするデータ構造やアルゴリズムは、これまで多く考案されています。
3Dゲーム「DOOM」に使われたことで有名なBSP木や、四分木、八分木、R木などです。
ここでは、空間を均等に分けたいことや、2次元を扱えばいいことなどから、Z階数曲線をベースにしたいと思います。
Z階数曲線ベースのインデックスの作り方
まず、緯度経度の値を用意します。これは64ビット精度の浮動小数点です。
それぞれを整数にします。緯度なら、+90して180で割ったものをINTMAXにかけてやればよいです。経度は、+180して360で割ります。
この際、数値誤差が最小になるように計算の順序は気にした方がいいでしょう。また、最後の数値はキャストしてuintにします。
次に、上位ビットから順番に並べていきます。経度の最上位ビット→緯度の最上位ビット→経度の2番目のビット→緯度の2番目のビットというように、交互に順番にならべて、64ビットの整数値を作ります。これが、キーになります。
なお、どちらを先にするかをシステム全体で決めてさえいれば、緯度経度のどちらを先にしてもかまわないかと思います。
ちなみに、この交互に並べる操作ですが、ハードウェアだとロジック回路を組むまでもなく、ラッチと配線でできそうなのでいいのですが、ソフトウェアの場合は少しめんどくさくなります。
個人的に一番楽かなと思うのは、4ビットごとの変換テーブルなどを作って、ORで結合することかなと思います。
なにかいい計算方法があれば知りたいです。
検索クエリの設計
上で作成したインデックスと、どのレベルの検索かを表す数字8ビット(0-255で十分)を合わせて送ってやれば、地球上の2のn乗分割された矩形を指定することができます。
また、ビット列を上位から見ていくことで、空間的な階層構造をたどることになるので、例えば上位Nビットがこのビット列と一致したら、このクエリをXというサーバーに移譲する、といった処理はやりやすいと思います。
検索処理とデータベースの構造について
データベースをKeyの完全一致検索が可能なKVSとして考えます。
検索クエリとして投げられるのは、自分の現在位置の緯度経度を元に計算した上記のインデックス値として、それに対応するValueでその矩形範囲に登録されているURL群をBLOBなどに格納した文字列配列の形などで持っていて、応答すればよいとなります。
まとめ
地理座標とURLを紐付けるサービスのクエリ仕様を検討してみました。大急ぎで書いたので、正確じゃないところとかあるかもしれませんので、気を付けてください。よろしくお願いします。