Illustratorでジェネラティブアートを作ってみる6
ボロノイ図
ボロノイ図は、平面上にある複数のサイトと呼ばれる点に基づき、空間を領域に分割する手法です。それぞれの領域（ボロノイ領域と呼ばれる）は、そのサイトに最も近い全ての点から構成されます。
特徴
各サイト（点）からのユークリッド距離を基準に、平面を分割する。
2点の間の境界は、その2点を結ぶ直線の垂直二等分線になる。
この図を使うことで、空間を効率的に分割する方法を視覚的に表現できます。
さて、なんのこっちゃわからんって言われそうなんですけど「任意の点の集合があって、それらの隣接するものとの最短の直線の中点を通る垂線を領域の境界としてそれぞれのサイトの領域を決定したもの。」という事になります。説明が意味不明って言われるとそうなんですけど、上のイメージをみてもらえば理解しやすいかと思います。
自然界では泡なんかが寄り集まった時にこのような構造が見られるわけなんですけど、コンピュータビジョンの領域分割やクラスタリングアルゴリズムや近傍探索などでも応用されるものなんですね。
で、今回はこのボロノイ図をイラレさんに描いてもらうことにしました。
手順
まずサイトとなるランダムに配置された点を生成します。
こんな感じですね。
さらに各点を頂点とした三角形に分割する。
このようにポリゴンメッシュっぽくなります。
続いて、各三角形の外接円を取り、その中心点をリストアップする。
はい、外接円の中心が境界の頂点になりますので、この座標をピックアップします。
この中心点をボロノイセルの境界として線を引いていきます。
はい、完成です。
と、まあ、とんでもなく面倒くさいです。面倒ですが手順自体はそんなに複雑ではありません。
ストレートに処理していけば書けそうです。というか、書きました。
var numPoints = 300;
var lyr = app.activeDocument.layers.add();
lyr.name = "Voronoi";
var wd = 500;
var ht = 500;
var points = [];
for (var i=0; i<numPoints; i++)
{
var x = Math.random() * wd;
var y = Math.random() * ht;
points.push([x, y]);
}
function triangulate(points)
{
var triangles = [];
for (var i=0; i<points.length; i++)
{
for (var j=i+1; j<points.length; j++)
{
for (var k=j+1; k<points.length; k++)
{
if (isValidTriangle(points[i], points[j], points[k], points))
{
triangles.push([points[i], points[j], points[k]]);
}
}
}
}
return triangles;
}
// Find the center and radius of the circumscribed circle
function circumcircle(a, b, c)
{
var d = 2 * ((a[0] - c[0]) * (b[1] - c[1]) - (b[0] - c[0]) * (a[1] - c[1]));
var ux = ((a[0] * a[0] + a[1] * a[1]) * (b[1] - c[1]) +
(b[0] * b[0] + b[1] * b[1]) * (c[1] - a[1]) +
(c[0] * c[0] + c[1] * c[1]) * (a[1] - b[1])) / d;
var uy = ((a[0] * a[0] + a[1] * a[1]) * (c[0] - b[0]) +
(b[0] * b[0] + b[1] * b[1]) * (a[0] - c[0]) +
(c[0] * c[0] + c[1] * c[1]) * (b[0] - a[0])) / d;
var center = [ux, uy];
var radius = Math.sqrt((a[0] - ux) * (a[0] - ux) + (a[1] - uy) * (a[1] - uy));
return {center: center, radius: radius};
}
// Delaunay Condition Check
function isValidTriangle(A, B, C, points)
{
var circle = circumcircle(A, B, C);
var radiusSq = circle.radius * circle.radius;
for (var i = 0; i < points.length; i++)
{
var P = points[i];
if (P!==A && P!==B && P!==C)
{
var distSq = (P[0] - circle.center[0]) * (P[0] - circle.center[0])
+ (P[1] - circle.center[1]) * (P[1] - circle.center[1]);
if (distSq < radiusSq) return false;
}
}
return true;
}
// draw Delaunay
function drawDelaunay(layer, triangles)
{
var red = new CMYKColor();
red.cyan = 0;
red.magenta = 100;
red.yellow = 0;
red.black = 0;
for (var i=0; i<triangles.length; i++)
{
var path = layer.pathItems.add();
path.setEntirePath([triangles[i][0], triangles[i][1], triangles[i][2], triangles[i][0]]);
path.stroked = true;
path.strokeColor = red;
path.strokeWidth = 0.3;
path.filled = false;
}
}
function drawVoronoi(layer, triangles)
{
var black = new GrayColor();
black.gray = 100;
var edges = {};
var circumcenters = [];
for (var i=0; i<triangles.length; i++)
{
circumcenters.push(circumcircle(triangles[i][0], triangles[i][1], triangles[i][2]).center);
}
// connect each center...
for (var i=0; i<triangles.length; i++)
{
for (var j=i+1; j<triangles.length; j++)
{
if (isNeighbor(triangles[i], triangles[j]))
{
var path = layer.pathItems.add();
path.setEntirePath([circumcenters[i], circumcenters[j]]);
path.stroked = true;
path.strokeColor = black;
path.strokeWidth = 0.3;
path.filled = false;
}
}
}
}
function isNeighbor(triangle1, triangle2)
{
var sharedVertices = 0;
for (var i=0; i<3; i++)
{
for (var j=0; j<3; j++)
{
if (triangle1[i][0]==triangle2[j][0] && triangle1[i][1]==triangle2[j][1])
{
sharedVertices++;
}
}
}
return sharedVertices==2;
}
// option draw circles.
function drawCircumcircles(layer, triangles)
{
var blue = new CMYKColor();
blue.cyan = 100;
blue.magenta = 50;
blue.yellow = 0;
blue.black = 0;
for (var i=0; i<triangles.length; i++)
{
var circle = circumcircle(triangles[i][0], triangles[i][1], triangles[i][2]);
var ellipse = layer.pathItems.ellipse(
circle.center[1] + circle.radius,
circle.center[0] - circle.radius,
circle.radius * 2, circle.radius * 2);
ellipse.stroked = true;
ellipse.strokeColor = blue;
ellipse.strokeWidth = 0.5;
ellipse.filled = false;
}
}
function drawPoints(layer, points)
{
var green = new CMYKColor();
green.cyan = 80;
green.magenta = 0;
green.yellow = 100;
green.black = 0;
for (var i=0; i<points.length; i++)
{
var ellipse = layer.pathItems.ellipse(
points[i][1] + 1, points[i][0] - 1, 2, 2);
ellipse.stroked = false;
ellipse.filled = true;
ellipse.fillColor = green;
}
}
var triangles = triangulate(points);
drawVoronoi(lyr, triangles);
drawPoints(lyr, points);このスクリプトの実行時間の大半は三角分割処理に費やされます。とりあえず効率の良い書き方よりもコンセプト自体を実装する目的で総当り的な処理になっています。本来ならトラップするべきエリア外に伸びた極端な辺が生じたりしますが、特にエラーも生じないので放置です。不必要な部分は人間が削除してしまえばOKなので。
このあと、線を選択したうえで太くしてアウトラインを取ってから合体した上で角を丸めるとトップのイメージのようなものが出来ます。
で、ですね、あまりにも実行負荷が高いのでなんとかならないものかとChatGPTに評価させてみました。
以下、一般的に用いられるフォーチューンのアルゴリズムとの比較評価の抜粋
このスクリプトは、デロネー三角分割（Delaunay Triangulation）を利用してボロノイ図を描画する手法を実装しています。デロネー三角形の外接円の中心を求め、それらを結ぶことでボロノイ図を構築しています。一方、フォーチュンのアルゴリズムは、スイープライン法を用いて直接ボロノイ図を構築する手法です。
- 計算量の比較
アルゴリズム 計算量（理論値）
フォーチュンのアルゴリズム 𝑂(𝑛・log 𝑛)
本スクリプト 𝑂(𝑛^3)（ナイーブ実装）
三角形を得る部分が三重ループ（全ての点の組み合わせを試す）になっており、最悪の場合𝑂(𝑛^3)の計算量になっています。
O(n log n) で動作するため、大規模なデータ（例えば1000点以上）では圧倒的に高速です。
ですよね〜三重ループはクソ重くなるよなってわかっててもやらんと仕方ないんやと思いつつ、なら、このコードをスキャンラインでなんとかするようなものに書き換えてみ？って思いました。ということでChatGPTに丸投げして出来たのが以下です。ちなみに動くようになるまで10か所程度の手直しが必要でしたｗ
var numPoints = 300;
var wd = 500;
var ht = 500;
var lyr = app.activeDocument.layers.add();
lyr.name = "FortuneVoronoi";
var points = [];
for (var i=0; i<numPoints; i++)
{
points.push([Math.random()*wd, Math.random()*ht]);
}
function dist(p1, p2)
{
return Math.sqrt((p1[0]-p2[0])*(p1[0]-p2[0]) + (p1[1]-p2[1])*(p1[1]-p2[1]));
}
function computeVoronoi(points, width, height)
{
var edges = [];
var step = 1;
for (var x=0; x<width; x+=step)
{
for (var y=0; y<height; y+=step)
{
var closest = null;
var minDist = Infinity;
for (var i=0; i<points.length; i++)
{
var d = dist([x, y], points[i]);
if (d < minDist)
{
minDist = d;
closest = i;
}
}
if (x>0 && y>0)
{
var left = closestPoint([x-step, y], points);
var top = closestPoint([x, y-step], points);
if (left !== closest) edges.push([[x, y], [x-step, y]]);
if (top !== closest) edges.push([[x, y], [x, y-step]]);
}
}
}
return edges;
}
function closestPoint(p, points)
{
var minDist = Infinity;
var index = -1;
for (var i=0; i<points.length; i++)
{
var d = dist(p, points[i]);
if (d<minDist)
{
minDist = d;
index = i;
}
}
return index;
}
function drawVoronoi(layer, edges)
{
var black = new GrayColor();
black.gray = 100;
for (var i=0; i<edges.length; i++)
{
var pth = layer.pathItems.add();
pth.setEntirePath(edges[i]);
pth.stroked = true;
pth.strokeColor = black;
pth.strokeWidth = 0.3;
pth.filled = false;
}
}
function drawPoints(layer, points)
{
var red = new CMYKColor();
red.cyan = 0;
red.magenta = 100;
red.yellow = 100;
red.black = 0;
for (var i=0; i<points.length; i++)
{
var ellipse = layer.pathItems.ellipse(
points[i][1] + 2, points[i][0] - 2, 4, 4);
ellipse.stroked = false;
ellipse.filled = true;
ellipse.fillColor = red;
}
}
var edges = computeVoronoi(points, wd, ht);
drawVoronoi(lyr, edges);
drawPoints(lyr, points);このコードの実行結果は以下のようになります。
基本的にスキャンラインなんてビットマップ処理でもないIllustratorとは相性が悪いのでグリッドによるサンプリングによるフォーチューンのアルゴリズム実装になっています。で、単位グリッドで境界を見ていきますからデロネー三角分割のように境界自体を直線で得ることは出来ません。結局ビットマップ処理と同じことをやるしか無いんですけど、これ、グリッドを細かく取るとアホみたいに時間食います。
まあ、色々見てみると知見が増えるのでヨシとしましょう。
ボロノイ図は都市計画なんかにも応用されるんですけど、デザイン上の特徴点をウエイト付けした上で階層化したものをボロノイ図化して自動評価用のデータとして運用する方法を考え中で、スクリプト自体も後ほど真面目にチューニングします。
