MySQL
アルゴリズム
geometry

最寄り駅を導出するアルゴリズム

はじめに

住所や緯度経度を扱うプログラミングをしていると、「最寄り駅を出しましょう」という要件が時々出てくる。

その時のアプローチはこんな感じ。

APIを使うという方法

http://api-sdk.navitime.co.jp/api/
当然のことながら地図や経路探索サービスを提供している会社からAPIを使うというのが一番てっとりばやい。ただお金はかかる。

緯度経度から距離を求めて並び替える方法

GoogleMapのAPIを始め、大半の地図サービスはランドマークや住所から緯度経度に変換してくれるサービスを提供されている。有料のことも多いが、緯度経度を導出するだけなら安い。また最初から緯度経度が提供されていることも多い。

経度1度あたりの距離というのは、地球が丸いから緯度によって変わってくる。赤道の方が緯度あたりの距離は長いし、北に行くほど短い。したがって、ちょっとだけ面倒な計算が発生する。

アルゴリズム自体は地球が球体であることを前提に経度あたりの距離を補正するだけなので、10行もかからない。
https://qiita.com/4geru/items/27785e9066c4e22eeaa3
ただ、「最寄り」を導出するには、自分の位置から、他のスポットの緯度経度をすべて計算して、距離順にソートという面倒なことをしないといけない。

MySQLにはgeometoryという型があるので、そこに緯度経度を格納するという方法もある。
https://qiita.com/mitani/items/6909406ac4fe0db2d35c

ただ、当たり前だけど専用の方はバイナリになって扱いにくい。DBエンジンにすごく依存する。上記サンプルでは計算値フィールドで並び替えたりしているなど、手放しでは採用できない。

最初から緯度経度で絞る方法

考えてみると、地図アプリが表示をするときって、「最寄り」の計算なんてしてない。やっているのは、緯度FROM,緯度TO,経度FROM,経度TO の4点を指定してその範囲に含まれるスポットを出しているだけだ。

「最寄り」と考えるから距離を計算して距離の小さい順にソートしようとしてしまっている。10Km先が最寄りであってもそれは最寄り駅とは言わない。大事なのは、「近くの緯度経度に含まれるスポット」なのだから、計算位置フィールドのORDERBY LIMIT ではなく、WHERE 緯度経度の範囲 なのだ。実データに対するWHEREならインデックスが効くので高速に検索できる。

そして最寄り駅のレベルなら徒歩圏内なので地球の丸さは影響しない。絞り込んだあとに緯度経度の差分の絶対値をみれば距離にも並べられる。これはフロント側で行っても良い。