三角形分割
之前畫球的時候，因為想把球的模型變成 Wavefront .obj file,所以當(dāng)時想的是分割辦法是這樣來分割三角形：

包括之前嘗試用Beizer曲線來畫Utah teapot也都是采用的這樣的辦法，根據(jù)生成的一層一層的點來分割三角形。

然而其實針對這一類情況，比如有一堆頂點，我們想把它們分割成三角形，是有專門的算法來做這些事的 - Triangulation， 也就是三角形分割。其中最出名的算法是 Delaunay triangulation （德勞內(nèi)三角化），這個算法可以把平面上的點分割成具有良好性質(zhì)的三角形。

所謂良好性質(zhì)是指在 Delaunay triangulation 的時候，它會最大化生成的所有三角形的內(nèi)角，會盡量避免 sliver triangle。所謂 sliver triangle 就是可能會有一個或者兩個很尖銳的角的三角形，這樣的三角形在線性插值的時候可能效果不太好。所以一般會想要避免。

Delaunay triangulation
以四個點為例，可以有以下的兩種三角化方式：

根據(jù)我們希望避免 sliver triangle 的角度來看第一種比第二種好。

Delaunay triangulation 就會生成第一種分割。

平面上的點集 P 的 德勞內(nèi)三角化 是一種 三角剖分 DT§，使得在 P 中沒有點嚴(yán)格處于 DT§ 中任意一個三角形 外接圓 的內(nèi)部。

D 位于 △ABC 外接圓的外部 √
A 位于 △BCD 外接圓的外部 √

C 位于 △ABD 外接圓的外部 ×
B 位于 △ACD 外接圓的外部 ×
其實很容易看出來，如果點在三角形的外接圓的內(nèi)部就很容易造成比較尖銳的角。

當(dāng)然也可能四個點在同一個圓上，這里以及以下我們暫時都不討論共圓和三點共線這種稍顯特殊的情況。

Voronoi diagram
Delaunay triangulation 是 Voronoi Diagram（沃羅諾伊圖）的 Dual（對偶圖）.

所謂 Dual（對偶圖），看以下例子：比如藍(lán)色的是圖G，紅色的圖就是它的對偶圖。

藍(lán)色的圖有四個面： f1, f2, f3, f4
四個面中取四個頂點 v1, v2, v3, v4
對于那些由一條edge分割的面，比如 f1-f2, f2-f3，f2-f4,直接連起來 v1-v2, v2-v3,v2-v4 形成edge
對于f3-f4,f1-f4這種不是由一條edge分割的面，需要連接v3-v4,v1-v4 形成回路

沃羅諾伊圖是根據(jù)到平面特定子集中點的距離將平面劃分為區(qū)域的圖,該點集（稱為種子，站點或生成器）是預(yù)先指定的，并且對于每個種子，都有一個對應(yīng)的區(qū)域，該區(qū)域由比該種子更近的所有點（比其他種子更近）組成。
如果平面上就兩個點，那么 Voronoi 圖就是這兩個點的中垂線分割：

再增加一個點，中垂線繼續(xù)出來分割：

比較容易理解 Delaunay triangulation 和 Voronoi diagram 的關(guān)系，畢竟外接圓這個就隱含了跟誰距離更近。

Parabolic Lifting Algorithm
找 Delaunay Triangulation 也可以轉(zhuǎn)化為一個找 Convex Hull 的問題，把2d平面上的每個點P升到空中并且給它的z坐標(biāo)是 [公式] ，然后找到這些點構(gòu)成的 bottom convex hull，把它們再映射回2d平面。

之所以這樣可行覺得因為：

圓的方程式可寫成 [公式] (寫成圓心式展開可得)
三點確定一個平面： [公式]
這個平面與 [公式] 相交
三點確定的平面與拋物面相交的結(jié)果：

[公式]

得到的也就是圓，所以這樣可以保證三點確定一個圓，也就是一個三角形有一個外接圓。

Coding Algorithm
然而在代碼時候，convex hull不一定是最好的方法，發(fā)現(xiàn)了這篇三角剖分算法(delaunay)，里面提到了這個算法：

subroutine triangulate
input : vertex list
output : triangle list
initialize the triangle list
determine the supertriangle
add supertriangle vertices to the end of the vertex list
add the supertriangle to the triangle list
for each sample point in the vertex list
initialize the edge buffer
for each triangle currently in the triangle list
calculate the triangle circumcircle center and radius
if the point lies in the triangle circumcircle then
add the three triangle edges to the edge buffer
remove the triangle from the triangle list
endif
endfor
delete all doubly specified edges from the edge buffer
this leaves the edges of the enclosing polygon only
add to the triangle list all triangles formed between the point
and the edges of the enclosing polygon
endfor
remove any triangles from the triangle list that use the supertriangle vertices
remove the supertriangle vertices from the vertex list
end
然后有優(yōu)化版本：

input: 頂點列表(vertices)　//vertices為外部生成的隨機或亂序頂點列表
output:已確定的三角形列表(triangles)
　　　　初始化頂點列表
　　　　創(chuàng)建索引列表(indices = new Array(vertices.length))　//indices數(shù)組中的值為0,1,2,3,…,vertices.length-1
　　　　基于vertices中的頂點x坐標(biāo)對indices進(jìn)行sort　 //sort后的indices值順序為頂點坐標(biāo)x從小到大排序（也可對y坐標(biāo)，本例中針對x坐標(biāo)）
　　　　確定超級三角形
　　　　將超級三角形保存至未確定三角形列表（temp triangles）
　　　　將超級三角形push到triangles列表
　　　　遍歷基于indices順序的vertices中每一個點　　　//基于indices后，則頂點則是由x從小到大出現(xiàn)
　　　　　　初始化邊緩存數(shù)組（edge buffer）
　　　　　　遍歷temp triangles中的每一個三角形
　　　　　　　　計算該三角形的圓心和半徑
　　　　　　　　如果該點在外接圓的右側(cè)
　　　　　　　　　　則該三角形為Delaunay三角形，保存到triangles
　　　　　　　　　　并在temp里去除掉
　　　　　　　　　　跳過
　　　　　　　　如果該點在外接圓外（即也不是外接圓右側(cè)）
　　　　　　　　　　則該三角形為不確定 //后面會在問題中討論
　　　　　　　　　　跳過
　　　　　　　　如果該點在外接圓內(nèi)
　　　　　　　　　　則該三角形不為Delaunay三角形
　　　　　　　　　　將三邊保存至edge buffer
　　　　　　　　　　在temp中去除掉該三角形
　　　　　　對edge buffer進(jìn)行去重 // 這里的去重是只要重復(fù)出現(xiàn)的edges全都去掉，不僅僅是重復(fù)部分，也包括原本的
　　　　　　將edge buffer中的邊與當(dāng)前的點進(jìn)行組合成若干三角形并保存至temp triangles中
　　　　將triangles與temp triangles進(jìn)行合并
　　　　除去與超級三角形有關(guān)的三角形
end
跟著算法寫了一個Python版本:

把隨機生成的點放在空間中看一下：

looks good!

代碼

參考：

Delaunay_triangulation
Dual graph
Voronoi diagram
Triangulate Efficient Triangulation Algorithm Suitable for Terrain Modelling
三角剖分算法(delaunay)

總結(jié)

以上是生活随笔為你收集整理的Delaunay triangulation network怎么理解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。