§ 表現手法コレクション
2008/03/26
さまざまな表現手法・アルゴリズムと、関連する資料やツールについて まとめるページです。
TSP Art
調べ物をしてたら TSP Art という頁を見つけまして、
率直に言って「凄い！ 凄いフィルタだね！ ところで TSP って何？」と思ったのですが、TSP は Traveling Salesman Problem （巡回セールスマン問題 ＝ 「セールスマンが所定の数の都市を1回だけ巡回する場合の最短経路を求める」問題（Wikipedia））のことで、例えば配送や配管の経路を決めたりするときに出てくる典型的難問のようなんですけど、その解決手法を応用して、点を繋いで線を描くと、上記サイトのような絵になるらしいです。
つまりフィルタ一発、というわけではなくて、それどころか、「約2000都市以内ならば普通のパーソナルコンピュータでも、およそ１日以内で厳密解を得られることが多い 」（上記 Wikipedia ）ってオイオイ、な、別の意味でも凄いものだったわけです。
…自転車です。
経路を見つけるには、作り方 の中でリンクされてる CONCORDE というソフトを使いました。点 1000 個から 自転車を描く経路を見つけるために 10分弱かかりました。（CPU:1.8GHz AMD Sempron） 500 個だと１分もかからなかったので、もっと点を増やすと、かかる時間も加速度的に増えるんだろうと思われます。（ CONCORDE は学術研究用途のみ無償のようです。）1000個の「都市」の位置を決めるためには、同じく 作り方 の中でリンクされているVoronoi Stippler というソフトを使いました。このソフトのコードは GPL に基づく copyleft ライセンスです。
各ソフト間でデータを出入力するには、出力データに対して色々加工が要るので、ちょっと面倒です。が、Voronoi Stippler は、これだけでも かなり凄いツールだと思います。画像を、見る間に こんな↓ドット絵にできちゃうんだから、これからはポチポチと点を打って図版の陰影を描くことは無いかも。
その他
- Spidron: