読者です 読者をやめる 読者になる 読者になる

謎言語使いの徒然

適当に気になった技術や言語を流すブログ。

力学モデル

日記 アルゴリズム

何というかメモ。

グラフを作画しようと思ってもなかなかレイアウトで良いアルゴリズムが思い浮かばなかったので調べてみた。

因みに最初に聞いてなんとなく困ったのが、衝突判定+摩擦係数方式。

単純にGUIで円としてアイテムを配置し、円同士が衝突 or 重なったりしたらお互い反対方向への移動ベクトルを持たせる。当然そのままでは停止しないので、摩擦係数をかけてやるというもの。

ただこれ、あんまり見やすくならないのです。反発係数小さくても摩擦係数を高くしてもあまりきれいなグラフにならない。

そんな時に見つけたのがコレ。

力学モデル (グラフ描画アルゴリズム) - Wikipedia

要するに、ノードを互いに反発する磁石みたいなものと捉え、ノード間のエッジはバネと見立てる。

で、それらが反発し合いつつ、安定した状態を完成系とするわけだ。

というか wikipedia のサンプルコード分からん。

とりあえず数式だけ考えてみようか

大学の座標系よろしく、二次元のベクトル空間で考えよう。

オブジェクト間の反発

F を力で、反発の係数 g とすると、F は二点間の距離の二乗に反比例する筈だ。

  • F = g / pow(d, 2)

もちろん二次元座標系なので、中心に近い点を基準に取れば、もう一点の方向ベクトルは (x, y) = (cos, sin) なので

  • (fx, fy) = g/pow(d, 2) * (cos, sin)

バネの弾性

バネの基本となる長さを L とすると、物体にかかる力 F は実際に伸縮した際の距離 d との差分 d - L に比例する筈だ。それも元に戻ろうとする方向だからマイナスだろう。

この時の弾力の係数を k とすれば

  • F = (d - L) * -k

前述通り cos, sin すれば力のベクトルになる。

バネに関しては物理的に2オブジェクトが繋がっているから、作用反作用をモロに受けるのかも知れない。かかるエネルギーは双方一緒だが、質量差は考慮すべきかも知れない。

摩擦係数

何のことはない、これは速度ベクトルの逆向きに係数をかければいい。というか静摩擦係数と動摩擦係数を分けて考えるべきなのかは知らない。

  • F = -V * μ

ここで困るのは、摩擦係数だけ使ってるのが速度だぞと。

離散時間で考える

速度 = 単位時間当たりの移動量なワケだが、単位時間分加速し終わった時点での移動ベクトルとも言い換えられる。

  • v = a * Δt

ならばニュートン先生は F = a * m(質量) とおっしゃってるので a = F / m でもいいわけだ。

質量差を考えなければ m = 1 でいいから、a = F すると、処理開始直後の物体の速度は

  • Vt = (Ft * Δt)

二フレーム目からの速度は

  • Vt = V(t - 1) + (Ft * Δt)

となるのか。これに対してなら摩擦はつけられる。

後は各フレームごとに Vt を計算して、それを足していけば、位置座標 R が計算できる…筈。

後は Wikipedia 様の言うように、全体のオブジェクトの移動ベクトル絶対値総和が一定以下に収まるまで回せば完成する。