fastapple's blog

時系列関係なく、情報を追記・分割・統合などします。ブログに記載の内容のうち、引用ではなく、私自身が記載している文章・コードなどについては、自由にご利用ください。

出会いアプリ(Tinder等)で、km表示のみで位置は特定される。


予約投稿などを駆使しているにせよ、月に10本以上記事を公開するのは実はこの記事で初めてっぽい。暇ならわりと書けるもんだなと思った。今後は、暇でないときも書けるようにしていきたい。閑話休題

昔どこかでまとまった記事をみたような気がするのだが、どういう検索ワードで調べればいいのか、でてこない。その記事では、タイトルのように、位置情報が完全な状態で与えられない場合でも、位置が特定可能なことを示した海外の記事を翻訳、解説したような記事だったとおもう。みつからないので、まあいい。今回これを考えてみることにする。

出会いアプリの王道といえばTinderである。ちょっとした研究をしようと思ったら、Tinderで調査しましたといえばいい気がする。Tinderは、標準的かつ世俗的な、出会いアプリの代表格という感じだ。Tinderは自分と相手との距離をkmで表示することができる。これでどこまでのことがわかるだろうか。こういったことを考えたい。結論から言うと、位置は完全に特定できてしまう。(ちなみにTinderで位置情報を隠すには有料会員にならないといけません。位置を知られたくない人は、有料会員になるか、アンインストールしましょう)

出会いアプリの位置情報の表示のさせかたは、ユーザーが色々選べる場合がある。ピンポイント度?が高いものから並べてみよう。
Lv1.自分の位置を公開する・・・いうまでもなく、自分の位置は相手にしられます。
Lv2.相手と自分の距離がわかる・・・このひとと、何km離れています。というやつ。
Lv3.相手が自分の何km圏内にいるのかわかる・・・何km離れているという表示はでなくても、「何km圏内にいる人」というのを検索出来るタイプのもの。位置を公開していなくても、この検索で捕捉対象になっている場合がありそう。
Lv4.位置情報に誤差をもたせられる・・・ログインするたびに、指定の距離だけランダムに誤差を付与するようなやつ。
Lv5.自分に近い順のひとから表示される・・・ログインすると、近いひとから順に表示されるようなもの。

さて、Lv1~Lv5まで並べてみました。このなかで、調べれば位置を特定できるものはどのレベルまででしょうか。正解は、Lv1~Lv3までは位置を特定できる。また、Lv4の場合、自宅など(定期的に長期滞在する地点)は特定できる。また、Lv.5の場合も、位置をある程度(人が多ければ多いほど正確に)絞り込むことができる。また、もし、2つのアカウントを用意することができれば特定できる。

特定するための方法名をとりあえず、上から順に名付けてみた。
Lv1.自分の位置を公開する
→対応不要
Lv2.相手と自分の距離がわかる
3点距離法(難易度★☆☆☆)で位置を特定できる。
Lv3.相手が自分の何km圏内にいるのかわかる
圏内探知法(難易度★★☆☆)で位置を特定できる。
Lv4.位置情報に誤差をもたせられる
3回取得法(難易度★★★☆)で位置を特定できる。
Lv5.自分に近い順のひとから表示される
ボロノイ法(難易度★★★★)で位置を絞り込むことができる。アカウントが複数ある場合に位置を絞り込む方法はなんとなくわかると思うので割愛。

なお、自分の位置情報は自由に動かせることが前提である。また、前提として、「計測中」は相手の位置が動かないこととする。自分の位置情報は、自分が実際に動いたり、あるいは位置情報を偽装するアプリなどでいくらでも動かせるものとする。位置情報を偽装する方法などはここでは省略する。

