透過 Worley 雜訊可以畫出 Voronoi 圖形，只不過代價是昂貴的運算，因為使用了全部的像素來運算，透過 CPU 來做這類運算相當吃力，因而 Worley 雜訊通常是應用 GPU 著色器的撰寫上。
可以透過幾何運算來求得 Voronoi 圖形，最易於理解的是半平面交集（Half-plane intersection），因為就是從勢力範圍的觀點來求 Voronoi 圖形。
例如，若一開始有兩個點，兩個點的中垂線畫出了兩者的勢力範圍：
現在將藍色點與另一個空間中的點也畫出勢力範圍，那麼藍色點可以擁有的勢力範圍，就是前一個勢力範圍與目前勢力範圍的交集：
重複相同步驟，藍色點與更多的點求得勢力範圍，並取得勢力範圍交集，直到全部的點都處理過為止。例如，有五個點的話，最後藍色點求得的勢力範圍就是下圖的紅色區域：
對於另外四個點，也可以重複以上的步驟，在每個點的勢力範圍交集都求得後，就會得到 Voronoi 圖形：
若要透過程式來實現半平面交集，只要有個夠大的正方形就可以了，為了方便，可以定義一個 polygonSquare 函式，可以指定正方形邊長大小，傳回正方形逆時針頂點的清單，頂點都使用 p5.Vector 來表示，這是因為透過向量，後續計算上會很方便：
function polygonSquare(size) {
const halfS = size / 2;
return [
createVector(halfS, -halfS),
createVector(halfS, halfS),
createVector(-halfS, halfS),
createVector(-halfS, -halfS)
];
}
那麼有兩個正方形的話，如何求得其交集呢？多邊形交集其實是個複雜的議題，幸好的是，正方形是凸多邊形，凸多邊形的交集在計算上簡單多了，先看看下圖：
求得另一方在自身範圍內的頂點，以及邊的交點，將這些點收集起來逆時針排序就可以了，因此有三個子任務必須完成：
- 自身範圍內的頂點
- 邊的交點
- 點的逆時針排序
自身範圍內的頂點，雖然可以使用〈像素多邊形〉中 inShape 的實現原理，不過凸多邊形要做這種判斷，有更簡單的方式，如果點在凸多邊形內，那麼該點與凸多邊形的每個頂點相連而成的向量，若逆時針每兩個向量進行叉積（cross），那麼叉積後的向量方向都會相同，因此可以實作出：
function inConvex(convexPoints, p) {
const preCp = p5.Vector.cross(
p5.Vector.sub(convexPoints[convexPoints.length - 1], p),
p5.Vector.sub(convexPoints[0], p)
).z;
for(let i = 0; i < convexPoints.length - 1; i++) {
const cp = p5.Vector.cross(
p5.Vector.sub(convexPoints[i], p),
p5.Vector.sub(convexPoints[i + 1], p)
).z;
if(preCp * cp <= 0) {
return false;
}
}
return true;
}
邊的交點就是兩線的交集，若線的資料結構定義為 {p1: v1, p2: v2}，其中 v1、v2 是座標，然而以向量表示，有了線的點資料，就可以求斜率，然後取得線的方程式表示，兩條方程式求聯立方程式，就可以求交點：
function onLine(line, p, epsilon = 1e-5) {
const v1 = p5.Vector.sub(line.p1, p);
const v2 = p5.Vector.sub(line.p2, p);
return p5.Vector.cross(v1, v2).mag() <= epsilon && p5.Vector.dot(v1, v2) <= epsilon;
}
function intersectionLines(line1, line2, epsilon = 1e-5) {
const a = p5.Vector.sub(line1.p2, line1.p1);
const b = p5.Vector.sub(line2.p2, line2.p1);
const cp = p5.Vector.cross(a, b).z;
if(abs(cp) >= epsilon) { // 不共線、不平行
const s = p5.Vector.sub(line2.p1, line1.p1);
const p = p5.Vector.add(line1.p1, p5.Vector.mult(a, p5.Vector.cross(s, b).z / cp));
// 交點是否在邊上
if(onLine(line1, p, epsilon) && onLine(line2, p, epsilon)) {
return p;
}
}
return null;
}
若兩線共線或平行，兩線的向量叉積大小會是 0，因為浮點數會有計算上的誤差，這邊使用了 epsilon 來設定大於該值，就不視為共線或平行了。
解聯立方程式得到的交點，可能是在邊的延伸上，然而我們要的是邊與邊的交點，因此必須進一步判斷交點是否在邊上，同樣地，如果點在邊上，那麼該點與邊的兩個頂點構成的向量，叉積會是 0，因為浮點數會有計算上的誤差，這邊使用了 epsilon，接著進一步判斷了點積（dot）的結果（也就是投影量）小於 epsilon，來判斷點是否在邊上。
接著就是針對收集到的頂點進行排序，這很簡單，可先找出多邊形的中點，這是因為中點的求得與頂點的順序沒有關係：
function convexCenterPoint(convexPoints) {
let x = 0;
let y = 0;
for(let i = 0; i < convexPoints.length; i++) {
x += convexPoints[i].x;
y += convexPoints[i].y;
}
return createVector(x / convexPoints.length, y / convexPoints.length);
}
然後用中點來求得它與每個每個頂點的夾角，根據夾角進行排序：
function convexCtClk(convexPoints) {
const centerP = convexCenterPoint(convexPoints);
return convexPoints.sort((p1, p2) => {
return atan2(p1.y - centerP.y, p1.x - centerP.x) -
atan2(p2.y - centerP.y, p2.x - centerP.x);
});
}
完成這三個子任務後，就可以來求凸多邊形交集了：
// 找出凸多邊形的邊與線的交點
function intersectionConvexLine(convexPoints, line, epsilon = 1e-10) {
const pts = [];
for(let i = convexPoints.length - 1, j = 0; j < convexPoints.length; i = j++) {
const p = intersectionLines(line, {p1: convexPoints[i], p2: convexPoints[j]}, epsilon);
if(p !== null && pts.every(pt => !pt.equals(p))) {
pts.push(p);
}
}
return pts;
}
// 凸多邊形交集
function convexIntersection(convexPoints1, convexPoints2, epsilon = 1e-10) {
// 邊的交點
const points = [];
for(let i = convexPoints1.length - 1, j = 0; j < convexPoints1.length; i = j++) {
const pts = intersectionConvexLine(convexPoints2, {p1: convexPoints1[i], p2: convexPoints1[j]}, epsilon);
for(let k = 0; k < pts.length; k++) {
points.push(pts[k]);
}
}
return convexCtClk( // 逆時針排列
// 接上凸多邊形內的頂點
points.concat(convexPoints1.filter(p => inConvex(convexPoints2, p)))
.concat(convexPoints2.filter(p => inConvex(convexPoints1, p)))
);
}
這篇文件就先完成到凸多邊形交集，為了做個展示，來個可平移、轉動各頂點的函式：
function polygonTranslate(polygonPoints, x, y) {
return polygonPoints.map(p => createVector(p.x + x, p.y + y));
}
function polygonRotate(polygonPoints, angle) {
return polygonPoints.map(p => p.copy().rotate(angle));
}
底下的範例可利用方才的函式，畫出兩個正方形的交集，其中一個正方形可以用滑鼠控制位置，按左、右鍵轉動：