【やってみた】リーマン多様体へのグラフ描画アルゴリズムの実装【実装してみた】
?
5 likes?2,674 views
リーマン多様体へのグラフ描画アルゴリズムの実装 http://ytakano.github.io/
![元論文の説明（１）
リーマン多様体 M は，すべての点 x M で
接ベクトル空間を持つ
リーマン多様体上の a と b を結ぶ
連続曲線 γ: [a, b] → M の長さは
length(γ) =
b
a
??γ(t)??dt
となり，任意の点 a, b 間を最小とする曲線の長さが
点 a, b 間の距離と定義され d(a, b) と表す
10](https://image.slidesharecdn.com/riemanwide1503-150413105245-conversion-gate01/85/-10-320.jpg)
![元論文の説明（３）
generateinitial layout(G)
while not donedo
for n ∈G do
x := position[n]
G := τx(G)
x := force directedplacement(n, G )
position[n] := τ?1
x (x )
end
end
すると，リーマン多様体上における
バネモデルレイアウトのアルゴリズムは以下のようになる
12](https://image.slidesharecdn.com/riemanwide1503-150413105245-conversion-gate01/85/-12-320.jpg)
【やってみた】リーマン多様体へのグラフ描画アルゴリズムの実装【実装してみた】
- 4. 元論文 Kobourov, S. G., and Wampler, K. Non-Euclidean Spring Embedders. IEEE Trans. Vis. Comput. Graph. 11, 6 (2005), 757?767. 4
- 5. 本発表の目的 5
- 6. 実装デモが主目的 6
- 10. 元論文の説明（１） リーマン多様体 M は，すべての点 x M で 接ベクトル空間を持つ リーマン多様体上の a と b を結ぶ 連続曲線 γ: [a, b] → M の長さは length(γ) = b a ??γ(t)??dt となり，任意の点 a, b 間を最小とする曲線の長さが 点 a, b 間の距離と定義され d(a, b) と表す 10
- 11. 元論文の説明（２） 1. 全ての y ∈M に対して τ?1 x (τx(y)) = y 2. ??τx(y)?? = d(x, y ) 3. τx は原点に対する角度を維持する 4. Range(τx) = M 5. Range(τ?1 x ) = Tx M ここで，すべての点 x M でリーマン多様体と 接ベクトル空間への写像を τx: M → Tx M，τx -1: Tx M → Mと定義する． ただし，τx とτx -1 は以下の条件を満たすとする． 11
- 12. 元論文の説明（３） generateinitial layout(G) while not donedo for n ∈G do x := position[n] G := τx(G) x := force directedplacement(n, G ) position[n] := τ?1 x (x ) end end すると，リーマン多様体上における バネモデルレイアウトのアルゴリズムは以下のようになる 12
- 13. なるほど よくわからん！ 13
- 19. 球面幾何上へのグラフレイアウト（１） 極座標表記 x y z φ θ a 半径１の単位球面を考えると 球面上にある任意の点 a (x, y, z)は θ [0, 2π) とφ [0, π) で表せる 19
- 21. 球面幾何上へのグラフレイアウト（３） 接ベクトル空間 x y z a ua va 任意の点 a の接ベクトル ua, va は ua = (?cosθcosφ, sinθsinφ, sinθ) va = (sinφ, cosφ, 0) と表わせ，点 a に及ぼす力は この接ベクトル空間で考えることができる 21
- 22. 球面幾何上へのグラフレイアウト（４） ２点間に及ぼす力 x y z a b いま点 a, b があり 点 a が b へ，ある力 F(a, b)で 引き寄せられているとする このときの F(a, b)について考える 引き合う力 22
- 23. 球面幾何上へのグラフレイアウト（５） 接ベクトル空間への写像と力の向き まず，点 b から 点 a の 接ベクトル空間への写像 b について考える ベクトル a b が 局所空間で 点 b が 点 a に 及ぼす力の向きとなる x y z a b b 力の向き 23
- 24. 球面幾何上へのグラフレイアウト（６） 直線 b b 点 b を通りベクトル a と 平行な直線 b b を考えると この直線 b b は x y z a b b x ?bx ax = y ?by ay = z ?bz az と表せ，媒介変数 t を使うと x = bx + ax t y = by + ay t z = bz + az t となる aと平行な直線 24
- 25. 球面幾何上へのグラフレイアウト（７） 点 a の接平面 点 a の接平面は x y z a b b ax (x - ax) + ay (y - ay) + az (z - az) となる 25
- 26. 球面幾何上へのグラフレイアウト（８） b の導出（A） x y z a b b ax (x - ax) + ay (y - ay) + az (z - az) x = bx + ax t y = by + ay t z = bz + az t を へ代入すると t が求まる t を x = bx + ax t y = by + ay t z = bz + az t へ代入すると b が求まる 26
- 27. 球面幾何上へのグラフレイアウト（９） b の導出（B） x y z a b b ax (bx + ax t ?ax ) + ay (by + ay t ?ay ) + az (bz + az t ?az ) = 0 (a2 x + a2 y + a2 z )t = a2 x + a2 y + a2 z ?ax bx ?ay by ?az bz t = a2 x + a2 y + a2 z ?ax bx ?ay by ?az bz a2 x + a2 y + a2 z すなわち t は となる．ただし単位球面なので t = 1 ?ax bx ?ay by ?az bz となり，b つまり力の向きが求まる 27
- 28. 球面幾何上へのグラフレイアウト（10） 力の大きさ 点 a, b 間の力の大きさは 点 a, b の球面上の距離 d(a, b) で表される x y z a bψ ただし，球面幾何なので d(a, b)は 点 a, b のなす角ψで表される 28
- 29. 球面幾何上へのグラフレイアウト（11） 点 a, b のなす角ψ 点 a, b のなす角ψは 球面三角法の余弦定理より となる x y z a b N ψ cosψ= cosθa cosθb+ sin θa sinθbcos(φa ?φb) ψ= cos?1 (cosθacosθb+ sinθa sinθb cos(φa ?φb)) 29
- 30. 球面幾何上へのグラフレイアウト（12） 力の向きと大きさ 力の向き b - a と 力の大きさψ が得られた x y z a b b ψ 力の向き 力の大きさ あとは点 a を実際に動かすのみ 30
- 31. 球面幾何上へのグラフレイアウト（12） 点 a の動き x y z a b b ψ 力の向き 力の大きさ 点 a の球面幾何上の動きは， ベクトル (b - a) と a の外積 (b - a)?a を軸として 角度cψだけ回転させれば良い （cは定数） b - a 外積（回転軸） (b - a)?a 任意軸の回転はクォータニオンで 実現可能 31
- 34. ね？簡単でしょう？ 34
- 36. デモ 36
- 37. まとめ ? 数式ではなく考え方を理解する ? 一見難しそうな数式でも，背景にある考え方を理解すれば実装できる ? 考え方がわかれば，数式も理解できる ? とにかく実装してみる ? 数学的な厳密性はあとでじっくり考える ? Try and Errorを繰り返す．たくさん失敗してみる．何度も何度も． ? 美しいは大正義 37