Volvox

サークルパッキング(Circle Packing)画像作成ソフト


Volvoxとは、中学生のとき習ったと思いますが、水の中に入る微生物で、球状の外殻の中に、小さい球が入った形状をしています。(詳しい事は知りません。専門外なので… 検索すれば、いろんな画像が見つかります。)このソフトは、生物のVolvoxとは全く関係はありません。サークルパッキングという、ある領域の中に円を詰め込む数学的な手法を用いて、円の中に円を詰め込んだふしぎな画像を簡単に作れるようにしようというソフトです。

結局何の役に立つのかは自分でもよくわかりませんが(^ ^;)、いじっているだけでも面白いと思いますので、ぜひ使ってみてください。これの役に立ったぞ!!というような報告も、お待ちしております。


目次

なお、操作法のみをまとめたクイックヘルプもあります。


このソフトでできること

突然ですが、上の画像を見てください。円の中に円が互いに接するように並んでいます。このように円をぴったり詰め込むには、円の中心や半径をいくらにすればいいか、正確に計算しなければなりませんが、普通に人間が計算するのは、とても難しい(やりたくもない…)というのはお分かり頂けると思います。このソフトでは、サークルパッキングといわれる、領域内に円を隙間なく詰め込むための数学的な手法を用いる事で、このような画像を簡単に作成することができます。

このソフトでは、作成した円の色や線の太さの変更も可能です。さらに、作成したデータをそのままEMF(Enhanced Meta File)や、EPS(Encapsulated PostScript)エクスポートする事もできますので、Microsoft Officeや、Adobe Illustratorなどのソフトにデータを渡すことで、さらに複雑な編集を行う事も可能です。もちろん、普通のbmp画像ファイルにもエクスポートできます。


Officeでの編集例(グラデーションをかけてみました)

 


グラフとサークルパッキング

サークルパッキングには、いろいろな手法があるようですが、このソフトでは、グラフから円のデータを作成します。ここでのグラフとは、量や割合をわかりやすく示すための、棒やら円やらの種類がある図のほうではありません。数学用語で、実際はもっと大きな意味がありますが、ここでは点と点とのつながりを表す図とでも考えておけばいいと思います。(いいかげんな説明ですが)

さて、このグラフとサークルパッキングに何の関係があるのでしょうか。

上の図を見てください。二つの円が接する場合には、二つの中心の間に線が引かれています。このようなものをグラフと呼ぶわけです。このソフトで扱うグラフでは、点が円を表し、線が二つの円が接するという事を表しています。このソフトは、このグラフから、それに対応するそれぞれの円の大きさ、場所を計算し、出力します。

さて、円同士の接する関係を表しているグラフですが、サークルパッキングに用いるためには、いくつかの条件があります。

  1. グラフの辺(エッジ)が、三角形になっていなければならない。
  2. それぞれの三角形が、辺で繋がっていなければならない。
  3. グラフの外側の点(ノード)が、内側の点(ノード)に繋がっていなければならない。


不適当なグラフの図

これらの条件を満たすグラフがあれば、それから円を隙間なく並べた絵が作れるわけです。

このソフトウエアでのグラフの編集では、1や2のような状態は起こりえないように設計してありますので、ユーザは、3の内部に未接続な外部のノードの事のみを考えればいいことになります。


使用法

インストール

圧縮されたVolvox.zipをlhasaなどで解凍して、適当なフォルダに置いてください。

アンインストール

解凍して出てきたフォルダごと削除してください。ただし、もしファイルタイプを登録した場合は、ファイルタイプ登録の削除を選択してから削除してください。→メニューの説明

グラフ編集の流れ

Volvox.exeをダブルクリックしてください。次のようなウインドウが現れます。

真ん中に見えるのが、グラフの初期状態です。マウスを用いて、グラフを編集していきます。

グラフの、節の部分(小さな四角)をノード、ノードを結ぶ直線を、エッジと呼びます。

グラフの三角形で囲まれた内部にあるノードを、内部ノードと呼びます。囲まれていないノードを、外部ノードと呼びます。外部ノードのうち、内部ノードとエッジで繋がっていないノードを、未接続ノードと呼びます。

エッジのうち、二つの三角形の辺となっているエッジを内部エッジ、なっていないものを外部エッジと呼びます。

