processingの備忘録　-ボロノイ図- - プログラミングの備忘録

こんにちは。
今回は processing で「ボロノイ図」を描画する、という題です。

おそらく「ボロノイ図　processing」などで調べれば数多出てくるものだとは思いますが、やりたいのでやります。

ボロノイ図とは
プログラム
- 正攻法
- 成長法
まとめ
参考

ボロノイ図とは

ボロノイ図は、ある点 (母点) の集まりについて、ある位置からどの母点が一番近いかによって区分けをした図です。
距離の取り方によって図の雰囲気は変わるようですが、特に「ユークリッド距離」 (最も一般的なもの) で考えた場合は、各母点間を垂直二等分線で分けたような図になります。

割といろいろなところで見られる図であり、知らないうちに身近にあるかもしれません。

プログラム

今回はユークリッド距離で考えたボロノイ図を描くこととします。

正攻法

どの母点が一番近いかによって色分けをしています。

int n = 50;
PVector[] p = new PVector[n];
color[] c = new color[n];

void setup(){
  size(500, 500);
  
  // 母点の位置と領域の色
  for(int i = 0; i < n; i ++){
    p[i] = new PVector(int(random(width)), int(random(height)));
    c[i] = color(int(random(256)), int(random(256)), int(random(256)));
  }
}

void draw(){
  // 描画範囲内の点全てについて
  for(int x = 0; x < width; x ++){
    for(int y = 0; y < height; y ++){
      
      // 一番近い母点を探す
      float dmin = dist(0, 0, width, height);
      int j = 0;
      for(int i = 0; i < n; i ++){
        float d = dist(x, y, p[i].x, p[i].y);
        if(d < dmin){
          dmin = d; // 一番近い母点との距離
          j = i; // 一番近い母点の番号
        }
      }
      
      // setupで指定した色に従って塗り分ける
      set(x, y, c[j]);
    }
  }
  
  // 母点の位置の描画
  for(int i = 0; i < n; i ++){
    fill(0);
    float dia = 2;
    ellipse(p[i].x, p[i].y, dia, dia);
  }
}

実行すると、

ボロノイ図が描けています。

この方法では母点の位置と領域の色を与えれば描いてくれるのでいじりやすいです。

例えば、クリックで母点の追加ができるようにすると、

int n = 1;
ArrayList<PVector> pos = new ArrayList<PVector>();
IntList R = new IntList();
IntList G = new IntList();
IntList B = new IntList();

void setup(){
  size(500, 500);
  
  // 母点の位置と領域の色
  for(int i = 0; i < n; i ++){
    pos.add(new PVector(int(random(width)), int(random(height))));
    R.append(int(random(256)));
    G.append(int(random(256)));
    B.append(int(random(256)));
  }
}

void draw(){
  // 描画範囲内の点全てについて
  for(int x = 0; x < width; x ++){
    for(int y = 0; y < height; y ++){
      
      // 一番近い母点を探す
      float dmin = dist(0, 0, width, height);
      int j = 0;
      for(int i = 0; i < pos.size(); i ++){
        PVector p = pos.get(i);
        float d = dist(x, y, p.x, p.y);
        if(d < dmin){
          dmin = d;
          j = i;
        }
      }
      
      // setupで指定した色に従って塗り分ける
      int r = R.get(j);
      int g = G.get(j);
      int b = B.get(j);
      set(x, y, color(r, g, b));
    }
  }
  
  // 母点の位置の描画
  for(PVector p: pos){
    fill(0);
    float dia = 2;
    ellipse(p.x, p.y, dia, dia);
  }
}

void mousePressed(){
  pos.add(new PVector(mouseX, mouseY));
  R.append(int(random(256)));
  G.append(int(random(256)));
  B.append(int(random(256)));
}

初めは母点が1つですが、クリックした場所に母点が追加され、ボロノイ図が更新されていきます。

また、先にも書いたように、距離の計算にユークリッド距離を使うと一般的なボロノイ図になります。

しかし距離の計算方法にはいろいろあるようで、それらの違いによって図の雰囲気も変わってきます。

マンハッタン距離

距離 d の計算方法を以下のように変えると、

float d = abs(p[i].x-x) + abs(p[i].y-y);

チェビチェフ距離

距離 d の計算方法を以下のように変えると、

float d = max(abs(p[i].x-x), abs(p[i].y-y));

ミンコフスキー距離

距離 d の計算方法を以下のように変えると、

float a = abs(p[i].x-x);
float b = abs(p[i].y-y);
float pp = 5;
float d = pow(pow(a, pp) + pow(b, pp), 1/pp);

（これが本当にミンコフスキー距離かは不安ですが、これはこれで良い感じなので良しとしました。）

pp の値によって変わります。
pp = 2 でユークリッド距離と同じものになります。

成長法

「成長法」のネーミングは適当です。~~（正攻法と韻を踏んでて良い。）~~

ボロノイ図って細胞っぽいよねってことで、同心円状に成長していく過程でぶつかって角ができ、ボロノイ図になる、という描画方法です。

int n_cells = 20;
Cell[] cells = new Cell[n_cells];

void setup(){
  size(500, 500);
  
  // 母点の位置の指定
  for(int i = 0; i < n_cells; i ++){
    cells[i] = new Cell(i, random(width), random(height));
  }
}

void draw(){
  background(0);
  
  for(int i = 0; i < n_cells; i ++){
    cells[i].calc();
    cells[i].display();
    cells[i].collision(cells);
  }

  for(int i = 0; i < n_cells; i ++){
    cells[i].update();
  }
}


class Cell{
  int id;
  float xo, yo;
  int n = 500;
  float[] r = new float[n];
  float[] t = new float[n];
  PVector[] p = new PVector[n];
  boolean[] f = new boolean[n];
  
  Cell(int _id, float _xo, float _yo){
    id = _id;
    xo = _xo;
    yo = _yo;
    
    for(int i = 0; i < n; i ++){
      r[i] = 0;
      t[i] = map(i, 0, n, 0, 2*PI);
      p[i] = new PVector();
      f[i] = false;
    }
  }
  
  // 細胞を形作る点の座標を計算
  void calc(){
    for(int i = 0; i < n; i ++){
      p[i] = new PVector(xo + r[i]*cos(t[i]), yo + r[i]*sin(t[i]));
    } 
  }
  
  // 描画
  void display(){
    // 細胞
    fill(255);
    noStroke();
    beginShape();
      for(int i = 0; i < n; i ++){
        vertex(p[i].x, p[i].y);
      }
    endShape();
    
    // 母点
    fill(255, 0, 0);
    ellipse(xo, yo, 5, 5);
  }
  
  // 細胞の半径を伸ばしていく
  void update(){
    for(int i = 0; i < n; i ++){
      if(f[i] == false){
        r[i] += 0.5;
      }
    }
  }
  
  // 細胞同士の衝突を判定
  void collision(Cell[] cells){
      for(Cell c: cells){
        if(c != this){
          
          for(int i = 0; i < n; i ++){
            for(int j = 0; j < n; j ++){
              
              if(f[i] == false){
                
                float d = PVector.dist(p[i], c.p[j]);
                
                if(0 < d && d < 2){
                  f[i] = true;
                }
              }
            }
          }
        }
      }
    }
}