Delaunay三角形分割アルゴリズム

このプログラムは、Delaunay三角形分割アルゴリズムを使用して線を引いています。このアルゴリズムは、与えられた点の集合を三角形の集合に分割するもので、三角形の外接円に対する空洞の最大化を行います。このアルゴリズムは、三角形網の形成に役立ちます。プログラムは、指定された点を動かすことで、時間が経つにつれて三角形網がどのように変化するかを示しています。また、描画には Processing 言語が使用されています。

ドロネー図 - Wikipedia

import megamu.mesh.*;

final int NUM_POINTS = 200;
float[][] points = new float[NUM_POINTS][2];
float[][] velocities = new float[NUM_POINTS][2];
Delaunay delaunay;

// 設定定数
final color BG_COLOR = color(0, 76, 96);
final color DOT_COLOR = color(0, 176, 196, 255);
final color LINE_COLOR = color(0, 176, 196, 255);
final float DOT_SIZE = 12;
final float LINE_WIDTH = 1;
final float DOT_SPEED_MIN = -1;
final float DOT_SPEED_MAX = 1;

void setup() {
  //fullScreen();
  size(700,300);
  smooth();
  initPoints();
}

void draw() {
  background(BG_COLOR);
  updatePoints();
  drawTriangles();
  drawDots();
}

// 初期化関数
void initPoints() {
  for (int i = 0; i < NUM_POINTS; i++) {
    points[i][0] = random(width);
    points[i][1] = random(height);
    velocities[i][0] = random(DOT_SPEED_MIN, DOT_SPEED_MAX);
    velocities[i][1] = random(DOT_SPEED_MIN, DOT_SPEED_MAX);
  }
  delaunay = new Delaunay(points);
}

// ポイント更新関数
void updatePoints() {
  for (int i = 0; i < NUM_POINTS; i++) {
    points[i][0] += velocities[i][0];
    points[i][1] += velocities[i][1];
    if (points[i][0] < 0 || points[i][0] > width) {
      velocities[i][0] *= -1;
    }
    if (points[i][1] < 0 || points[i][1] > height) {
      velocities[i][1] *= -1;
    }
  }
  delaunay = new Delaunay(points);
}

// 三角形描画関数
void drawTriangles() {
  stroke(LINE_COLOR);
  strokeWeight(LINE_WIDTH);
  int[][] links = delaunay.getLinks();
  for (int[] link : links) {
    float startX = points[link[0]][0];
    float startY = points[link[0]][1];
    float endX = points[link[1]][0];
    float endY = points[link[1]][1];
    line(startX, startY, endX, endY);
  }
}

// ドット描画関数
void drawDots() {
  noStroke();
  fill(DOT_COLOR);
  for (float[] point : points) {
    ellipse(point[0], point[1], DOT_SIZE, DOT_SIZE);
  }
}