こんにちは。駅メモエンジニアの id:dorapon2000 です。

約半年前の 6 月 1 日にステーションメモリーズ！（駅メモ！）10 周年を記念してタイムラインと地図の切替機能をリリースしました。大変好評を頂いておりとても嬉しいです。

今回は、その機能の中で毎秒最寄り駅を計算するロジックをどのように実現しているのかについてお話します。様々なスペックの端末で遊ばれているため、可能な限りリソースを節約するような工夫をしました。堅い言い方をすれば、過去の計算情報を使った最近傍探索アルゴリズムを実装しました。

記事中のサンプルコードは TypeScript で記述しています。

2024/11/22 追記：
はてなブックマークでのご指摘ありがとうございます。ご指摘をいただいた「事前計算の時間計算量」と「基準点と現在地の距離が近すぎるとき」の説明部分を修正しております。

誤：事前計算を O(N) で行い
正：事前計算を O(N log(N)) で行い

誤：さて、赤円内には最低で 1 駅以上は存在していることが前提となります。
正：さて、青円内には最低で 1 駅以上は存在していることが前提となります。（ここ以外の文章もここに習って修正）

ソースコードのロジックには変更を加えておりません。

実現したいこと
制約
実装方法
- 全探索
実際に実装したアルゴリズム
まとめ
採用募集案内

実現したいこと

駅メモ！では全国 9000 以上の鉄道駅を扱っている
その中からユーザーの現在地からの最寄り駅を求めたい
最寄り駅は毎秒求めたい

最寄り駅を求めることで、地図上に最寄り駅のマークを表示したいわけですね。

制約

駅メモ！は駅の位置情報連動型ゲームです。アプリ上でボタンを押すことで、最寄り駅へ訪れたことになります。この最寄り駅の計算ロジックはバックエンドに存在します。したがって、バックエンドに API 経由で問い合わせて最寄り駅を取得する方法がまず最初に考えられます。

結論から述べると、この方法は採用しませんでした。駅メモ！で遊びながら鉄道で移動するユーザーはそれなりの速度で動いています。駅が密集している都市部では目まぐるしく最寄り駅が変わります。毎秒最寄り駅を更新したいときに API 通信を都度していてはユーザー体験を損ないそうです。また、通信量やサーバー負荷も気になります。

そのため、フロントエンドで最寄り駅を計算することにしました。フロントエンドでは以下の情報を持っています。

日本全国 9000 駅の座標情報
現在地の座標情報

実装方法

調べてみると最近傍探索アルゴリズムにはいくつかあるようです。

ChatGPT に聞くと KD-Tree という初めて聞くデータ構造で時間計算量を落とす方法を紹介されました。ただ、業務の中で難解なアルゴリズムをあまり採用したくありません。コードレビューもメンテナンスも大変です。データ構造の初期化でそれなりの計算リソースを消費しても、地図をすぐ閉じられてしまい無駄になる可能性もあります。データ構造を保持するためのメモリ使用量についても気になります。

最近傍探索の最もシンプルなアルゴリズムは全探索です。私が実装したアルゴリズムの紹介の前に、一旦全探索のアルゴリズムではどうなるか見てみましょう。

全探索

function getNearestStation() {
  nearestStation = null
  distanceToNearest = Infinity // 現在地から最寄り駅までの距離
  for (station in 日本全国9000駅) {
    if (distance(現在地, station) < distanceToNearest) {
      nearestStation = station
      distanceToNearest = distance(現在地, station)
    }
  }
  return nearestStation
}

毎秒実行(地図上に最寄り駅を描画(getNearestStation()))

シンプルなのであまり説明は不要かと思います。現在地と各駅との距離を計算して、その中で最も短い距離の駅が最寄り駅です。それを毎秒計算します。時間計算量は毎秒 O(N) です。

メリット

わかりやすい

デメリット

毎秒 9000 駅の計算をしていると端末の消費電力が心配

実際に実装したアルゴリズム

このあとの説明がしづらいため、考えたアルゴリズムは「エコ方式」と名付けます。エコ方式は大きく「事前計算」と「最寄り駅計算」の 2 つの工程に分かれます。

