Quadkeyで範囲検索を行う

2020-01-11

前回の問題点

前回は GeoHash で位置情報を Hash 化し範囲で検索する方法を紹介しました。 問題としては範囲が長方形で精度によって縦長や横長になる、精度によって範囲が大きく異なり扱いづらい点がある等です。 今回紹介する Quadkey は GeoHash よりも精度が高く、範囲も正方形、隣接タイルの取得も容易等より良いアルゴリズムとなっています。 多少不利な点として GeoHash よりもデータ量が増大するという特徴がありますが現代ではそこまで不利になるものでもないでしょう。

Quadkey

QuadkeyについてはMicrosoftの公式が良いでしょう。 BingMapsで採用されているようです。実装も公開されていて移植も簡単です。

前回と同じくサンプルとして東京大学を選びます。緯度が35.716701、経度が139.759556です。 (全国大学データより)

この位置情報を Quadkey で Hash 化(20桁)すると 13300211231002302131 という文字列になります。 GeoHash と同様に 13300211231002302131 -> 1330021123100230213 -> 133002112310023021 …と右桁から短くするすることにより範囲が広くなるという特徴があります これを地図上で表現するとこのようになります

サンプル画像

ちなみに、こちらのサービスで確認した結果です。

Quadkeyの特長

Quadkeyはメルカトル図法を採用しています。 メルカトル図法は地球儀を円筒に投影したものですので、極になるにつれ距離や面積が拡大される、つまりズレが大きくなるという欠点があります。

ただ、メリットもあり地図の常に縦は南北を表し左右も常に東西を表し、緯度経度方向距離も常に正しく保たれます。 極付近のズレが大きいデメリットがありますが、これも極付近にはほぼ人が生活していないため(全く無いわけではありませんが)影響は極少ないです。

もちろんズームレベルが小さく(つまり広域レベル)なれば問題も大きくなりますが、 市区町村レベルのような通常の生活の範囲であれば緯度経度の辺と距離が等しく表現できます。

アルゴリズム

Quadkeyは世界を4分割(4タイル)し、その各タイルを更に4分割する、というのを繰り返していきます。 この分割したタイトルの値を単につなげればQuadkeyとなります。 また、この性質上1文字毎にズームレベルが増えるという仕組みになっています。 つまりこれは4分木その物です。

quadkeyの分割

Bing Maps Tile Systemより引用

この1文字でズームレベルが増えるという特徴の為データベースでは前方一致検索が使えるのもメリットの1つです(GeoHashもここは同様です)。

また、4分木ですので上位との差は4倍ですので、検索時にもデータ量はさほど増えずデータ量の負荷も少なくなります。 また、隣接タイルの取得もさほど難しくもなく検索時には隣接タイトル含めて9タイルを指定して検索するのが常套手法となります。

検索結果の厳密化や近い場所から sort を行いたいという場合には、すでに紹介した距離を求める方法を用いて計算すれば良いでしょう。 この場合にも検索結果のデータ量が少ないという事がメリットとなります。

GeoHashの実装

Microsoftやその他Web上の情報を元に、 Ruby で実装したのがこちらです。 隣接タイトルの取得は省略します。

def clip(val, minval, maxval)
  return [[val, minval].max, maxval].min;
end

def cal_quadkey(lat, lon, level)
  lat = clip(lat, -85.05112878, 85.05112878)
  lon = clip(lon, -180.0, 180.0)

  x = (lon + 180) / 360
  sin_lat = Math.sin(lat * Math::PI / 180)
  y = 0.5 - Math.log((1 + sin_lat) / (1 - sin_lat)) / (4 * Math::PI)
  map_size = 256 << level
  pixel_x = clip(x *  map_size + 0.5, 0, map_size - 1)
  pixel_y = clip(y *  map_size + 0.5, 0, map_size - 1)

  xtile = (pixel_x/ 256).to_i
  ytile = (pixel_y/ 256).to_i

  quadkey = ""
  (0...level).each do |i|
    bi = level-i
    digit = 0
    mask = 1<<(bi-1)

    digit += 1 if (xtile&mask) != 0
    digit += 2 if (ytile&mask) != 0
    quadkey += digit.to_s
  end
  return quadkey
end

puts cal_quadkey(35.716701, 139.759556, 20) #=> 13300211231002302131

ズームレベルと検索について

ズームレベルとタイルの大きさの具体的な値は Bing Maps Tile System に掲載されていますが、 具体的に想像はしづらい場合は maptiler が便利でしょう。

私が確認した所ですと、19で1ブロックほど、16で町レベル、14で区レベル、12で市レベルといったところでしょうか。 データ量次第ですがあまりズームレベルを小さくすると取得データ量が膨大になり実用レベルにはならないと思われます。

実際にローカルの Database ( 1000万件以上 ) で実験をしたところズームレベルが14,5以上になると極端に処理が重くなりました。

対策案としては、ズームレベルの適切な選択、データに対して属性を付け適切なフィルタリングを行う、前方一致ではなくズームレベル毎にカラムを用意する、等が有効でしょう。

ライブラリ

Ruby であれば deg84/quadkey が有名なのでしょうか。 ただ、アルゴリズム系のgemですし作れば終わりなので更新もされていないようです。

Python であれば CartoDB/python-quadkey のようです。

他の言語でもライブラリは見つかるでしょう。また無くても自作という手段も選択肢として十分あり得るでしょう。

まとめ

Quadkey はデータ量の点で多少不利な点はありつつも、 GeoHash よりもより良い選択肢となるでしょう。

また、 Database との親和性が高い点、 Databae に依存しない設計が可能、取得データ量が GeoHash よりも少ない、等も嬉しい点です。

実装も難しくはなく、ライブラリも提供されている場合も珍しくないので開発者にとっても負担が少ないというのも良い点です。

GISを作成する場合には是非検討するのが良いでしょう。