2014年4月9日水曜日

Minimum Spanning Treesの経過観察

Minimum Spanning Treesというものを知ってしまった。
昔作ったバウンズボールと組み合わせてリアルタイムに変化する様子を見てみたいと思ったので製作中。

とりあえずボールとそれをつなぐすべての線を表示するところまで終了。
マシンパワーが弱いためか、ボールの数を20個にするとCPUが100%近くまで跳ね上がってしまう。

まだ枝の選別を加えていない状態なのにこれではいけないので、カクカクするがフレームレートを10fpsに下げて、ボールの数も10個に減らした。かなり寂しい。

使っているのはD3.js。最初とまどったが分かると便利。

修正

点の数-1個の線があれば十分なので減らした。とても軽くなり、フレームレートを20fpsまで上げても50個位は描画できるようになった。
試しに、線の長さでソートして最短のものを描画するようにしてみたのが上の図。
これからアルゴリズムを加えていくが、どの程度遅くなるか、どのような動きをするのか楽しみ。