円のあつまりを囲う線を書く

2008 BLOG

ちょっとした幾何学のTips.

Enclosingcircles-2

先に紹介したMashupアプリのプロトタイプの画面で、ミックスしたいループのオブジェクトを線で囲むと、それらをきれいに囲う線が現れたのを覚えているだろうか? 人間なら子供でも簡単に書けるが、コンピュータに書かせようとすると、ちょっとした幾何の計算が必要になる。ある特定の円に対する接線の導出なら簡単だが、円の「集合」を包む場合にはどうしたらいいのだろう? アルゴリズムを考えていたところ、ぴったりな問題と回答を発見した。

石畑 清(明治大学理工学部)
連載Program Promenade「円の集まりをロープで囲む」 (情報処理学会論文誌、2003年 4巻9号) [PDFファイル]

アルゴリズムの基本はこんな感じ。

1. 一番右下にある円を総当たりで探す
2. 1の円から見て、共通接線とx軸の角度が一番大きくなる円を選択。
3. 2の円から見て、共通接線…  (以下、繰り返し)

200803111330

一番右の円にロープをかけて、時計回りに順にぐるっと巻いていくような感じだ。かなり直感的な解である。Processingのデモを作ったのでご参考までに。 アルゴリズムは石畑先生のソースのままだが、囲う線の長さを求めるのではなく、線を描画できるように少しだけ修正した。(クリックすると円をランダマイズする)

Appletstart-4


ちなみに当初の画面はこんな感じだった。とりあえずは審美的な観点から、上記の表現を採用したが、実際はどちらがミックスの表現としてわかりやすいのだろうか… 

Prev Interface

音楽を構成する要素の視覚的な表現は、AudioPadやReacTableなどの先進的なプロジェクトはもちろんのこと、各種商用ソフトウェアでも多種多様な手法が試されている。一度包括的にサーベイする必要がありそうだ。

[ 関連本 ]


“Visualizing Data” (Ben Fry)

Processingの共同開発者の一人、Ben Fryがデータの可視化について語った本。情報デザインの本にありがちな概念のみをつらつらと書き連ねた本とは異なり、読んだ人がすぐに使えるテクニックが満載。Processingの実際のコードも多数掲載している。特にデータ間の補完のテクニックなどは、え、そんなに簡単な方法なんだ!と目から鱗が落ちた。