事前計算
- 最寄り駅計算の前に事前計算して、適当な時間間隔で再計算する
- 計算時の現在地を基準点 center とする
- center からみた各駅との距離を配列に保存する
- メソッド updateCenter で行う
最寄り駅計算
- 事前計算の結果をもとに毎秒最寄り駅を求める
- 基準点 center を中心として、基準点-現在地間の距離の 3 倍の半径を持つ円内に含まれる駅の中から全探索をする
- メソッド get で行う

なぜこれで最寄り駅計算ができるのか図解します。

図解

事前計算については工程の説明の通りです。現在地 (基準点 center) と各駅との距離を計算し、配列に格納します。配列にはのちの計算の都合上、駅が近い順に入れておきます。

エコ方式もジャンルは全探索ですが、探索範囲をできるだけ小さくしようと試みています。現在地を中心とした探索円 (青円) を描き、その円内に最低 1 駅以上存在していれば、探索円内に最寄り駅も必ず存在していると言えます。つまり、青円に属する駅の中から全探索すればよいです。しかし、9000 個もある駅のどれが青円内にあるのかわからないことが問題です。

そこで基準点という概念を持ち込んで次のように考えます。基準点を中心とした探索円 (赤円) を描き、その中に青円が完全に内包されていれば、同じようにその中にも最寄り駅が存在しています。しかも、事前計算によって赤円に属する駅は特定可能です！その赤円というのが、「基準点-現在地間の距離の 3 倍の半径を持つ円」なんですね。

さて、青円内には最低で 1 駅以上は存在していることが前提となります。しかし現在地と基準点の距離が近すぎるときに、青円が 1 駅も含めないほど小さくなってしまうかもしれません。その場合は、基準点に最も近い駅が青円の中に入るように調整し、かつ赤円は青円を含むように赤円の半径を調整します。

アルゴリズムコードの解説

先程の説明をコードで示します。

type LngLatArray = [number, number] // [経度, 緯度]
type MapStation = {
  stationId: number
  coordinate: LngLatArray
}
type StationDistance = {
  station: MapStation
  distance: number // center から駅までの距離 (座標の差)
}

/**
 * ユーザーの座標から最寄り駅を計算するクラス
 *
 * - 基準点 center と全駅との距離を事前に計算し、配列 sortedStationDistances に記録しておく
 * - 配列 sortedStationDistances は距離で昇順にソートする
 * - 最寄り駅を求める際は、ユーザーの現在地と基準点の距離 distanceCenterToUser を計算し、
 *   配列の中にある distanceCenterToUser * 3 以下の駅の中で最寄り駅を再計算する
 * - ユーザーの現在地と基準点が離れすぎたときは、基準点を更新して sortedStationDistances を再計算する
 */
class NearestStation {
  /* 再計算の基準になる座標 */
  private center: LngLatArray = null as unknown as LngLatArray

  /* 基準座標からの距離で昇順にソートされた駅リスト */
  private sortedStationDistances: StationDistance[]

  constructor(stations: MapStation[]) {
    this.sortedStationDistances = stations.map((station) => ({
      station,
      distance: Infinity,
    }))
  }

  /**
   * 基準座標を更新し、全駅で基準座標との距離を再計算する
   *
   * @param userLocation ユーザーの座標
   */
  private updateCenter(userLocation: LngLatArray) {
    this.center = userLocation

    this.sortedStationDistances = this.sortedStationDistances
      .map(({ station }) => {
        const distance = NearestStation.distance(
          this.center,
          station.coordinate
        )
        return { station, distance }
      })
      .sort((a, b) => a.distance - b.distance)
  }