詳細をみていく。Lv1は説明不要なので、Lv2から。
Lv2・・・3点距離法を使って、相手と自分の距離から位置を特定する(難易度★☆☆☆)
相手の場所を点Pとする。まず、いまの自分の場所を点Q_1とする。相手との距離が1kmちょうどとすると、相手は、いまの自分の場所点Q_1を中心した1kmの円の、円周上のどこかに位置することがわかる。(図はここからフリーハンドです。)
f:id:fastapple:20171125184113j:plain
さらに別の場所(点Q_2とする)へ移動し、再度距離を調べる。点Pは、点Q_2を中心とした円の円周にも存在するので、もはや、点Pの存在する可能性がある位置は2箇所に絞られる。
f:id:fastapple:20171125184248j:plain
さらに別の場所(点Q_3とする)へ移動し、再度距離を調べる。点Pは、この方法で、完全に1箇所にしぼられた。
f:id:fastapple:20171125184346j:plain
この、3箇所へ移動し距離を測る。という方法は割りと簡単に実施することが出来る。容易に位置を特定できることがわかるだろう。

では次にLv3のケースを見ていこう。
Lv3・・・圏内探知法を使って、相手が自分の何km圏内にいるかという情報のみで、位置を特定する。(難易度★★☆☆)
もし、何km圏内ということしかわからなければ?これもうまくいく。1km圏内の相手が表示されるとしよう。相手である点Pが最初圏内にあるとする。自分である点Qを徐々に南へ動かしていくと、かならずどこかで、点Pが圏外となる。このとき、点Pは、点Qを中心とした半径1km前後の円の近くにあることがわかる。もっといえば、点は南へ動かしてきたので、円の南側である下半分には存在せず、円の北側にある上半分に存在することがわかる。
f:id:fastapple:20171125205625j:plain

こうしてたどり着いた点を、新たに点Q'とする。この位置は重要なので控えておく必要がある。さらに点Q'を東西に動かすことを考えてみる。東側(図の右側)へ動かしたとき、点Pは2度と圏内に入ることはない。一方、西側(図の左側)へ動かしたとき、点Pは、再びしばらくの間、圏内に存在する。このことから、点Pが、点Q'を中心とする半径1kmの円周の、左上側領域に存在することがわかる。
f:id:fastapple:20171125205906j:plain

Q'を西へ動かしていったところ、再び点Pが圏外となる場所がある。ここを点Q''としよう。このとき、点Q'と点Q''の間の距離をdとする。すると、点Pの位置が正確にわかってしまう。図をみればすぐに直感的に分かるが、点Q'を中心とする円の上半分の円弧を、東西に渡る線分で切り取るとき、ちょうど長さdで切り取ることが出来る箇所が存在する。(d'とする)この場合は、その線分の西側の点が、点Pである。
f:id:fastapple:20171125210130j:plain


では次にLv4のケースを見ていこう。
Lv4・・・3回取得法を使って、位置情報に誤差が含まれる場合にも、位置を特定する。(難易度★★★☆)
自分の位置情報に誤差を含められるケースがある。たとえば、「1kmの誤差」など。その場合、例えば典型的なケースではログインする度に実際の位置から1km離れた場所にいることになる。
ところで、Lv1~3のどれかの状況に当てはまる場合には、位置を特定できることがわかった。Lv4のケースでも「誤差の影響をうけたあとの点P」の位置は、求めることが出来る。しかしながら、自宅などでログインする場合、点Pの位置は実際にはかわっていない。誤差を含んだ位置だけがログインごとに特定されうる。例えば3回ログインしたとき、設定された位置をそれぞれ、点P_1,P_2,P_3とすると、以下の図のようになる。
f:id:fastapple:20171125213905j:plain
図をみると一目瞭然だが、点P_1,P_2,P_3は点Pからすべて同じ距離だけ離れているので、この3点を結ぶ円が存在する。この円は、点P_1,P_2,P_3からなる三角形に外接する円であることがわかる。と、いうことは、この外接円の中心(外心)は紛れもなく求めたい、点Pである。
すこし特殊なケースを考えよう。1kmの誤差といっても、もしかすると、ログインごとに0~1kmの範囲で誤差を与えるような実装になっているかもしれない。このような場合は、3回の計測ではわからず、確率的にしか位置はわからないが、回数を重ねるごとに精度をあげていくことができる。いわゆる典型的なモンテカルロ法を使って求めればいい。つまり実際の点P(x,y)に対して、n回目にログインした際の誤差の影響をうけた点を点P_n(x_n,y_n)とすると、次の式のようになるだろう。\sum_{n=1}^{\infty}(\frac{x_1+x_2+\cdots+x_n}{n})\rightarrow{x},\sum_{n=1}^{\infty}(\frac{y_1+y_2+\cdots+y_n}{n})\rightarrow{y}

