quadKeyを使って、地図上に表示するマーカーの情報を適切に取得しよう

この記事はHERE Advent Calendar 2022の19日目の記事です

はじめに

HEREでは、自分がどういう表示をしたいかによって、地図上で何かを表示するとき様々な方法があります。特定の状況において、マーカーを使いたいと言う方はいらっしゃるのではないでしょうか。例えば、お店の場所をマーカーで示したり、シェアサイクルのステーションをマーカーで表示したりですね。特に検索などを組み合わせて、動的に地図上に表示するオブジェクトを変えたいときは、選択肢として考える方も多いかもしれませんね。

HEREの表示は確かに高速（個人の感想ですが、以前使っていたGoogle Mapより早いと思います）なのですが、多くのマーカーを建てたい場合に、考慮した方が良いこともあります。具体的には、マーカーで示したい位置のデータがDB上に保存されていて、APIを用いてマーカーで示したい位置のデータを取得し、HEREに渡して、地図上に表示するような場面を想定した場合についてです。

考慮した方が良い点

• 全マーカーのデータをDBから取得する必要があるか
  • 例えば、北海道の地図を表示するのに、沖縄のデータをDBから取ってくる必要があるか

• 取得したマーカーのデータを全てHEREに渡す必要があるか
  • 今、フォーカスされているのは、札幌周辺なのに、帯広のデータをHEREに渡す必要があるか

以降では、上記に対して、効率的にマーカーを立てることを考えていきます。

確認環境

フロントエンド

• vue.js 2.6.14
• quadkey 0.0.1

バックエンド

• typeorm 0.3.11
• nesyJs 9.2.1

私は、Vue.jsに組み込んで、HEREを試しました。チュートリアル通りに進めると、簡単に組み込めました。

色々な方法がありますが、今回は、quadKeyを使った方法を解説します。

quadKeyとは何か

地図を４等分し、４等分した、それぞれを、更に4等分しと、これを続けていくと、どの矩形の中にいるかが、４等分する際の、0, 1, 2, 3のどこにいるかで表現できる。この考えに基づいて、位置の矩形を４進数で表現したのが、quadKeyで、Microsoftが提唱しました。

quadKeyのメリット

• 親要素や、兄弟要素との関連がわかりやすい。
  • 130なら、親は、13と、最後の桁を除外した値
  • 130なら、兄弟は、131, 132, 133と、最後の桁以外が一致する値
• 共通部分が簡単に探せる
  • 11120と、11132なら、両方、111の子孫（111の区画内に、両方存在する）
• 桁数が1桁増えると、矩形の1辺が1/2とわかりやすい
  • 11120, 11121, 11132なら、11120と11121の2倍程度、11132は他の2つと離れている可能性がある（各区画のどこにいるかなので、2倍固定にはならない）

quadKeyの実装

Javascript用のライブラリーが公開されているので、そちらを利用しました。

上記をyarn add quadkeyなどで追加したら、下記のように、簡単にquadKeyを求められるようになります。

import * as quadKey from 'quadKey';

// quadKeyの計算確認
console.log(quadkey.toQuaKey(43.068564, 141.3507138));

他の言語もライブラリーが公開されていたり、Microsoftのページで、C#の実装が公開されているので、参照して、それぞれの環境用に準備することはそれほど難しくないかと思います。

位置情報の格納テーブル例

今回は、以下のテーブルに、場所の情報を格納して、確認しました。

CREATE TABLE "landmarks" (
    "id"                INTEGER PRIMARY KEY AUTOINCREMENT NOT NULL,
    "name"              VARCHAR(20), /* 場所の名前 */
    "description"       TEXT, /* 場所の説明 */
    "latitude"          DOUBLE(9, 7), /*　緯度 */
    "longitude"         DOUBLE(10,7), /* 経度 */
    "quad_key"          DECIMAL(24), /* quadKeyの保持 */
    "telphone_number"   VARCHAR(15), /* 場所の問い合わせ電話番号 → マーカーの表示に使用 */
    "url"               TEXT, /* 場所のホームページのURL → マーカーの表示に使用 */
);

