座標上の2点間の距離を求める

2019-12-03

位置情報を処理する時に必要になってくる処理の1つが座標上の2点間の距離を求める方法でしょう。 2点間の距離と言えば中学校でならった公式がまず最初に浮かびますがこれは使用できません。

地球は球体であり我々はその表面上にいるのでそれを考えると利用できないのは簡単に想像できます。

ちなみに実際には綺麗な球体ではなくデコボコで、この様な形をしているそうです。 思ったよりデコボコですよね…

球面三角法

実際には地球はデコボコと書きましたが、地球を球と仮定する方法が「球面三角法」です。

2点を P (φ1, λ1)、 Q (φ2, λ2) とすると、2点間の距離は以下の公式で表せます。 ただし、それぞれの値はラジアンとします。 rは赤道半径です

x = r arccos (sin φ1 sin φ2+cos φ1 cos φ2 cos(λ1 − λ2))

これを素直に実装します(Ruby)

# ラジアンに変換
def deg2rad(x)
  x * Math::PI / 180
end

def distance(lat0, lon0, lat1, lon1)
  # 赤道半径(m)
  r = 6378137.0

  x0 = deg2rad(lat0)
  y0 = deg2rad(lon0)
  x1 = deg2rad(lat1)
  y1 = deg2rad(lon1)

  r * Math.acos(Math.sin(x0) * Math.sin(x1) + Math.cos(x0) * Math.cos(x1) * Math.cos(y0 - y1))
end

東京駅 (35.6786464, 139.7654616) と 大阪駅 (34.7024898, 135.4937619) で計算してみます

distance(35.6786464, 139.7654616, 34.7024898, 135.4937619) #=> 403483.2185515306

Google Mapで計算すると 403.13km とのことでほぼ問題ない値と言えるでしょう。

Vincenty法

地球を回転楕円体とみなし、2点間の距離を計算するアルゴリズムです。 この考え方は現在GPS等でも採用されている方法であり、GRS80と呼ばれる回転楕円体を採用しています。 GRS80は日本でも正式な距離として認められています。

概要を知りたい場合は以下の国土交通省国土地理院のページが参考になるでしょう。

世界測地系移行の概要


計算式はWikipediaを参考にすれば良いでしょう。 ただ、読めば分かるように計算式が複雑でありコードは割愛します

Wikipedia:Vincenty法

特徴として収束計算の為にループ処理を行うために計算時間が掛かる、計算式によっては収束しないまたは収束に時間が掛かるという問題点があります。 状況によっては採用を避けるのがベターかもしれません

Hubenyの公式

検索を行うとよく出てくるのがこのアルゴリズムです。 緯度経度を用いた3つの距離計算方法.pdf によると出典が不明瞭ではあるがカシミール3Dという3次元地図ソフトのマニュアルとの記述があります。

検索に出てくる式を元に実装したものがこちらです。

def distance(lat0, lon0, lat1, lon1)
  # 赤道半径
  rx = 6378137.0
  # 極半径
  ry = 6356752.314245

  x0 = deg2rad(lat0)
  y0 = deg2rad(lon0)
  x1 = deg2rad(lat1)
  y1 = deg2rad(lon1)

  diff_x = x0 - x1
  diff_y = y0 - y1
  p = (x0 + x1)/2.0

  e = Math.sqrt((rx**2 - ry**2)/rx**2)
  w = Math.sqrt(1 - e**2 * Math.sin(p)**2)
  m = (rx*(1-e**2))/w**3
  n = rx/w

  Math.sqrt((diff_y*m)**2 + (diff_x * n * Math.cos(p))**2)
end

同様に、東京駅と大阪駅で計算してみます

distance(35.6786464, 139.7654616, 34.7024898, 135.4937619) #=> 482186.60850321857

球面三角法とほぼ変わらない値となっていますが、誤差は3つの中で一番大きいようです

緯度経度を用いた3つの距離計算方法.pdf にも誤差が大きいとの記述がありますが、実装はVincenty法ほど難易度が高いので採用される場合が多いようです。

他アルゴリズム

上記以外にもアルゴリズムはあります。見つかった物を羅列しておきます

問題

まず、どの方法を用いても多少の誤差が発生しますので注意してください。仕様次第ではありますが誤差を気にする場合はアルゴリズムの選択に注意を払うべきでしょう

また、これらの方法は計算方法はともかく2点間の距離を計算する方法でありデータベース上にある大量のデータとの距離を計算する場合には大量の計算が発生するので向いていないでしょう。

よくあるパターンは特定の地点から一定距離にあるデータを取得する、といった処理です。

これらを解決するにはデータベースから一定の範囲の少量のデータのみ取得し、そこから距離計算を行うといった処理になるでしょう。 この問題をどうやって解決するかは次回以降にしたいと思います

関連記事