在〈Delaunay 三角分割（一）〉談過，如果有一堆隨機散佈的點，建立了 Delaunay 三角分割，找出相鄰三角形的外接圓，將圓心連接起來，就可以構成 Voronoi 圖形。
既然是相鄰三角形，就表示有共用頂點，實際上一個 Voronoi 細胞的細胞核，就是一組相鄰三角形的共用頂點，例如下圖中，紅色細胞核是六個三角形的共用頂點：
因此要找出一個 Voronoi 細胞，是由哪些相鄰三角形的外接圓心連接而成，就是找出哪些三角形包含該細胞核作為頂點之一，然後求得其外接圓心，以逆時針（或順時針）排序就可以定義出一個 Voronoi 細胞的多邊形了。
因為在〈Delaunay 三角分割（三）〉中，已經實作出 Delaunay 三角分割了，Delaunay 的實例本身，帶有 triangles 特性，可以從中找出某個點作為頂點的三角形，也因為有 Delaunay 實例也有 circles 特性，可用來取得外接圓心，想實作出 Voronoi 並不是難事，只是尋找過程有沒有效率罷了。
若要有效率地尋找以細胞核作為頂點的三角形並排序，可以在找到三角形時，在頂點上做點調整，例如某個細胞核的三角形們若頂點編號如下：
對於這些三角形，給予新的頂點順序，例如，(b, c, a)、(c, d, a)、(d, e, a)、(e, f, a)、(f, g, a)、(g, b, a)：
每個三角形的新頂點順序，最後一個頂點都是做為細胞核的頂點 a，這樣的好處是，若找到某個以 a 頂點的三角形，該三角形第 2 個頂點，若為某三角形的第 1 個點，那它就是下個以 a 頂點的三角形。
例如，找到 (d, e, a) 以細胞核 a 為頂點，這個三角形的第 2 個頂點是 e，而以 e 為第 1 個頂點的三角形為 (e, f, a)，正好是下個以細胞核 a 為頂點的三角形，依此類推下去，就可以依序找出圍繞 a 的三角形了。
現在，可以來將任務分解為：
- 圍繞某點的三角形頂點關係
- 建立細胞頂點關係
首先在 Delaunay 中定義 voronoi 方法，實作第一個任務，說明就直接寫在註解中了：
class Delaunay {
...
voronoi() {
const tris = Array.from(this.triangles.keys());
// 收集外接圓心（Voronoi 細胞頂點）
const vertices = tris.map(t => this.circles.get(t).center);
// 計算圍繞某點的三角形關係
// connectedTris: 收集最後頂點連著 i 的三角形
// triIndices: 三角形與第 i 個外接圓的對應
const {connectedTris, triIndices} = connectedTrisIndices(this, tris);
...
}
}
function connectedTrisIndices(d, tris) {
// 收集最後頂點連著 i 的三角形
const connectedTris = [];
for(let i = 0; i < d.coords.length; i++) {
connectedTris.push([]);
}
// 三角形與第 i 個外接圓心的對應
const triIndices = new Map();
for(let i = 0; i < tris.length; i++) {
const [a, b, c] = tris[i];
// rt1、rt2、rt3 都代表 tris[i]，只是頂點順序不同
const rt1 = [b, c, a];
const rt2 = [c, a, b];
const rt3 = [a, b, c];
// connectedTris 的索引就是三角形最後一個頂點索引
// 這可用於後續依序走訪連接至某點的三角形
connectedTris[a].push(rt1);
connectedTris[b].push(rt2);
connectedTris[c].push(rt3);
// rt1、rt2、rt3 都代表 tris[i]，外接圓心都是 vertices 的第 i 個
triIndices.set(rt1, i);
triIndices.set(rt2, i);
triIndices.set(rt3, i);
}
return {connectedTris, triIndices};
}
接著就是收集細胞頂點：
class Delaunay {
...
voronoi() {
...
const {connectedTris, triIndices} = connectedTrisIndices(this, tris);
// 收集各細胞的頂點索引
const cells = [];
// 從 4 開始是因為不包含自設的矩形頂點
for(let i = 4; i < this.coords.length; i++) {
// 連接 i 點的三角形們構成的細胞
cells.push(indicesOfCell(connectedTris[i], triIndices));
}
return {vertices, cells};
}
}
function indicesOfCell(iTris, triIndices) {
// 取得其中一個三角形的首個頂點，這邊取第 0 個三角形的首個頂點
let vi = iTris[0][0];
const indices = [];
for(let _ = 0; _ < iTris.length; _++) {
// 找到一個以 vi 為起點的三角形，這邊取第 0 個
const t = iTris.filter(t => t[0] === vi)[0];
// 收集細胞頂點索引
indices.push(triIndices.get(t));
// 目前三角形的下個頂點，就是下個三角形的起點
vi = t[1];
}
return indices;
}
如果只是想繪製細胞，那麼有個傳回細胞頂點座標的方法會比較方便：
class Delaunay {
...
pointsOfVoronoiCells() {
const {vertices, cells} = this.voronoi();
return cells.map(cell => cell.map(i => vertices[i]));
}
}
這麼一來，就可以用傳回的細胞頂點座標來繪圖了，底下的範例可以使用滑鼠來決定每個點，同繪製 Delaunay 三角分割與 Voronoi 圖形：