グラフ可視化ツールと手法のまとめ

レイアウトの種類

Force-directed 力指向レイアウト	Planar 平面グラフ	Orthogonal 直交レイアウト	Circular 円状レイアウト	Radial 放射状レイアウト	Tree 木構造レイアウト	Hierarchical 階層レイアウト
頂点間に斥力、辺の間に引力が 働くような力学モデルに基づいて エネルギーを最小化させる	辺同士の交差を 最小化させる	辺が軸に平行に なるよう配置する	頂点を同心円上に 配置する	中心から放射状に 配置する	木構造のレイアウト	DAG（有向非巡回グラフ） のレイアウト

グラフ可視化ツールの手法

レイアウトの種類	yFiles	NetworkX	igraph	graph-tool	GraphViz	Gephi	Cytoscape	Mathematica
Force-directed	Organic	spring → [FR91] kamada_kawai → [KK89]	DrL → [MBW07] fruchterman_reingold → [FR91] kamada_kawai → [KK89] gem → [FLM94] graphopt → (graphopt) davidson_harel → [DH96] lgl → [ADWM04, FR91]	sfdp → [Hu05] fruchterman_reingold → [FR91] arf → [Geipel07]	neato → [GKN04] fdp → [Hu05] sfdp → [Hu05]	Fruchterman-Reingold → [FR91] Yifan Hu Multilevel → [Hu05] OpenOrd → [MBKB11] ForceAtlas2 → [JVHB14]	Edge-weighted Spring-Embedded Prefuse Force Directed	SpringEmbedding → [Hu05] SpringElectricalEmbedding → [Hu05]
Planar		planar		planar → [CP95]				PlanarEmbedding
Orthogonal	Orthogonal
Circular	Circular	circular shell	circle reingold_tilford_circular → [RT81]	get_hierarchy_control_points → [Holten06]	circo → [GK06]	Circular → (GitHub)	Attribute Circle Group Attributes Circular	CircularEmbedding BalloonEmbedding StarEmbedding
Radial	Radial			radial_tree	twopi	Radial Axis → (GitHub)		RadialEmbedding
Tree	Tree		reingold_tilford → [RT81]					TreePlot → [BETT98]
Hierarchical	Hierarchical		sugiyama → [STT81]		dot → [TSE93, NW01]		Hierarchical	LayeredGraphPlot → [STT81, GKNV93]

ツールとレイアウトの種類ごとにサポートされている手法をまとめた。 元になる論文が見つかったものは横に記載

RGBとRYB、色相環の話

色空間ごとの色相環（左：RGB(HSV)、中：RYB(文献1)、右：RYB(文献2)）

色彩理論では色相環上での反対位置（補色）や正三角形の位置にある色同士は相性がいいらしい。→配色の調和

ただし、ここでいう色相環とはマンセル表色系など人間の知覚に基づいた色空間上のものであり、ただ HSV をずらっと並べてもガタガタな輪っかしかできない。

例：
qiita.com
design-spice.com

とりあえず RGB より良さそうで実装が簡単そうな RYB(Red-Yellow-Blue) 表色系について調べた。

(1) RYB Color Compositing

文献1は文献2が RYB → RGB の非可逆変換であることを指摘し、相互変換可能な手法を提案している。
誤差がほぼゼロで変換も簡単なので汎用性は高そう。
この手法で作った色相環がトップ画像中央のもので、RGB と比べるとオレンジの幅が広くなったのと紫が薄くなった印象があるけどあんまり滑らかな感じはしない…

(2) Paint Inspired Color Mixing and Compositing for Visualization

文献2は RYB 三次元空間上の8つの格子点それぞれに対応する RGB 値を置き、その間を線形補間することで RYB → RGB への変換を行うもの。
この手法の結果がトップ画像右のもので、左二つより大分いい感じがする。
RYB への逆変換を行う方法についての議論は見つかったが未解決なようなので、実用するとしたら近似するしかないのかな。

参考文献

(1) RYB Color Compositing
(2) Paint Inspired Color Mixing and Compositing for Visualization（誤植修正版）
(3) transformation - RYB and RGB color space conversion - Mathematics Stack Exchange
(4) 配色の調和 | 基礎編 | TOYO INK 1050+

以下ソースコード

人狼(ジャッジメント)用盤面整理ツール

人狼でCOや占い結果を整理するためのツールを作った。
ジャッジメント用に作ったものだがキャラクターは差し替え可能なので任意の人狼に対応できると思う。

動作環境：Windows10
ダウンロード：https://drive.google.com/uc?id=1Clt6nq7GRYY9m8BtURwxQwVAEKUJqx_8

自作言語ボツ構文集

自作言語を作っていて、一度考えはしたものの結局ボツになった構文。

1. return return x

意味：呼び出し元の呼び出し元に x を返す
ボツの理由：実用性がない

id = (x -> return return x)

func = (n ->
    sum = 0
    for i in 1:n do(
        sum += id(i)
    )
    return sum
)

func(4) //なぜか10ではなく1が返る

もちろん return はいくつでも繋げられる。
ちなみに continue continue や break break は普通に使いどころがありそうなので入れようか迷っている。

2. 半開区間をループに使う

xs = [1,2,3,4,5]

sum = 0
for i in [0, xs.size) do(
    sum += xs[i]
)

意味：0 から xs.size-1 までの間 i に 1 ずつ足しながら do 以下を実行する
ボツの理由：テキストエディタで括弧の対応が狂う

3. 閉区間をループに使う

