ぱろっと・すたじお

技術メモなどをまったりと / my site : http://parrot-studio.com/

geo-triangle と 「こじつけトライアングル」リリース

先日の「Gunma.web #5」の二次会で、
「群馬のパワースポットをこじつけで探す」という話が出ていました


Gunma.web #5 (on 2011/05/14) まとめ - ぱろっと・すたじお


話をしながら、なんとなく仕組みが浮かんできたのと、
この日にやったLTが私的に不本意で終わったこともあり、
その場で「ライブラリだけでも実装しますよ」的な話をしました


・・・ということで、作りました(`・ω・´)


あくまで動作確認サンプルサイトなので、デザインとか一切考えてません
住所を入力して座標を求める仕組みすらありません
きっと誰かがまともな実装をしてくれる・・・


ちなみに、「前橋駅」「新前橋駅」「中央前橋駅」の三点の中心は、
とある学校になっている、という事実が判明


http://parrot-studio.com/gt/m/36.383304,139.073632,36.391026,139.075107,36.378536,139.046445


ローカルネタですいません・・・(´・ω・`)


なお、ロジックが非常に簡単なので、最終的にはJavaScript・・・というか、
CoffeeScriptで書きたいと思ってますが、時間がある時に書き直す感じで・・・


その代わり(?)、地図を表示するURLの「m」を「c」に変えると、
JSON形式で中心(重心)の座標を返します


http://parrot-studio.com/gt/c/36.383304,139.073632,36.391026,139.075107,36.378536,139.046445


常識的な範囲で使ってもらって構いませんが、
ソースも公開していることですし、
自前のサーバに置いてもらった方が・・・

geo-triangleの実装


ここからは完全に蛇足ですが、
「三点の座標の中心」をどうやって求めているか、というお話


一概に「三角形の中心」といっても、
Wikipediaによると5種類もありますΣ(゚Д゚)ガーン


そんなこともよくわかってなかった私は、
最初「各辺の中点を通る垂直二等分線の交点」=「外心」を求めてしまいました


鈍角三角形の外心は三角形の外になってしまうため、
あまり「中心」という感じがしないので、これは没に(´・ω・`)
(gemのおまけで残してありますが)


次に考えたのが「重心」で、これは定義上確実に三角形の「中」に存在します
計算式も思いついたので、これでいこうと

問題:
点A(a, b)、B(c ,d)、C(e, f)が与えられたとき、その重心をa,b,c,d,e,fで表せ

重心の定義は「各辺の中点と向かい合う頂点を結んだ線の交点」なので、
以下の戦略で求められるはずです

  1. ABの中点とCを結ぶ一次関数y=px+qを求める
  2. BCの中点とAを結ぶ一次関数y=rx+sを求める
  3. y=px+qとy=rx+sの交点(連立方程式の解)(x, y)が重心


後は実際に座標を代入していけばいいのですが・・・とにかく面倒です
ちょっといじってみればわかりますが、
計算間違いしない方がおかしいレベルの複雑さ(ノ゚Д゚)ノ彡┻━┻


途中まで計算したところで、これではダメだろうと、
他の手段を考えたところで、基本的なことを思い出しました


「ベクトルの計算はまず原点をずらす」


つまり、Cを新しい原点O'と見なして、
A、Bを平行移動させ、O'、A'、B'の重心を求めた後、
移動分を戻せば元の重心になるはずです


三次元ベクトル計算でも同じような考え方で、
回転して原点を動かし、計算してから再び戻す、という話が、
この本に書いてあります


ゲームプログラマになる前に覚えておきたい技術

ゲームプログラマになる前に覚えておきたい技術


ということであらためて、O'(0, 0)、A'(sa, sb)、B'(sc, sd)
(ただし、sa = a-e、sb = b-f、sc = c-e、sd = d-f)の三点について、
重心を求めることを考えます

  1. O'A'の中点とB'を結ぶ一次関数y=px+qを求める
  2. A'B'の中点とO'を結ぶ一次関数y=rxを求める(原点を通るので切片=0)
  3. y=px+qとy=rxの交点(連立方程式の解)(x, y)がO'A'B'の重心
  4. その重心をずらした(x+e, y+f)が本当の重心


これだと(0,0)が計算に絡むので、圧倒的に簡単になるわけですが、
出てきた答えがこれまた驚きでしてΣ(・ω・ノ)ノ

答え:
x : (sa + sc) / 3 + e = (a + c + e) / 3
y : (sb + sd) / 3 + f = (b + d + f) / 3
ただし、sa = a-e、sb = b-f、sc = c-e、sd = d-f

最初に原点移動させずに計算したときは、
こんなシンプルな答えになるとは思えなかったので、
合っているか非常に疑問だったのですが・・・


でもこれ、論理的に考えると正しいのです


「線分を頂点側から2:1に分割する点=重心」という性質を考えると、
O'(0,0)とA'B'の中点P((sa+sc)/2, (sb+sd)/2)を2:1で分ける点になります


線分y=rxは原点を通るので、単純にPの座標を2/3した点が重心です
つまり、((sa+sc) / 2) * (2/3) = (sa+sc) / 3 となるので、
やっぱり答えは正しい・・・と


ということで、geo-triangleを仮リリースしまして、
それを使ったサンプルサイトを組んでみたわけですが、
確かに地図上で見ると「それっぽい」点が出てますよね


まあ、数学(というか代数幾何?)をまともにやっていれば、
こんなのは常識なのかもしれませんが、
それなりに苦労したので記録に残しておく感じで...φ(・ω・`)