jsとcanvasでグラフの描画(力学モデル)を実装した

jsとcanvasでグラフの描画(力学モデル)を実装した
LINEで送る
Pocket

こんにちは。

今回は、力学モデル (グラフ描画アルゴリズム) – Wikipediaというグラフを描画するための面白いアルゴリズムを見つけたので、
こいつをjavascript(CoffeeScript)とcanvasで実装してみました。

目次

  • 動作デモ
  • 用語の整理
  • 基本的な理論のおさらい
  • ノードの実装
  • グラフの実装
  • Canvasユーティリティの作成
  • 初期化処理

動作デモ

まずはこちらを御覧ください。
5つの丸が、ふわふわ動いてバランス良い配置になると思います。

用語の整理

まず、グラフとは、折れ線グラフ円グラフのようなものではありません。
頂点と辺の集合で構成されている方のグラフです。

グラフ理論 – Wikipedia

グラフとは、↑のグラフのことで、
グラフの頂点のことをノード
ノードの点と点を繋ぐ辺をエッジと呼びます。

基本的な理論のおさらい

力学モデルのwikiに書いてある通りですが、少し噛み砕いてみます。

まず、ノードの座標決定には
クーロンの法則フックの法則という法則が絡んできます。

どちらの法則も、
要はノード同士が引き合う/反発する力は徐々に安定へ収束するというだけです。

この2つの法則を元に各ノード同士に働く力を計算し、
その力を元に座標を決定します。

ノードの実装

早速実装に移ります。
コードはCoffeeScriptで書きます。

まず、ノードに最低限必要な物は、
x座標, y座標, 半径, x方向の速度, y方向の速度の5つです。

ごくシンプル。

今回はそれに加えて、

  • 各ノードに固有のIDを持たせたい
  • 中にテキストを表示したい
  • ランダムに背景色をつけたい
  • ノード同士の接続情報をグラフではなくノード同士に持たせたい

ということで最終的に以下のような定義になりました。

グラフの実装

今回のキモ、力指向グラフです。
balanceメソッドが、このグラフに属する各ノードの位置を計算します。

wikiに書いてある擬似コード、ほぼそのままだと思います。

Canvasユーティリティの作成

今回はcanvasで実装するので、さくっとcanvasのユーティリティを作ります。

_drawGraph()では、

  1. 接続されているノード同士を全て線分で繋ぐ
  2. 各ノードの背景を描画し、テキストを入れる

ということを行っています。

初期化処理

↑の3つだけではクラス定義でしかないので、初期化します。

最初の方はあまり意味がなく、canvasのサイズ調整をしているだけです。

いくつかノードを生成して、
そのノードのインデックスを渡して接続します。

そして、そのグラフのインスタンスをcanvasにadd(↑のCanvasクラスを参照)して、
50ミリ秒ごとに再描画をかけています。

というコードになっております。 コードベースでの解説となってしまいましたが、これで説明は以上です。

jsdo.itでも公開していますが、
一応zipのダウンロードリンクも貼っておきます。

ダウンロード

参考

» Force-based graph drawing in AS3

LINEで送る
Pocket

Comments are closed.