如何使用JavaScript计算Voronoi图的区域边界坐标

我正在使用 p5.js 构建Voronoi图，目前参考公开教程中的算法，通过给同一归属区域的像素统一着色的方式，已经实现了Voronoi图的基础可视化展示，效果如下：

当前版本的实现代码如下（逻辑稍显杂乱、运行效率较低）：

const h = 512
const w = 512

const scl = 512;
const rez = h / scl;

const tiles = []
let points = []

function randomIntFromInterval(min, max) { // 区间随机整数，包含上下限
  return Math.floor(Math.random() * (max - min + 1) + min)
}

function setup() {
  createCanvas(w, h);
  background(220);
  
  for (let i = 0; i < 12; i++) {
    const p = randomIntFromInterval(0, h * h)
    points.push(p)
  }

  for (let y = 0; y < scl; y++) {
    for (let x = 0; x < scl; x++) {
      tiles.push(0);
      const xx = x * rez;
      const yy = y * rez;
      noFill();
      stroke(0);
      rect(xx, yy, rez, rez);
      const indx = `${x + y * scl}`
      if (+indx === points[0] || +indx === points[1] || +indx === points[2]) {
        stroke(225, 0, 0)
        fill(255, 0, 0)
      }
      text(indx, xx + rez / 2 - 5, yy + rez / 2 + 5)
    }
  }

  compute(0, scl, scl)
  
  for (const p of points) {
    const x = p % scl;
    const y = (p - x) / scl;
    fill(0)
    circle(x * rez, y * rez, 5)
  }
}

function compute(x, len, grandLen) {
  const corners = getCorners(x, len, grandLen)
  const lookup = []
  for (const corner of corners) {
    const ds = []
    for (const point of points) {
      ds.push(distance(corner, point, scl));
    }
    lookup.push(ds)
  }
  const is = []
  for (let i = 0; i < lookup.length; i++) {
      const min = Math.min(...lookup[i])
      const iMin = lookup[i].indexOf(min);
      is.push(iMin);
  }
  if (is.every((val, i, arr) => val === arr[0])) {
    const colorR = map(points[is[0]], 0, h*h, 0, 255)
    const colorG = 255 - map(points[is[0]], 0, h*h, 0, 255)
    paintRegion(corners[0], len, rez, color(colorR, colorG, 200))
  } else {
    const rects = divide(corners[0], len)
    rects.forEach(r => {
    compute(r, len / 2, grandLen)
    })                    
  } 
}

function paintRegion(a, len, size, color) {
  let ax, ay;
  [ax, ay] = toCoords(a);
  fill(color)
  noStroke(0);
  rect(ax * size, ay * size, size * len, size * len)
}

function toCoords(index) {
  const x = index % scl;
  const y = Math.floor((index - x) / scl);
  return [x, y]
}

function distance(a, b, len) {
  let ax, ay, bx, by;
  [ax, ay] = toCoords(a);
  [bx, by] = toCoords(b);
  const p1 = Math.pow(bx - ax, 2);
  const p2 = Math.pow(by - ay, 2);
  return sqrt(p1 + p2);
}

// l1为当前方块边长，l2为画布边长
function getCorners(a, l1, l2) {
  const corners = []
  corners.push(a);
  corners.push(a + l1 - 1);
  corners.push(a + (l1 - 1) * l2)
  corners.push(a + (l1 - 1) * l2 + (l1 - 1));
  return corners
}

function divide(a, len) {
  let ax, ay;
  [ax, ay] = toCoords(a);
  const d = len / 2;
  const p1 = ax + ay * scl;
  const p2 = ax + d + ay * scl;
  const p3 = ax + (ay + d) * scl;
  const p4 = ax + d + (ay + d)  * scl;
  return [p1, p2, p3, p4];
}

function draw() {}

页面对应的依赖引入代码：

<script src="https://cdn.jsdelivr.net/npm/p5@1.5.0/lib/p5.js"></script>

需求说明 #

目前这种像素着色的展示形式实用性不足，需要获取所有Voronoi区域的边界坐标（包含画布自身的边界）。之前检索过二维平面的形状边缘提取方案，但认为基于渲染后图像做后处理提取边界的方式本末倒置，因此想确认两个问题：

• 是否存在直接计算Voronoi图边界的方案？
• 如果没有直接计算方案，遍历像素数组提取边界的最简实现方式是什么？

已知numpy、Matlab平台有大量相关实现资源，但本次需要适配JavaScript运行环境的解决方案。

最终方案结论 #

经过进一步调研，参考德劳内三角网推导Voronoi图的相关技术资料后，可以确认：Fortune算法是直接获取Voronoi区域边界的最优方案。
算法相关公开资料收录了多语言实现链接，实际测试Raymond Hill开发的Javascript-Voronoi开源实现，运行效果稳定良好，可直接在JavaScript环境中使用，无需从零实现算法，也不需要走渲染后提取像素边界的冗余路径。

内容的提问来源于stack exchange，提问作者Jsutotherel