これらは色分けで表示されます。この色の設定は、あとで変更する事もできます。グラフとサークルパッキングの項目を読むとわかるように、未接続ノード(デフォルトでは黄色)がなくなるようにグラフを作れば、サークルパッキングを実行する事が可能となります。

マウス操作のインターフェースは、次のようになっています。(重要!)
●マウスで左ボタンを押したまま、ノードをドラッグすると、ノードを移動させる事ができます。
●マウスで、外部エッジ左クリックすると、そのエッジを一辺とするような三角形が出来るように、エッジ、ノードが追加されます
●マウスで、左クリックすると、その点が内部ノードになるように、エッジが追加されます
●エッジが2つしか繋がっていない未接続ノードをクリックすると、そのノードが削除されます。
両端のノードが、共通の内部ノードと繋がっているような外部エッジクリックすると、そのエッジが削除されます。

前にも書いたように、内部ノードに未接続の外部ノードがなくなるようにグラフを作成してください。グラフが出来たら、ツールバーのボタンをクリックしてください。円が円の中に敷き詰められるはずです。グラフは、各ノードが対応する円の中心に来るように自動的に変形されます。

 

円編集の流れ

円が生成されたら、次に各円の色や線の太さを決定します。円表示&編集モードに移るには、ツールバーのを押します編集→アンチエリアシングを選択することで、滑らかに表示させる事が出来ますが、描画に時間がかかります。

円を左クリックすると、選択状態になりますので、に見える円設定バーで色や線の太さを決定してください。SHIFTCTRLキーを押しながらクリックする事で、複数の円も選択できます。

円を複数同時に選択するには、その円の付近で左ドラッグしてください。長方形が描かれます。ボタンを離した時点での長方形に触れた円が選択されます。SHIFTキーやCTRLキーを押しながらドラッグすれば、さらに加えて選択できます。

さらに、グラデーション機能もつけてみました。各円の中心座標に応じて色を自動設定する機能です。円の中もグラデーションになるのではありません。→下のサンプルを参照。グラデーションの色の設定は、円設定バーの下の部分で行います。二つの色のうち、左側が始点の色です。その下のボタンでは、グラデーションをどこ(線、内部)に適用するか設定できます。

実際にグラデーションで円の色を変えるには、まず色を変えたい円を選択してください。そのあと、円設定バーの下のほうのボタンをクリックします。線形グラデーションの場合は線形ボタン、円形グラデーションの場合は円形ボタンを押してください。その後、ビューを左ドラッグすると、ドラッグの始点、終点に応じて、各円の色が変更されます。

グラデーションモードから抜けるには、もう一回円設定バーのボタンを押すか、右クリックします。

グラデーションの始点、終点の座標を、円の中心に自動的に合わせてしまうこともできます。メニューの、表示→設定を参照してください。


グラデーションの使用法


グラデーション使用例

さらに、もっと複雑な編集を加えたい場合は、EMFやEPSにエクスポートして、他のソフトに読み込んでください。普通のビットマップにもエクスポート可能です。

メニューの説明

ファイル(F)メニュー

新規作成

Volvoxファイル(*.vvox)を新規に作成します

開く

Volvoxファイルを開きます

上書き保存

現在のファイルに保存します

名前を付けて保存

別のファイルに保存します

エクスポート→EMF

現在描かれている円を、EMF(Enhanced Meta File)に保存します。Enhanced Meta Fileとは、画面に描く手続きをそのまま記録したようなファイルで、Officeに読み込めば、オートシェイプとして編集する事が可能です。

エクスポート→EPS

現在描かれている円を、EPS(Encapsulated PostScript)に保存します。Adobe Illustratorなどの、EPSを読み込むことが出来るソフトでは、EMFより正確にデータを読み込めると思います。

エクスポート→ビットマップファイル

現在描かれている円を、ビットマップファイル(.bmp)に保存します。設定ダイアログで、『アンチエリアシング』を選択すると、絵をより正確に計算して滑らかな画像を生成します。普通より時間がかかるはずですが、普通の環境で画像がものすごく大きくないのならほとんど違いはわかりません。

エクスポート→テキストファイル

現在描かれている円を、テキストファイルに保存します。テキストファイルのフォーマットは自分で設定する事が出来ます。詳しい事は設定ダイアログに書いてありますが、例えば、

