Arduinoでquadkeyを生成する

Arduino上でQuadKeyを使いたかったので、既存のライブラリを調査して移植した。

QuadKeyって？

QuadKeyはMicrosoftが開発した位置情報ハッシュアルゴリズムで、Bing Mapsのタイル指定に使われている。文字列で矩形を表現することができ、先頭一致でマッチングをかけることができるため、位置情報のクラスタリングなんかに便利。

• Tile Coordinates and Quadkeys

類似技術として、ジオハッシュやジオヘックスなどがある。

サンプルコード

以下はArduinoスケッチの一部。 latlon_to_quadkey() にGPSなどから取得した緯度経度と任意のズームレベル（町単位なら 17 くらいがおすすめ）を渡すと、QuadKey文字列を含むStringオブジェクトを返します。

手元ではちゃんと動いてそうに見えますが、にわかArduinoプログラミングなので動作は保証しません。

#include <math.h>

/**
   以下を参考に実装
   https://cttr.jp/2019/04/10/post-453/
   https://github.com/buckhx/QuadKey/blob/master/quadkey/tile_system.py
*/
struct PixelXY {
  int x;
  int y;
};

struct TileXY {
  int x;
  int y;
};

double clip(double val, double minVal, double maxVal) {
  return min(max(val, minVal), maxVal);
}

String latlon_to_quadkey(double lat, double lon, int zoom_level) {
  // geo to pixel xy

  // normalize values
  lat = clip(lat, -85.05112878, 85.05112878);
  lon = clip(lon, -180.0, 180.0);

  double x = (lon + 180) / 360;
  double sin_lat = sin(lat * M_PI / 180);
  double y = 0.5 - log((1 + sin_lat) / (1 - sin_lat)) / (4 * M_PI);
  int map_size = 256 << zoom_level;
  int pixel_x = clip(x *  map_size + 0.5, 0, map_size - 1);
  int pixel_y = clip(y *  map_size + 0.5, 0, map_size - 1);

  PixelXY xy = {pixel_x, pixel_y};

  // pixel xy to tile xy
  TileXY tile = {xy.x / 256, xy.y / 256};

  int tile_x = tile.x;
  int tile_y = tile.y;

  String quadkey = "";
  for (int i = 0; i < zoom_level; i++) {
    int bi = zoom_level - i;
    int digit = 0;
    int mask = 1 << (bi - 1);

    if ((tile_x & mask) != 0 ) {
      digit += 1;
    }
    if ((tile_y & mask) != 0) {
      digit += 2;
    }
    quadkey += String(digit);
  }

  return quadkey;
}

例

latlon_to_quadkey(35.677730, 139.754813, 17) の実行結果。

※こちらのサイトで確認

参考

• 【C++】緯度経度からquadKey生成
• QuadKey (Python2用QuadKeyライブラリ)