Delaunay and Voronoi - OpenProcessing

mySketch
xxxxxxxxxx
 
/**
 * Basic code for creating Delaunay triangulations / Voronoi diagrams
 * using a Poisson distribution of points
 **/
​
const n = 100;
let points;
let delaunay, dt, vp, vdi;
​
function setup() {
  createCanvas(windowWidth, windowHeight);
  const avgArea = width * height / n;
  const avgSize = sqrt(avgArea);
  const poisson = new PoissonDiskSampling({
    shape: [width * 2, height * 2],
    minDistance: avgSize,
    maxDistance: 1.5 * avgSize,
    tries: 10
  });
  points = poisson.fill().map(([x, y]) => [x - width / 2, y - height / 2])
  delaunay = Delaunator.from(points);
  vp = voronoiPolygons ();
  dt = delaunayTriangles();
  vdi = voronoiDelaunayIndices();
}
​
function pointInTriangle(p, tri) {
  let v = [];
  for (let i of [0,1,2]) {
    v[i] = createVector(...tri[i]).sub(createVector(...tri[(i+2)%3]))
  }
  let c = [];
  for (let i of [0,1,2]) {
    let u = p5.Vector.sub(p,tri[i]);
    c[i] = p5.Vector.cross(u,v[i]).z < 0;
  }
  return c[0] == c[1] && c[1] == c[2] 
}
​
function draw() {
  
  let mouse = createVector(mouseX, mouseY);
  let itri = -1;
  for (let i=0; i < dt.length; i++) {
    let tri = dt[i];
    if (pointInTriangle(mouse,tri)) itri = i;
  }
  
  stroke('black');
  strokeWeight(2);
  for (let i = 0; i < vp.length; i++) {
    let poly = vp[i];
    if (vdi[i].indexOf(itri) >= 0) fill('lightgray');
    else fill('white')
    beginShape();
    for (let p of poly) vertex(...p);
    endShape(CLOSE)
  }
  
  stroke('red')
  strokeWeight(1);
  for (let i=0; i < dt.length; i++) {
    let tri = dt[i];
    if (i==itri) fill(255,0,0,50);
    else noFill();
    beginShape()
    for (let p of tri) vertex(...p)
    endShape(CLOSE)
  }
}
​
//
// Delaunator utility functions
//
​
function delaunayTriangles() {
  let triangles = [];
  for (let i = 0; i < delaunay.triangles.length; i += 3) {
    let idx = delaunay.triangles.slice(i, i + 3);
    let tri = [];
    for (let j of idx) {
      tri.push(points[j]);
    }
    triangles.push(tri);
  }
  return triangles;
}
​
function voronoiPolygons() {
  let centers = [];
​
  function triangleCenter(t) {
    if (centers[t]) {
      return centers[t];
    } else {
      const vertices = pointsOfTriangle(t).map(p => points[p]);
      const center = circumcenter(vertices[0], vertices[1], vertices[2]);
      centers[t] = center;
      return center;
    }
  }
  
  const faces = [];
  const seen = new Set();
  
  for (let e = 0; e < delaunay.triangles.length; e++) {
    const p = delaunay.triangles[nextHalfedge(e)];
    if (!seen.has(p)) {
      seen.add(p);
      const edges = edgesAroundPoint(e);
      const triangles = edges.map(triangleOfEdge);
      const face = [];
      for (let t of triangles) {
        face.push(triangleCenter(t))
      }
      faces.push(face)
    }
  }
  return faces;
}
​
function voronoiDelaunayIndices() {
  const faceTriangles = [];
  const seen = new Set();
  for (let e = 0; e < delaunay.triangles.length; e++) {
    const p = delaunay.triangles[nextHalfedge(e)];
    if (!seen.has(p)) {
      seen.add(p);
      const edges = edgesAroundPoint(e);
      const triangles = edges.map(triangleOfEdge);
      faceTriangles.push (triangles);
    }
  }
  return faceTriangles;
}
​
​
function circumcenter(a, b, c) {
  const ad = a[0] * a[0] + a[1] * a[1];
  const bd = b[0] * b[0] + b[1] * b[1];
  const cd = c[0] * c[0] + c[1] * c[1];
  const D = 2 * (a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]));
  return [
    1 / D * (ad * (b[1] - c[1]) + bd * (c[1] - a[1]) + cd * (a[1] - b[1])),
    1 / D * (ad * (c[0] - b[0]) + bd * (a[0] - c[0]) + cd * (b[0] - a[0])),
  ];
}
​
function edgesOfTriangle(t) {
  return [3 * t, 3 * t + 1, 3 * t + 2];
}
​
function triangleOfEdge(e) {
  return Math.floor(e / 3);
}
​
function nextHalfedge(e) {
  return (e % 3 === 2) ? e - 2 : e + 1;
}
​
function pointsOfTriangle(t) {
  return edgesOfTriangle(t)
    .map(e => delaunay.triangles[e]);
}
​
function edgesAroundPoint(start) {
  const result = [];
  let incoming = start;
  let count = 20;
  do {
    result.push(incoming);
    const outgoing = nextHalfedge(incoming);
    incoming = delaunay.halfedges[outgoing];
    if (count-- <= 0) throw "Infinite loop";
  } while (incoming !== -1 && incoming !== null && incoming !== start);
  return result;
}