%X, %Y, %R, %IR, %IG, %IB

とすると、各円ごとに一行に、円の中心x座標、y座標、半径、内部色R、内部色G、内部色Bがコンマ区切りで書き込まれます。フォーマット例は、TextExp.txtにもありますので、参考にしてください。

編集(E)メニュー

全て選択

円表示&編集モードのときのみ有効です。外円以外の全ての円を選択します。

選択反転

円表示&編集モードのときのみ有効です。外円以外の円の選択を反転します。

円をコピー

円表示&編集モードのときのみ有効です。選択している円の設定(色、線の太さ)をコピーします。複数選択されている場合、それらの円の共通した性質のみがコピーされますので、ご注意ください。例えば、内側の色が同じで、線の色と線の太さが異なる2つの円を選択していた場合、内側の色だけがコピーされます。

円を貼り付け

円表示&編集モードのときのみ有効です。コピーされた円の設定を、現在選択している円に反映します。

グラフを縮小

グラフ表示&編集モードのときのみ有効です。グラフが大きすぎて編集しにくい場合、グラフ全体を縮小できます。割合は、設定ダイアログで変更できます。これを実行しても、円の座標は変更されません。

クリップボードにコピー

現在描かれている円を、クリップボードにEMFとしてコピーします。エクスポート→EMFとほぼ同じ結果が得られますが、半径は現在表示されている値が使用されます。

表示(V)メニュー

グラフ表示

グラフ表示&編集モードにします。このモードでは、グラフの編集を行います。

円表示

円表示&編集モードにします。円の色や線の太さを編集できます。

アンチエリアシング

円表示&編集モード中に、円を滑らかに描画するようになります。ただし、描画に時間がかかるため、CPUが遅い場合には上手く切り替えて使ってください。

ツールバー&ステータスバー&円設定バー

それぞれのバーの、表示/非表示を切り替えます。

設定

背景色や、グラフのノード、エッジの色、サイズなどを設定できます。

実行(R)メニュー

サークルパッキング

サークルパッキングの計算を実行し、各円の半径や位置の計算を行います。一回の計算で不足の場合は、何回も実行する事で、正確な値を求める事が出来ます。

ノードのランダマイズ

ノードの座標計算の際の順番を変更する事により、より正確な値を求められるようにします。詳しくは、FAQを参考にしてください。

ヘルプ(H)メニュー

ファイルタイプを登録

レジストリに、vvoxファイルの情報を登録し、vvoxファイルのダブルクリックでファイルが開けるようにします。このソフトをアンインストールするときは、登録を削除を実行してください。なお、これ以外にこのソフトがレジストリをいじる事はありません。

登録を削除

レジストリの登録情報を削除します。


FAQ

ありそうな質問をまとめてみました。

Q1.「序数6646がダイナミックライブラリMFC42.DLLから見つかりません」などのメッセージが出て実行できない。

MFCランタイム(Mfc42.dll, Msvcrt.dll)が古過ぎたり、インストールされていなかったりするようです。VectorなどでMFCランタイムを検索してみてください。それをインストールすれば動くようになると思います。

Q2.サークルパッキング実行ボタンを押しても、「内部ノードと繋がっていない外部ノードがあります」と出てしまいます。

グラフの条件として、全ての外側のノード(点)は、内側にあるノード(点)と繋がっていなければならないという条件があります。詳しくは、をご覧ください。内部ノードと繋がっていないノード(デフォルトで黄色)がなくなるようにグラフを作ってください。

Q3.円は生成されましたが、ちゃんときれいに接してくれません。

このソフトでは、内部で繰り返し演算により、パラメータを求めるようになっています。円の数(ノードの数)が多いと、一回ではパラメータが正確でない場合があります。何回も、サークルパッキング実行ボタンを押してみてください。

これでダメな場合は、表示→設定を選び、「Thurston」の所の、閾値を小さくしてみてください。内部の繰り返し演算の精度を上げることができます。※ただし、小さくしすぎると問題が発生する場合もあります。Q9を見てください。

それでもダメな場合、実行→ノードのランダマイズを実行してから、サークルパッキングを実行してみてください。円の中心座標の計算順序を入れ替える事により、より正確になる場合があります。気に入らない場合は、何回も実行してください。

