🎡ボロノイ図とドロネー三角形分割 distance関数(= length(p2-p1))
簡単な例として、ある街にある商店群を考えてみよう。ここで、ある店の顧客数を推定したいとする。他のすべての条件（価格，商品，サービスの質など）が同じであれば，顧客は単に距離の考慮によって好きな店を選ぶと仮定するのが妥当である：彼らは自分に最も近い店に行くだろう．
ボロノイ図の双対グラフ（点群からなるユークリッド空間の場合）は、同じ点群に対するドロネーの三角形分割に相当する。
一般に離散点集合Pのドロネー三角形分割は、Pのボロノイ図の双対グラフに相当する。ドロネー三角形の外接はボロノイ図の頂点となる。2次元の場合、ボロノイ図の頂点は、ドロネーの三角形の隣接関係から得られる辺で結ばれています。ドロネーの三角形分割で辺を共有する2つの三角形は、その外周がボロノイ分割の辺で接続されます。
W=98;k=d=m=0;b=[];t=1;I=m=>X=(A,G)=>{var P=G.slice(1);for(var i=m;i--;)P[0]([i,A],P)};q=I(W);z=(A,G)=>{[i,j,p]=A.flat();m=1e5;for(k=W/2;k--;)m=(d=dist(i,j,b[k],b[k+W/2]))<m?d:m;stroke(m*t+W);point(i,j);};draw=_=>{q([],[q,q,z]);t+=.1;};setup=_=>{for(i=W;i--;)b[i]=random(W);}//#p5t pic.twitter.com/9jMjL7uKaQ
— m_oka (@m_oka) October 20, 2022
しくみはいまいちわからないが、たぶんボロのってるコードなのかなと思う。distのところとか
GLSLのコード、距離とって最小とって濃淡付けてというのは同じみたいだが、コードを読んでみても三角形がどうこうというのと直感的につながらない。さて
セルラーノイズではディスタンスフィールドに基づいて、複数の点の中から最も近い点への距離を計算します。4つの点に対してディスタンスフィールドを作りたいとしましょう。どうすれば良いでしょうか。それぞれのピクセルについて、最も近い点への距離を計算したいですね。現在のピクセルからすべての点への距離を繰り返し計算し、最も近い点への距離を記録するようにします。
distance は2点 p0 と p1 の間の距離を返す。つまり、length(p0 - p1) である。
ドロネー三角形分割（Delaunay triangulation）とボロノイ図（Voronoi diagram）は、点の集合を基にした幾何学的な構造であり、密接に関連していますが、それぞれ異なる概念を持っています。
ドロネー三角形分割 (Delaunay triangulation):
これは、2次元の点の集合を基にして、その点たちを三角形で繋ぐ方法です。
三角形分割の中で、任意の三角形の外接円の内部に他の点が存在しないようにします。
この性質により、分割された三角形の角度がなるべく大きくなり、狭い角度を持つ三角形が生成されにくいです。
ボロノイ図 (Voronoi diagram):
2次元の点の集合を基にして、それぞれの点に最も近い領域を生成する方法です。
具体的には、ボロノイ図におけるある領域内の任意の点は、その領域に属する生成点に他の生成点よりも近いです。
それぞれの領域は多角形として描かれ、隣接する領域の境界は、2つの生成点の中点を結んだ直線になります。
ボロノイ図を手動で作成する場合、以下の基本的なステップを参考にすることができます：
点の配置:
まず、平面上に点（生成点と呼ばれる）をいくつか配置します。これらの点が、ボロノイ図の各セルの「中心」となります。
中点の特定:
任意の2つの生成点を選び、それらの中点を求めます。
垂直二等分線の引き方:
2つの生成点を結ぶ線分の垂直二等分線を求めます。この線は、2つの生成点に最も近い領域を分割する境界となります。
境界の確定:
その他の生成点に対しても、2つの点の組み合わせごとに垂直二等分線を引き、境界を確定します。
セルの確定:
ある生成点に最も近い領域をその点のボロノイセルとします。上記の手順で、すべての生成点に対してセルが定義され、ボロノイ図が完成します。
無限の境界:
ボロノイ図には、無限に広がるセルが存在することがあります。これは、その生成点が他の生成点から十分離れている場合に起こります。手動での描画では、このようなセルの境界は適切に切り取られるか、無限に伸びるとみなされます。
平面上に与えられた有限個の点 P={p1,p2,...,pn} に対して、任意の点 pi のボロノイ領域 V(pi) は以下のように定義されます。
let points = [];
let n = 10; // 生成する点の数
function setup() {
createCanvas(400, 400);
colorMode(HSB); // 色をHSBモードで指定
// ランダムな位置に点をn個生成
for (let i = 0; i < n; i++) {
points.push(createVector(random(width), random(height)));
}
}
function draw() {
background(255);
// 各ピクセルについて、最も近い点を見つけて色を決定
loadPixels();
for (let x = 0; x < width; x++) {
for (let y = 0; y < height; y++) {
let nearestPointIndex = 0;
let minDist = dist(x, y, points[0].x, points[0].y);
for (let i = 1; i < points.length; i++) {
let d = dist(x, y, points[i].x, points[i].y);
if (d < minDist) {
minDist = d;
nearestPointIndex = i;
}
}
// 色を点のインデックスに基づいて決定
let col = color((nearestPointIndex * 360 / n) % 360, 80, 80);
set(x, y, col);
}
}
updatePixels();
// 点を黒色で描画
fill(0);
noStroke();
for (let point of points) {
ellipse(point.x, point.y, 5, 5);
}
}
お願い致します