緯度、経度、quadKeyを保持できるテーブルであれば、問題ありません。DBで、quadKeyを保持することで、場所の検索に、quadKeyを活用します。

DBからちょうど良いマーカーのデータを取得する

現在、表示している地図の領域を取得する

上記のように考えると、

フロントエンド

1. 地図の境界の左上、右下の緯度経度を取得
2. 2つの点を内包するquadKeyを計算
3. バックエンド側に、quadKeyを使って、位置情報の取得のリクエスト

バックエンド

1. 送られたquadKeyから、前方一致する位置情報のデータを取得
2. レスポンスとして返す

フロントエンド側の実装

  methods: {
    initializeHereMap() { // Hereのマップのレンダリング

      const mapContainer = this.$refs.hereMap;
      const H = window.H;
      // プラットフォーム オブジェクトからデフォルトのマップ タイプを取得する
      let maptypes = this.platform.createDefaultLayers();

      // マップ オブジェクトをインスタンス化し、表示
      this.map = new H.Map(mapContainer, maptypes.vector.normal.map, {
        zoom: 13,
        center: { lat: 43.068564, lng: 141.3507138 }, // 札幌駅周辺の緯度・経路
      });

      // 後の初期化処理は、必要に応じて。
    }
  }

  // マップ境界の上の緯度の取得
  private function getMapBoundTop() {
    return this.map.getViewModel().getLookAtData().bounds.getBoundingBox().getTop();
  }

  // マップ境界の下の緯度の取得
  private function getMapBoundBottom() {
    return this.map.getViewModel().getLookAtData().bounds.getBoundingBox().getBottom();
  }

  // マップ境界の左の経度の取得
  private function getMapBoundLeft() {
    return this.map.getViewModel().getLookAtData().bounds.getBoundingBox().getLeft();
  }

  // マップ境界の右の経度の取得
  private function getMapBoundRight() {
    return this.map.getViewModel().getLookAtData().bounds.getBoundingBox().getRight();
  }

  // 表示している地図の境界の上の緯度、左の経度を取得し、返す
  private function getMapBoundTopLeft() {
    return {
      lat: this.getMapBoundTop(),
      lng: this.getMapBoundLeft(),
    }
  }

  // 表示している地図の境界の下の緯度、右の経度を取得し、返す
  private function getMapBoundBottomRight() {
    return {
      lat: this.getMapBoundBottom(),
      lng: this.getMapBoundRight(),
    }
  }

  // 表示している地図の境界を内包する矩形のquadKeyを取得する
  private function getQuadKeyContainedMapBound() {
    const mapTopLeftQuadKey = quadKey.toQuaKey(this.getMapBoundTopLeft());
    const mapBottomRightQuadKey = quadKey.toQuaKey(this.getMapBoundBottomRight());
    
    // 2つのquadKeyの一致するところを取得する
    const quadKeyLength = String(mapTopLeftQuadKey).length;
    for (let index = quadKeyLength; i >= 0; i--) {
      const pattern = String(mapTopLeftQuadKey).substr(0, index);

      if (String(mapBottomRightQuadKey).startsWith(pattern)) {
        return pattern;
      }
    }
  }

  // APIをコールする処理

バックエンド側の実装（Repository部分）

import { Repository, EntityRepository, Like } from 'typeorm';
import { Landmark } from '../entities/landmark.entity';

@EntityRepository(Landmark)
export class LandmarkRepository extends Repository<Landmark> {
  /**
   * @param quadKey
   */
  public async findByQuadKey(quadKey) {
    return await this.find({
      where: { quadKey: Like(`${quadKey}%`) },
    });
  }
}

HEREにちょうど良いマーカーのデータを渡す

APIで取得したマーカーの中から、描画している領域の境界内に存在するマーカーだけを絞り込んで、HEREでマーカーを立てる