もしそれでもダメな場合は、諦めてください。(- -;) あまり円の数が多すぎると、ちゃんと接する事が難しくなってきます。

Q4.エクスポートしたEMFデータをOfficeで編集しようとすると、円が乱れてしまいます。

詳しい事はよく知らないのですが、EMFへ渡す座標データは整数であるため、小さな画像にしてしまうと不正確になることがあるようです。EMFに出力するときは、画像サイズを大きくすると上手くいくと思います。ちなみに、ビットマップファイルなどと違い、サイズを大きくしてもファイルサイズはあまり変わりません。

EPSへのエクスポートでは、座標は浮動小数点数であるため、EMFよりかなり正確に出力できると思います。

Q5.円が端のほうによってしまったのですが。

実は、このソフトでは始めに中心に配置する円を決め、そこから順に他の円を求めていくというアルゴリズムになっています。中心に配置する円を替えれば、円の配置も全く変わります。中心に配置する円は、ユーザが変更する事ができます

中心に配置する円は、ビューの中心付近にある内部ノードが自動的に選ばれます。そのため、中心付近にわざと中心にしたい内部ノードを持ってくれば、中心の円が変更されます。


はじめの状態で、ノードを2つ目のように移動させて、サークルパッキングを実行すると、円の配置が変わります。

Q6.グラフの操作が難しいのですが。

ちょっと独特な操作法なのですが、このようにした理由は、上でも説明した通りグラフの形状にかなり厳しい制限があるためです。グラフの中に4角形が出来ないようにしたり、グラフが点でつながるような状態にならないようにするには、このソフトのインタフェースのように、操作に制限を加えるのが簡単だと考えました。この制限内で操作していれば、知らず知らずのうちに制限のほとんどがクリアされたグラフができます。不便かもしれませんが、慣れていただきたいと思います。(- -;)

Q7.設定をデフォルトに戻したい。

Volvox.exeと同じフォルダに生成される、Volvox.iniを削除して、再び実行すれば元に戻ります。

Q8.円の線の太さを0にしたら、何だか円同士が離れているように見えてしまいます。

自分の試した範囲では、Win98SEの場合と、Win2000の場合では、Windowsの円描画関数に少し違いがあるようです。Windows2000では、円の線の太さを0に設定すると、ちょっと円の間が離れているように描画される模様です。でも、データ上はぴったり接しているはずです。表示→アンチエリアシングを選択してみてください。アンチエリアシングの場合の描画は、Windowsの円描画関数を使っていないので、環境によらず同じように見えると思います。

Q9.サークルパッキングを実行したら、グラフがおかしくなってしまいました!!


おかしくなった画面

繰り返し計算の閾値を小さくしすぎたため、変な値に収束してしまい起こるようです。表示→設定を選び、「Thurston」の所の、閾値を大きくしてみてください。また、この問題が起こったファイルはエラーが残ってしまう可能性がありますので、データはセーブしない方がいいと思います。こちらの実験では、閾値0.000001で問題が発生しました。

Q10.これの理論は?

実は僕もあまり良くはわかっておりません。授業でちょっと習っただけだったので。理論数学も専門ではありませんし。これは元はその授業のレポートとして作ったJava Appletです。(トップページからたどれます。)それをVC++に移植して、いろいろ機能を追加したのがこれです。これをちゃんと説明するには、双曲幾何学とかその辺の知識が必要です。わかる人に教わってください…


製作&動作環境

製作環境

Windows98SE、Pentium III 550MHz、320MB Memory

VC++6.0 SP5

動作環境

Windows95, 98, Me, NT4, 2000, XP(?)

Mfc42.dll, Msvcrt.dllが必要(98SE以上では元から入っています)


著作権など

このソフトはフリーソフトです。どうぞご自由にお使いください。ただし、このソフトを使って何か問題が起こったとしても責任は負えませんので、各自の責任でお使いください。著作権は作者である私、米澤航太が保有しています。再配布は、アーカイブの中身を変えないようにしてください。転載する場合は、出来れば私まで連絡してください。

バグや感想、要望等がありましたら、メールでお送りください。特にバグの場合は、どのような状況でどんな事が起こったのか詳しく教えていただけると助かります。

このソフトでは、Alger Pikeさんの、CInitDialogBarクラスを使わせて頂いています。(こちらを参照) 素晴らしいコードに感謝いたします。


メール