  /**
   * ユーザーの座標から最寄り駅を計算して返す
   *
   * @param userLocation ユーザーの座標
   * @returns 最寄り駅
   */
  public get(userLocation: LngLatArray): MapStation {
    if (this.center === null || !this.isInEffectiveRange(userLocation)) {
      this.updateCenter(userLocation)
      return this.sortedStationDistances[0].station
    }

    // 探索円の半径
    const searchCircleRadius = (() => {
      const distanceCenterToUser = NearestStation.distance(
        this.center,
        userLocation
      )
      const distanceCenterToFirstStation =
        this.sortedStationDistances[0].distance

      // 基準点を中心として基準点とユーザーの距離の 3 倍の半径をもつ円の中に必ず最寄り駅がある
      // ただし、基準点とユーザーの距離が近過ぎた場合は、青円を内包する探索円に最低1駅は入ることを保証する
      return Math.max(distanceCenterToUser, distanceCenterToFirstStation) * 3
    })()

    let distanceUserToNearestStation = Infinity
    let nearestStation: MapStation = null as unknown as MapStation
    for (const { station, distance: distanceCenterToStation } of this
      .sortedStationDistances) {
      // 探索円内に必ず最寄り駅がある
      if (searchCircleRadius <= distanceCenterToStation) {
        break
      }

      const distanceUserToStation = NearestStation.distance(
        station.coordinate,
        userLocation
      )
      if (distanceUserToStation < distanceUserToNearestStation) {
        distanceUserToNearestStation = distanceUserToStation
        nearestStation = station
      }
    }

    return nearestStation
  }

  /**
   * 基準座標とユーザー座標が離れすぎているときに false を返す
   *
   * @param userLocation ユーザー座標
   * @returns 基準座標を再計算するべきかどうか
   */
  private isInEffectiveRange(userLocation: LngLatArray) {
    // 距離的に約 5 km離れていたら再計算させる
    const LIMIT_DISTANCE = 0.055
    return NearestStation.distance(this.center, userLocation) < LIMIT_DISTANCE
  }

  /**
   * 2点間の距離を計算する
   * ただし、単位はメートルではなく座標なので注意
   *
   * @param c1 座標1
   * @param c2 座標2
   * @returns 距離
   */
  private static distance(c1: LngLatArray, c2: LngLatArray) {
    return Math.sqrt((c1[0] - c2[0]) ** 2 + (c1[1] - c2[1]) ** 2)
  }
}

const nearestStation = new NearestStation(日本全国9000駅)
毎秒実行(地図上に最寄り駅を描画(nearestStation.get(現在地)))

事前計算

