アイリッジ開発者ブログ

アイリッジに所属するエンジニアが技術情報を発信していきます。

位置情報のaccuracyを活用した来店判定方法

アイリッジ プロダクト開発グループの朴です。

geography上で位置情報を使ってユーザーの来店判定をする時、普段は距離を計算して判定すると思います。 もう少し細かく説明すると、特定場所(お店など)の中心になる座標とユーザーの位置情報を元に距離を計算して特定の値より大きいか小さいかでin/outの判定をするということです。 これは特定場所の中心点を「円心」にし、特定の値を「半径」にするの中に(ユーザーの位置情報)があるかを判定することを意味します。

この判定方法はいいと思いますが 位置情報にはさらにaccuracyという精度を表す値があり、androidの場合はfloatで単位はmeterです。 これは位置情報の座標を円心にし、accuracyを半径にしている円のとこかに存在することを意味します。 つまり、accuracyが小さければ小さいほど位置情報の正確度が上がるということです。

それではどうしたらaccuracyを判定時に活用できるのか?

先に言及したように位置情報とaccuracyを組み合わせると円で表現できます。 それで「特定場所の円」と「ユーザーの円」ができ、円と円の関係で演算が出来るようになります。 もし円と円が重なった場合はその部分の面積を取って割合でin/outの判定ができるということです。

ではこれからその方法をpython codeと共に紹介します。

1. 二つの円の重なり合う面積

円と円が重なった場合にその部分の面積を取る数式を確認します。
下記の絵のように座標平面上に二つの円があります。

f:id:iridge-tech:20190423183539p:plain 画像出典

円心がx 軸上にある二つの円 R1とR2は「半径をRとr、扇形の内角を\theta_1 \theta_2 、円心間の距離をd」だとすると二つの円が重なり合った部分の面積は

R1の扇形の面積 + R2の扇形の面積 - (R1の三角の面積 + R2の三角の面積) 

になります。では、実際に面積を求める数式を書いてみます。
まず二つの扇形の面積は


S_1 = \pi R^2 \cdot \frac{\theta_1}{2\pi} \space,\space\space S_2 = \pi r^2 \cdot \frac{\theta_2}{2\pi} \\
\therefore S_1 + S_2 = \frac{R^2 \theta_1 + r^2 \theta_2}{2}

になります。
次、二つの三角形の面積は


T_1 = \frac{R \cdot R}{2}\sin\theta_1 \space,\space\space T_2 = \frac{r \cdot r}{2}\sin\theta_2 \\
\therefore T_1 + T_2 = \frac{R^2 \sin\theta_1 + r^2 \sin\theta_2}{2}

になります。
それで、二つの円の重なり合った部分の面積は


A = \frac{R^2 \theta_1 + r^2 \theta_2}{2} - \frac{R^2 \sin\theta_1 + r^2 \sin\theta_2}{2} \\
\therefore A = \frac{R^2(\theta_1 - \sin \theta_1) + r^2(\theta_2 - \sin \theta_2)}{2}

になります。
これをpythonで表現すると以下のようになります。

import math

def theta1():
    raise NotImplementedError()

def theta2():
    raise NotImplementedError()

def intersection_area(R, r, d):
    t1 = theta1()
    t2 = theta2()
    return (pow(R, 2) * (t1 - math.sin(t1)) + pow(r, 2) * (t2 - math.sin(t2))) / 2

結局、\theta_1 \theta_2 が分かれば重なり合った部分の面積を求められることですね。
では、次に余弦定理を使って各\theta を求めてみます。
\theta_1


r^2 = R^2 + d^2 − 2dR \cdot \cos\frac{\theta_1}{2} \\
\cos\frac{\theta_1}{2} = \frac{d^2 + R^2 - r^2}{2dR} \\
\therefore \theta_1 = 2 \cdot \cos^{-1}\frac{d^2 + R^2 - r^2}{2dR}

\theta_2


R^2 = d^2 + r^2 − 2dr \cdot \cos\frac{\theta_2}{2} \\
\cos\frac{\theta_2}{2} = \frac{d^2 - R^2 + r^2}{2dr} \\
\therefore \theta_2 = 2 \cdot \cos^{-1}\frac{d^2 - R^2 + r^2}{2dr}

