三角形分割
之前画球的时候，因为想把球的模型变成 Wavefront .obj file,所以当时想的是分割办法是这样来分割三角形：
包括之前尝试用Beizer曲线来画Utah teapot也都是采用的这样的办法，根据生成的一层一层的点来分割三角形。
然而其实针对这一类情况，比如有一堆顶点，我们想把它们分割成三角形，是有专门的算法来做这些事的 - Triangulation， 也就是三角形分割。其中最出名的算法是 Delaunay triangulation （德劳内三角化），这个算法可以把平面上的点分割成具有良好性质的三角形。
所谓良好性质是指在 Delaunay triangulation 的时候，它会最大化生成的所有三角形的内角，会尽量避免 sliver triangle。所谓 sliver triangle 就是可能会有一个或者两个很尖锐的角的三角形，这样的三角形在线性插值的时候可能效果不太好。所以一般会想要避免。
Delaunay triangulation
以四个点为例，可以有以下的两种三角化方式：
根据我们希望避免 sliver triangle 的角度来看第一种比第二种好。
Delaunay triangulation 就会生成第一种分割。
平面上的点集 P 的 德劳内三角化 是一种 三角剖分 DT§，使得在 P 中没有点严格处于 DT§ 中任意一个三角形 外接圆 的内部。
D 位于 △ABC 外接圆的外部 √
A 位于 △BCD 外接圆的外部 √
C 位于 △ABD 外接圆的外部 ×
B 位于 △ACD 外接圆的外部 ×
其实很容易看出来，如果点在三角形的外接圆的内部就很容易造成比较尖锐的角。
当然也可能四个点在同一个圆上，这里以及以下我们暂时都不讨论共圆和三点共线这种稍显特殊的情况。
Voronoi diagram
Delaunay triangulation 是 Voronoi Diagram（沃罗诺伊图）的 Dual（对偶图）.
所谓 Dual（对偶图），看以下例子：比如蓝色的是图G，红色的图就是它的对偶图。
蓝色的图有四个面： 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 形成回路
沃罗诺伊图是根据到平面特定子集中点的距离将平面划分为区域的图,该点集（称为种子，站点或生成器）是预先指定的，并且对于每个种子，都有一个对应的区域，该区域由比该种子更近的所有点（比其他种子更近）组成。
如果平面上就两个点，那么 Voronoi 图就是这两个点的中垂线分割：
再增加一个点，中垂线继续出来分割：
比较容易理解 Delaunay triangulation 和 Voronoi diagram 的关系，毕竟外接圆这个就隐含了跟谁距离更近。
Parabolic Lifting Algorithm
找 Delaunay Triangulation 也可以转化为一个找 Convex Hull 的问题，把2d平面上的每个点P升到空中并且给它的z坐标是 [公式] ，然后找到这些点构成的 bottom convex hull，把它们再映射回2d平面。
之所以这样可行觉得因为：
圆的方程式可写成 [公式] (写成圆心式展开可得)
三点确定一个平面： [公式]
这个平面与 [公式] 相交
三点确定的平面与抛物面相交的结果：
[公式]
得到的也就是圆，所以这样可以保证三点确定一个圆，也就是一个三角形有一个外接圆。
Coding Algorithm
然而在代码时候，convex hull不一定是最好的方法，发现了这篇三角剖分算法(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
然后有优化版本：
input: 顶点列表(vertices) //vertices为外部生成的随机或乱序顶点列表
output:已确定的三角形列表(triangles)
初始化顶点列表
创建索引列表(indices = new Array(vertices.length)) //indices数组中的值为0,1,2,3,…,vertices.length-1
基于vertices中的顶点x坐标对indices进行sort //sort后的indices值顺序为顶点坐标x从小到大排序（也可对y坐标，本例中针对x坐标）
确定超级三角形
将超级三角形保存至未确定三角形列表（temp triangles）
将超级三角形push到triangles列表
遍历基于indices顺序的vertices中每一个点 //基于indices后，则顶点则是由x从小到大出现
初始化边缓存数组（edge buffer）
遍历temp triangles中的每一个三角形
计算该三角形的圆心和半径
如果该点在外接圆的右侧
则该三角形为Delaunay三角形，保存到triangles
并在temp里去除掉
跳过
如果该点在外接圆外（即也不是外接圆右侧）
则该三角形为不确定 //后面会在问题中讨论
跳过
如果该点在外接圆内
则该三角形不为Delaunay三角形
将三边保存至edge buffer
在temp中去除掉该三角形
对edge buffer进行去重 // 这里的去重是只要重复出现的edges全都去掉，不仅仅是重复部分，也包括原本的
将edge buffer中的边与当前的点进行组合成若干三角形并保存至temp triangles中
将triangles与temp triangles进行合并
除去与超级三角形有关的三角形
end
跟着算法写了一个Python版本:
把随机生成的点放在空间中看一下：
looks good!
代码
参考：
Delaunay_triangulation
Dual graph
Voronoi diagram
Triangulate Efficient Triangulation Algorithm Suitable for Terrain Modelling
三角剖分算法(delaunay)