quadKey方式での近傍検索

概要

地理情報から近傍検索をする方法は様々。
今回はシンプルに文字列検索で近傍検索の絞り込みができるような仕組みについて調査。

他の選択肢

GeoHash
- 緯度経度のビットを組み合わせて作られる
- Base32文字列によって構成される（例：57.64911,10.40744 -> u4pruydqqvj）

quadKeyの性質

世界地図を分割し、どのエリアにいるかで決まる
4進数文字列で表現される（例：13201301)
20段階の精度で利用ができる（GeoHashより細かいらしい）
- quadKeyの桁数とレベル数が一致
- 世界地図を4つに分割したのがレベル1（0,1,2,3）、レベルが1上がると各エリアが同じように4分割（00,01,02,03,10,11...33）される
quadKey文字列の先頭は親要素を完全に含んでいる（検索に利用しやすい）
- 133（1の子の13の子）
ベース（https://ja.wikipedia.org/wiki/Z階数曲線）

quadKeyの作り方

quadKeyのレベルに応じたサイズの仮想マップを作成。
レベル（精度）が高いほどピクセル数が増える。

緯度経度からマップの位置をポイントする。（ピクセルのXY座標指定）
ピクセルの所属するquadKeyエリアに所属するのかを判定してエリア座標を取得する。

それぞれ2進数にする。桁数はLevelXのXとし、不足する分は上位桁を0パディングする。
3 -> 011
5 -> 101

YとXを最上位桁から1桁ずつ値を取得し、交互に先頭から埋めていく。
quadKey(2進数) = 100111

次にこれを4進数にする
quadKey(4進数) = 213 -> "213" (文字列のquadKeyとして利用できる)

近傍検索

quadKeyで近傍検索をする場合にまずquadKeyで絞り込みをおこなうことになる。
ただしエリア境界が近い場合に隣のエリアにある近傍情報が拾えない問題があるので、
検索対象に周囲8エリアも含めるのが一般的。
周囲8エリアの求め方は、検索quadKeyからエリア座標の特定（前章の[3,5]にあたる）、
8エリアの座標を求めてそれぞれのquadKeyを作成する。

実際にXkm以内という条件や、近い順ソートなどはこれだけでは行うことができない。
空間インデックス非対応DBで利用する場合には、一旦これで絞り込んでから、距離順で処理となるのだと思う。

コードでの記述

エリア座標からquadKey文字列を作る場合の例を取り上げる。

レベルごと（quadKeyの1文字ごと）に処理する。
1文字は4進数なので、2進数だと2桁分に相当し、00、01、10、11の4パターンになる。
Y座標が4^1桁、X座標が4^0桁となるので、以下のような求め方ができる。

public static String tileXYToQuadKey(PointInt tile, int levelOfDetail) {
        StringBuilder quadKey = new StringBuilder();
        for (int i = levelOfDetail; i > 0; i--) {
            char digit = '0';
            int mask = 1 << (i-1);
            if ((tile.getPointX() & mask) != 0) {
                digit++;
            }
            if ((tile.getPointY() & mask) != 0) {
                digit++;
                digit++;
            }
            quadKey.append(digit);
        }
        return quadKey.toString();
    }

bingのblogよりこれをJavaに置き換えたもの。