になります。
この式を以前のpython codeに加えると下記のようになります。

import math

def theta(R, r, d):
    return 2 * math.acos((pow(d, 2) + pow(R, 2) - pow(r, 2)) / (2 * d * R))

def intersection_area(R, r, d):
    t1 = theta(R, r, d)
    t2 = theta(r, R, d)
    return (pow(R, 2) * (t1 - math.sin(t1)) + pow(r, 2) * (t2 - math.sin(t2))) / 2

これで二つの円の重なり合う面積を求める式が出来ました。

それではこれをgeography上にはどうやって適用できるのか確認してみます。

2. geography上で二つの円の重なり合う面積

1.の絵でR1を特定場所の円、R2をユーザーの円だとするとRは場所の半径に、rは位置情報のaccuracyになります。 面積を計算するためにはさらにdを求める必要があります。 そしてR, r, dは同じ単位にする必要もあります。(私はmeterで合わせています。)

ここではgeographyの説明は省略しますが geography上の距離計算にはhaversine formulaがよく使われます。 この式を使うとR1とR2の円心間の距離を計算できます。
下記はhaversine式をpythonで書いたものです。

import math

# 座標は(long, lat)、単位はmeter
def distance(p1, p2):
    return 1000 * 6371 * 2 * math.asin(math.sqrt(
        pow(math.sin((p1[1] - p2[1]) * math.pi /180 / 2), 2)
        + math.cos(p1[1] * math.pi / 180)
        * math.cos(p2[1] * math.pi / 180)
        * pow(math.sin((p1[0] - p2[0]) * math.pi /180 / 2), 2)
    ))

これでdも求められるようになりました。

この後ユーザーが特定場所に位置するかしないかを判定するためのには取った面積の重なった割合を計算する必要があります。 割合はユーザーの円R2が場所の円R1にどのくらい重なり合ったのかを計算すればいいので下記の式になります。
ユーザーの円R2が場所の円R1に重なり合った割合を計算すればいいので


\frac{A}{\pi r^2}

になります。
この式で割合を計算し、最終的に決めた閾値と比較してin/outを判定すればいいです。

ここで注意する点は今まで説明したのは二つの円が重なった場合に限るということです。 すなわち、重なっていない場合や一方の円に含まれる場合は該当しません。
では、判別するcodeをpythonで書いてみます。

import math

ar = 0 # 割合、重なっていない場合
if d + R <= r: # R2の中にR1が存在する場合
    ar = (math.pi * pow(R, 2)) / (math.pi * pow(r, 2)) # R1の面積 / R2の面積
elif d + r <= R: # R1の中にR2が存在する場合
    ar = 1.0
elif d < R + r: # 重なっている場合
    ar = intersection_area(R, r, d) / (math.pi * pow(r, 2)) # 重なり合う面積 / R2の面積

では、試してみます。 下記のように位置情報を設定します。

# 円心座標(long, lat)
R1_p = (136.9122221, 35.1299227)
R2_p = (136.9116187, 35.1295955)
# 半径(meter)
R = 70.0
r = 130.0

dはdistance()で取得します。

d = distance(R1_p, R2_p)

これで実行した結果は下記のようです。

65.83955443494703 <- 距離
0.28405751429740494 <- 割合

上記の位置情報をjupyterで描画してみました。

f:id:iridge-tech:20191204194614p:plain

青の円がR1、赤の円がR2で各円の円心も同じ色のiconで表示しました。 R1とR2の円心間の距離は「65.83955443494703」でR1の半径(R)より小さいため距離ベースの判定ではユーザーはinだと判定されます。 一方、面積の判定では28.4%が重なったと結果がでました。

面積ベースの判定は閾値の決め次第ですが うまく調整すれば距離ベースの判定よりも精度が向上できると思います。

補足

半径を下記のように変えて試してみました。

# 円心座標(long, lat)
R1_p = (136.9122221, 35.1299227)
R2_p = (136.9116187, 35.1295955)
# 半径(meter)
R = 40.0
r = 60.0

結果は

65.83955443494703 <- 距離
0.1523932496106786 <- 割合

f:id:iridge-tech:20191204194635p:plain