最寄り駅計算の前に事前計算して、適当な時間間隔で再計算する

  public get(userLocation: LngLatArray): MapStation {
    if (this.center === null || !this.isInEffectiveRange(userLocation)) {
      this.updateCenter(userLocation)
      return this.sortedStationDistances[0].station
    }

最寄り駅の初回計算時、あるいは基準点 center と現在地が約 5km 離れたら基準点を現在地に更新してメソッド updateCenter で再計算します。 get は毎秒呼ばれるため、ほぼリアルタイムに基準点と現在地が 5km 離れているかどうかを監視していると言えます。

5km に大きな理由はないのですが、後述します。

計算時の現在地を基準点 center とする

center からみた各駅との距離を配列に保存する

  private updateCenter(userLocation: LngLatArray) {
    this.center = userLocation

    this.sortedStationDistances = this.sortedStationDistances
      .map(({ station }) => {
        const distance = NearestStation.distance(
          this.center,
          station.coordinate
        )
        return { station, distance }
      })
      .sort((a, b) => a.distance - b.distance)
  }

保存先の配列は sortedStationDistances で、center への距離が短い駅順にソートしておきます。つまり、updateCenter を呼んだ時点での現在地は center であるため、最寄り駅は sortedStationDistances[0] に入っていることになります。

最寄り駅計算

基準点 center を中心として、基準点-現在地間の距離の 3 倍の半径を持つ円

// 探索円の半径
const searchCircleRadius = (() => {
  const distanceCenterToUser = NearestStation.distance(
    this.center,
    userLocation
  )
  const distanceCenterToFirstStation = this.sortedStationDistances[0].distance

  // 基準点を中心として基準点とユーザーの距離の 3 倍の半径をもつ円の中に必ず最寄り駅がある
  // ただし、基準点とユーザーの距離が近過ぎた場合は、青円を内包する探索円に最低1駅は入ることを保証する
  return Math.max(distanceCenterToUser, distanceCenterToFirstStation) * 3
})()

基準点-現在地間の距離の 3 倍を探索円の半径 searchCircleRadius として求めています。もちろん、探索円の中に駅がある場合は最寄り駅の存在が保証されているのですが、探索円の中に駅がない可能性もあります。その場合は、青円を内包する探索円内に少なくとも 1 駅はある程度まで半径を広げています。

円内に含まれる駅の中から全探索をする

let distanceUserToNearestStation = Infinity
let nearestStation: MapStation = null as unknown as MapStation
for (const { station, distance: distanceCenterToStation } of this
  .sortedStationDistances) {
  // 探索円内に必ず最寄り駅がある
  if (searchCircleRadius <= distanceCenterToStation) {
    break
  }

  const distanceUserToStation = NearestStation.distance(
    station.coordinate,
    userLocation
  )
  if (distanceUserToStation < distanceUserToNearestStation) {
    distanceUserToNearestStation = distanceUserToStation
    nearestStation = station
  }
}

return nearestStation

配列 sortedStationDistances の中から基準点に近い順に最寄り駅を走査して、探索円外に出たらその時点で探索を打ち切ります。その時点での最寄り駅 nearestStation が真の最寄り駅と同一です。

5km についての解説

現在地が基準点から 5km 離れたら、基準点を更新するために再計算すると述べました。ここでの再計算は全国約 9000 駅に対する全探索です。

現在地が基準点に近いほど、探索円 (赤円) の半径も小さくなり、計算効率が上がります。したがって、現在地と基準点が「離れ過ぎたら」、適度に基準点を現在地に更新するほうが効率が良くなります。その「離れ過ぎたら」という基準が明確に定まっておらず、感覚で 5km と設定しました。ここでその 5km のことを「再計算距離」とラベリングしておきます。

さて、少なくとも次のことが言えます。

ユーザーの移動速度が速い場合、すぐに基準点と「離れ過ぎて」しまい全探索を何度もすることになるため、再計算距離は長いほうがよい
ユーザーの移動速度が遅い場合、長い間探索円内に滞在してくれるので、現在地と基準点は近いほうがよく、早めに基準点の更新をできるよう再計算距離は短い方がよい
ユーザーが地方を移動している場合、現在地と基準点が離れていても探索円内に駅が少ないため計算コストが小さく、再計算距離は長くてよい
ユーザーが都内を移動している場合、逆に計算コストが高くなるため、再計算距離は短い方がよい

これらすべてにちょうど良い唯一の再計算距離は自明でないので、感覚で 5km としてしまいました。

エコ方式の計算量

全駅数を N ≒ 全国約 9000 駅、探索円内の駅数を n < N とすると、ユーザが基準点から 5km 離れるたびに事前計算を O(N log(N)) で行い、ユーザーが基準点から 5km 以内の円内にいる間は毎秒 O(n) で最寄り駅探索ができます。事前計算が N log(N) になりますが、毎秒全探索の毎秒 O(N) よりはずっと計算量が落ちています。

具体例をあげます。現在地が基準点から 1km 離れている場合、n は基準点を中心として半径 3km の円内にある駅の数です。地方であれば数駅でしょうし、都内だと山手線の内側の面積の約 45% の範囲と同じなので 50 駅程度でしょうか...。現在地が基準点から 5km 離れている場合、地方だと十数駅で、都内だとおおよそ 23 区の面積と同じなので 500 駅くらいです。

まとめ

過去の計算情報を使った最近傍探索アルゴリズムを実装した
時間計算量を毎秒 O(n) < O(N) に抑える事ができる
- ただし、事前計算は O(N log(N))

個人的には計算中にマジックナンバーが出てくる面白いアルゴリズムを思いついたなと思っています。リアルタイムに最近傍探索をしたいとき、こちらのアルゴリズムを検討してみてはいかがでしょうか！

採用募集案内

モバファクでは中途採用・新卒採用ともに絶賛募集中です。会社の情報については、モバファクブログでも発信しています。技術好きな方、モバファクにご興味をお持ちの方は、ぜひご応募ください！

モバファクブログ：https://corpcomn.mobilefactory.jp/
採用サイト：https://recruit.mobilefactory.jp/

Mobile Factory Tech Blog

技術好きな方へ！モバイルファクトリーのエンジニアたちが楽しい技術話をお届けします！

毎秒現在地を使った最近傍探索をしたい