xs = [1,2,3,4,5]

sum = 0
for i in [1, xs.size] do(
    sum += xs[i-1]
)

意味：1 から xs.size までの間 i に 1 ずつ足しながら do 以下を実行する
ボツの理由：リスト記法と衝突してるので、リスト走査（foreach的な）と紛らわしい気がする

4. 1..10

意味：1～10 の範囲を表す値
ボツの理由：数字のパースにライブラリ組み込みのやつを使ったら、 1. を読んだ時点で浮動小数点数の1と解釈してしまうみたいな感じだった気がする。
とりあえず範囲は 1:10 で表すようにしたけどこれはこれで別の構文と衝突しているのでやっぱり .. にするかもしれない。

5. タプル

p1 = (1, 2)
p2 = (7, 3)
v = p2 - p1

ボツの理由：カンマ区切りの式を括弧で括ったものと完全に衝突する
丸括弧で括ったデータ構造が作れると座標の表記を数学に合わせられるので入れたかった
リストでもそんなに困らない。

6. 関数/演算子オーバーロード

//2次元ベクトルの和と差
operator(+) = (v1 is vec2, v2 is vec2 -> vec2{x: v1.x + v2.x, y: v1.y + v2.y})
operator(-) = (v1 is vec2, v2 is vec2 -> vec2{x: v1.x - v2.x, y: v1.y - v2.y})

//行列積
operator(*) = (m1 is mat2x2, m2 is mat2x2 -> mat2x2{
    a: m1.a*m2.a + m1.b*m2.c, b: m1.a*m2.b + m1.b*m2.d, 
    c: m1.c*m2.a + m1.d*m2.c, d: m1.c*m2.b + m1.d*m2.d
})

ボツの理由：型がないとさすがに厳しそう
この言語に静的型は無く、型のように見える vec2 と mat2x2 はただの値。
引数に a is b と書くと与えられた引数 a とひな型となる値 b の構造を比較して合ってれば関数を実行するという感じになる。
でもやっぱり実際に走らせるまでどの関数が呼ばれるかわからないのは怖いと思うのでやめた。

ピクセルシェーダで空を描く

Siv3Dが(2D限定で)ピクセルシェーダをサポートしたらしいので、GPU Gems 2に載っていた大気散乱シミュレーションのコードを移植してみました。頂点シェーダからそのままピクセルシェーダに移しただけなので少し遅いです。

大気散乱シミュレーションについては、このページの参考文献に高品質な実装法の紹介があるので、興味のある人はそちらを読むといいと思います。（自分はインクを塗るのに忙しくてまだ読んでない。）

あと、地形生成のソースコードはここからお借りしました。
以下スクリーンショットとソースコードです。

平行

#include <Siv3D.hpp>

const double eps = 1e-8;

bool isZero(const Vec2& v)
{
	return v.length() < eps;
}

bool operator||(const Vec2& v1, const Vec2& v2)
{
	return !isZero(v1) && !isZero(v2) && (1.0 - eps) < Abs(v1.normalized().dot(v2.normalized()));
}

void Main()
{
	const Vec2 v1(1, 0), v2(-1, 0), v3(1, 1);
	Println(v1 || v2);
	Println(v1 || v3);
	WaitKey();
}

春休み中はブログたくさん更新する予定だった…

加算ブレンドでメタボールっぽい表現

円形の光の画像を用意して、加算ブレンドでたくさん描画した後、比較ブレンド？で閾値以下の明度の部分を単色で塗りつぶせばそれっぽくなりそうと思った。

光の画像はここの濃度分布関数を参考にして作った。
http://www.syuhitu.org/other/meta/meta.html

ソースコード

#include <Siv3D.hpp>

//濃度分布関数に基づいてImageを作成
Image BallImage(int size)
{
	const double ts=0.1,te=1.0;
	const double C=1.0;
	const int radius=size/2;
	
	const Vec2 center(radius,radius);
	Image image(size,size);
	for(int y=0; y<image.height; ++y)
	{
		for(int x=0; x<image.width; ++x)
		{
			const double tm = Vec2(x,y).distanceFrom(center)/radius;
			const double a = Min(tm-te,0.0);
			const double Cm = C*a*a/(ts-te)/(ts-te);
			image[y][x] = ColorF(Cm);
		}
	}
	
	return image;
}

void Main()
{
	const int threshold = 250;
	const Texture texthr(640,480,Color(threshold));
	const Texture texball(BallImage(200));

	std::vector<std::pair<Vec2,Vec2>> balls(70);
	for(auto& ball : balls)
	{
		ball.first = Vec2(Random(0,640),Random(0,480));
		ball.second = Vec2(Random(-1.0,1.0),Random(-1.0,1.0));
	}

	while(System::Update())
	{
		Graphics::Set2DBlendState(true,Blend::SrcAlpha,Blend::One,BlendOp::Add);
		for(auto& ball : balls)
		{
			ball.first += ball.second;
			texball.drawAt(ball.first);
		}

		Graphics::Set2DBlendState(true,Blend::One,Blend::One,BlendOp::Max);
		texthr.draw();
	}
}

実行結果

メタボール部分のRGB値がそれぞれ255でそれ以外の部分が250だから大分見づらい。

最後の比較ブレンドを省いて赤くしたのが一番上に貼った画像で、こっちは見やすいけど有効範囲の外にまで色がついてしまっている。まあ工夫すればどこかで使えるかもしれない。

牛乳

せっかくなので、Box2Dを使って流体っぽくしてみた。