最後にLv5のケースを見ていく。
Lv5・・・ボロノイ法で、自分に近い順のひとから表示される場合に、位置を絞り込む。(難易度★★★★)
Lv5のケースでは、自分に近い順のひとから、ひとが表示される、こういう場合も、かなり位置を絞り込むことができるのではないかと思っているが、今回の方法は、「本当はもう少し絞れるだろうなぁ」と思うが、その手前の部分まで。という感じである。まずは問題を簡単にするため、自分の点Q以外に、求めたい点Pと、それ以外の点Rがあるような状況を想定する。自分に近い順で点が表示されるため、状況としてはPが近い場合と、Rが近い場合の、2パターンであり、逆にいえば、それだけしか判らない。以下の図のように点Pと点Rがあるとき、その境界線の部分で、近い順が入れ替わるため、調べていくと、この境界線は導き出すことができる。ただし、わかるのは、境界線をはさんで等間隔に(境界線に対して垂直に)点Pと点Rがあるということがわかるだけで、可能性は無数に存在する。
f:id:fastapple:20171125225858j:plain

さて、もうひとつ点Sが存在する場合を考える。このとき、新たに自分自身(点Q)を色々動かしてわかることは、点Pと点Sの間の境界線と、点Rと点Sの間の境界線だ。さて、よくよく考えると、この境界線は、点P,R,Sから成る三角形の各辺を垂直に二等分している。これはどこかでみたことがある。そう。この3つの境界線の交点Gは、この三角形の外心となっている。
f:id:fastapple:20171125234148j:plain

ここにきて外心の性質などを必死で探していたが、なかなか今回使えそうな性質がない。ただ、外心で調べていくのは正解だった。ボロノイ図というのを発見した。ボロノイ図というのは、要するにこういう作業を積み重ねて、近い点がある区画を塗り分けたものをいう。詳細な説明をここに書くとなかなか大変なので、Wikipediaに譲ろう。wikipedia:ボロノイ図
上記の方法で、母点の位置はわからないが、ボロノイ図の境界線は描けてしまうというのが面白い。そして、上記図で、点Gとしていたのは、ボロノイ点に相当する。ボロノイ点は、任意の母点3つからなる三角形の外心である。
さて、点Qを動かしまくれば、点Pを母点とするボロノイ領域がわかるので、位置がある程度わかるといえるのではないか。(もう少しがんばれそうな気がすごくするが)ボロノイ領域をすごく頑張って求めないといけないのだが。
冒頭の方にも書いたとおり、アカウントが2つあれば、このような方法をとらなくても、やり方はあるわけである。なんだかボロノイ図の事ばかり考えていたので、それを使った方法しか思いつかないが、ボロノイ点と、さらにその近くの母点の座標が(それが用意した2つ目のアカウントなら)分かるわけなので、これで、ボロノイ点を中心とした円を描ける。そしたら、再度2つ目のアカウントを移動して別の母点として使い、ボロノイ点を中心とした円を再度描く。その2つの円の交点が、点Pが構成していると考えられるボロノイ領域に存在するなら、それがまさに点Pであろう。場合によっては、何回か移動する必要があるかもしれないが。

長くなったが、まとめる。
■事実■
大半のアプリで、位置情報は、仮の場所を設定しない限りは、相手に知られる可能性がある。

アプリ開発側で考えられる対応■
・仮の場所を設定できる方法を提供すること。
・誤差をもたせる方法より、位置を区画化させたりする方法を提供するほうがいい。→ただし、実装が難しくなる。
→ただし、どうやらほとんどの開発者は、これを有料にしたいらしい。

■ユーザ側でとれる方法■
・仮の場所を設定する。
・仮の場所を設定できないなら、あきらめる。(或いは付け焼き刃を承知で誤差を持たせる。)
・アンインストールする。