フロントエンド側の実装

  
  public function addMarkersToMap() {
    const inDisplayAreaMarkers = this.markers.filter((marker) => {
      // マーカーの緯度・経度が境界の中
      if (marker.lat <= this.getMapBoundRight()
        && marker.lat >= this.getMapBoundLeft()
        && marker.lng <= this.getMapBoundTop()
        && marker.lng >= this.getMapBoundBottom()
      ) {
        return marker
      }
    });

    for (const inDisplayAreaMarker of inDisplayAreaMarkers) {
      // 既に描画済みのマーカーは新規で追加しない、描画済みではない差分は、マーカーを立て、描画済みに記録
      if (this.drawnMarker.indexOf(inDisplayAreaMarker) == -1) {
        const marker = new H.map.Marker({
          lat: inDisplayAreaMarker.lat,
          lng: inDisplayAreaMarker.lng,
        });
        this.map.addObject(marker);
        this.drawnMarker.push(inDisplayAreaMarker);
      }
    }
  }

上記に、イベントハンドラを組み合わせると、良い感じに、地図の表示の変更に合わせて、マーカーが新規で立ちます

    // ドラッグ処理の終了時に、境界を確認し、マーカーの差分を立てる
    map.addEventListener('dragend', function(evt) {
     this.addMarkersToMap();
    }

quadKey使わずに、最初から緯度・経度の比較で良いのでは？

HEREに渡すところで、quadKey使ってないじゃんと思われた方多いと思います。quadKeyはその性質上、描画領域と、ピッタリ一致する矩形を取ってくるとかは苦手です。どんどん小さくしても、点や線ではなく矩形として残るためです。ただ、タイルを埋めるように描画領域に、ほぼほぼ一致するquadKey群を取ってくることは可能です。でも、それって、聞いてるだけでもすごい面倒くさいですよね。

では、quadKeyを使わずに、最初から緯度・経度の比較でDBからもデータを取得すれば良いのではと思われた方もいるかもしれません。もちろん、それも可能です。でも、quadKeyを使う利点もあります。quadKeyだと、1つの条件式で済むので、DBによっては、データの取得が楽になるのもありますが、実装面のメリットもあるのです。特に、ユーザが地図の倍率を変えられたり、描画している領域を変えられるようなサービスの場合は、quadKeyの方が計算が楽なことがあります。

quadKeyの近傍計算の理論

例えば、quadKeyの場合、近傍の計算が楽なため、表示領域が左に動きそうなときに、隣接する左の矩形のデータを簡単に取得できます。

最初、これを知ったとき、個人的には感動しました。

上記は、レベル4、16 × 16の場合の各、quadKeyの値です。

適当な横一列をとってきます。

0220, 0221, 0230, 0231, 0320, 0321, 0330, 0331, 1220, 1221, 1230, 1231, 1320, 1321, 1330, 1331

このままだと、規則性が無いように見えますよね。それぞれ、２進数に変換してみましょう。

101000, 101001, 101100, 101101, 111000, 111001, 111100, 111101, 1101000, 1101001, 1101100, 1101101, 1111000, 1111001, 1111100, 1111101

このままだと、少しわかりづらいので、縦並びにして、右寄せします。

 101000
 101001
 101100
 101101
 111000
 111001
 111100
 111101
1101000
1101001
1101100
1101101
1111000
1111001
1111100
1111101

各２進数の、右から見た際の、偶数番目の桁と、奇数番目の桁に注目してください。偶数番目の桁は、右から2番目が0、右から4番目が1、右から6番目が1で、全て、一致していますよね。更に一致しない奇数番目を取り出してみると、何だか、規則性が見えてきませんか

 101000     0 0 0    000
 101001     0 0 1    001
 101100     0 1 0    010
 101101     0 1 1    011
 111000     1 0 0    100
 111001     1 0 1    101
 111100     1 1 0    110
 111101     1 1 1    111
1101000   1 0 0 0   1000
1101001   1 0 0 1   1001
1101100   1 0 1 0   1010
1101101   1 0 1 1   1011
1111000   1 1 0 0   1100
1111001   1 1 0 1   1101
1111100   1 1 1 0   1110
1111101   1 1 1 1   1111

更に、先ほど、取り出した奇数番目の２進数を１０進数に変えてみましょう

 101000     0 0 0    000   0
 101001     0 0 1    001   1
 101100     0 1 0    010   2
 101101     0 1 1    011   3
 111000     1 0 0    100   4
 111001     1 0 1    101   5
 111100     1 1 0    110   6
 111101     1 1 1    111   7
1101000   1 0 0 0   1000   8
1101001   1 0 0 1   1001   9
1101100   1 0 1 0   1010  10
1101101   1 0 1 1   1011  11
1111000   1 1 0 0   1100  12
1111001   1 1 0 1   1101  13
1111100   1 1 1 0   1110  14
1111101   1 1 1 1   1111  15

と、このように、それぞれ、スタートを0として、左から何番目かを表しています。
そのため、例えば、上の表にないレベル１５のquadKey、012010011113101とかを考えてみましょうか。
２進数に変換すると、110000100000101010111010001です。

110000100000101010111010001   // ２進数に変換
1 0 0 1 0 0 1 1 1 1 1 1 0 1   // 奇数番目だけ取得
9469                          // １０進数に変換

012010011113101は、レベル15において、スタートを0として、左から9469番目ということのようです。
ということは、左隣は9468番目で、右隣は9470番目ですよね。
左隣の具体的なquadKeyを考えましょう

9468
10010011111100                 // ２進数に変換
1 0 0 1 0 0 1 1 1 1 1 1 0 0    // 奇数番目に配置

ここで偶数番目は、012010011113101の２進数 110000100000101010111010001と同じはずです。

110000100000101010111010001    // 元の012010011113101の２進数
 1 0 0 0 0 0 0 0 0 1 0 0 0    　//  偶数番目だけ取得

後は、組み合わせるだけですね

1 0 0 1 0 0 1 1 1 1 1 1 0 0    // 奇数番目に配置
 1 0 0 0 0 0 0 0 0 1 0 0 0    　 //  偶数番目だけ取得
110000100000101010111010000    // 求めるquadKeyの２進数
12010011113100　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　// ４進数に変換
012010011113100　　　               // ゼロパディングで比較対象と桁を揃え求めるquadKeyに

縦方向に関しては、２進数にして、奇数番目だけを取得すると、上から何番目か求められます。

説明が大分長くなりましたが、ライブラリで、この辺りの計算用の関数が用意されていると、
簡単に、今のquadKeyの隣が求めらます。

quadKeyを用いたクラスター化

表示倍率に合わせて、複数のマーカーを集約してクラスターにしたい場合も、quadKeyなら簡単にできます。
上記の近傍計算から、周囲の8つのquadKeyの矩形よりも、マーカーの数が多いquadKeyの矩形を代表にしていけば良いのです。

quadKeyで表せる矩形内に、DB上の位置データが含まれるかは、前述の通り、前方一致で、簡単に矩形に含まれる位置データのみを取得できるので、この辺りの計算を行いたい場合にもquadKeyは、有効活用できます。

最後に

HEREを使ってみて、かなりパワフルなので、マーカーをそこまで立てない場合は、この記事の工夫とかは不要だなと思います。また、大量のマーカーを立てたい場合は、カスタムレイヤーを使うような他の方法もあって、こういう工夫が必要かどうかは、サービスにもよるかなと思います。例えば、マーカー自体も動的に動くような、動体を地図上に表示したいとか、予約サイトの絞り込みのように、リアルタイムで位置以外の条件がどんどん変わってく場合に、位置を絡めて検索させたいとかですね。

結構、ニッチかなとは思いつつ、参考にしていただければ幸いです。あと、下の参考記事、quadKeyの近傍について書いてある文献が少なかったので、とても助かりました。ありがとうございます。

参考記事