开篇
在做⼀个Low Poly的课题，⽽这种低多边形的成像效果在现在设计中越来越被喜欢，其中的低多边形都是由三⾓形组成的。
管式反应器
⽽如何⾃动⽣成这些看起来很特殊的三⾓形，就是本章要讨论的内容。
选择
其是最先是由很多离散的点组成，基于这个确定的点集，将点集连接成⼀定⼤⼩的三⾓形，且分配要相对合理，才能呈现出漂亮的三⾓化。这时则要求使⽤三⾓剖分算法（Delaunay），引于对Delaunay三⾓形的定义为： 【定义】三⾓剖分：假设V是⼆维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的⼀个三⾓剖分T=(V,E)是⼀个平⾯图G，该平⾯图满⾜条件：
1.除了端点，平⾯图中的边不包含点集中的任何点。
2.没有相交边。
3.平⾯图中所有的⾯都是三⾓⾯，且所有三⾓⾯的合集是散点集V的凸包。
在实际中运⽤的最多的三⾓剖分是Delaunay三⾓剖分，它是⼀种特殊的三⾓剖分。先从Delaunay边说起：
【定义】Delaunay边：假设E中的⼀条边e（两个端点为a,b），e若满⾜下列条件，则称之为Delaunay边：存在⼀个圆经过a,b两点，圆内(注意是圆内，圆
上最多三点共圆)不含点集V中任何其他的点，这⼀特性⼜称空圆特性。
【定义】Delaunay三⾓剖分：如果点集V的⼀个三⾓剖分T只包含Delaunay边，那么该三⾓剖分称为Delaunay三⾓剖分。
【定义】假设T为V的任⼀三⾓剖分，则T是V的⼀个Delaunay三⾓剖分，当前仅当T中的每个三⾓形的外接圆的内部不包含V中任何的点。
如图，将离散点联结成Delaunay三⾓形
算法
关于Delaunay三⾓形的算法，有翻边算法、逐点插⼊算法、分割合并算法、Bowyer-Watson算法等。
⽽在这⼏种算法中，逐点插⼊算法⽐较简单、易懂，在本⽂中只针对该算法进⾏讨论，该算法也是⽬前使⽤最为⼴泛的Delaunay算法。
在该算法中，主要应⽤Delaunay三⾓形【定义4】，理解下来就是每⼀个三⾓形的外接圆圆内不能存在点集内的其它任何⼀点，⽽有时候会出现点在外接圆上的情况，这种情况被称为“退化”。
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
其⽅法虽然可实现三⾓化，但是效率还是不太⾼
在看过该js也是基于该伪代码进⾏编写的，但是作者在其中进⾏了⼀次排序优化，使得代码运⾏效率得到了提⾼ 珍珠岩助滤剂优化后的伪代码为：
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进⾏去重
将edge buffer中的边与当前的点进⾏组合成若⼲三⾓形并保存⾄temp triangles中
将triangles与temp triangles进⾏合并
除去与超级三⾓形有关的三⾓形
end
⼤多数同学看过伪代码后还是⼀头雾⽔，所以⽤图来解释这个过程，我们先⽤三点来做实例：
如图，随机的三个点
根据离散点的最⼤分布来求得随机⼀个超级三⾓形（超级三⾓形意味着该三⾓形包含了点集中所有的点）
我的⽅法是根据相似三⾓形定理求得与矩形⼀半的⼩矩形的对⾓三⾓形，扩⼤⼀倍后则扩⼤后的直⾓三⾓形斜边经过点(Xmax,Ymin)
但是为了将所有的点包含在超级三⾓形内，在右下⾓对该三⾓形的顶点进⾏了横和⾼的扩展，并要保证这个扩展三⾓形底⼤于⾼，才能实现包含
数据的波动
这样求得的超级三⾓形不会特别⼤使得计算复杂，⽽且过程也简单，并将超级三⾓形放⼊temp triangles中
所以该三⾓形不为Delaunay三⾓形，将其三边保存⾄edge buffer中，temp triangle中删除该三⾓形
保安单元
将该点与edge buffer中的每⼀个边相连，组成三个三⾓形，加⼊到temp triangles中
再将重复对temp triangles的遍历并画外接圆，这时使⽤的是第⼆个点来进⾏判断
1. 该点在三⾓形1外接圆右侧，则表⽰左侧三⾓形为Delaunay三⾓形，将该三⾓形保存⾄triangles中
2. 该点在三⾓形2外接圆外侧，为不确定三⾓形，所以跳过（后⾯会讲到为什么要跳过该三⾓形），但并不在temp triangles中删除
3. 该点在三⾓形3外接圆内侧，则这时向清空后的edge buffer加⼊该三⾓形的三条边，并⽤该点写edge buffer中的三⾓边进⾏组合，组合
成了三个三⾓形并加⼊到temp triangles中
再次对temp triangles进⾏遍历，这⾥该数组⾥则含有四个三⾓形，⼀个是上次检查跳过的含有第⼀个点的三⾓形和新根据第⼆个点⽣成的三个三⾓形
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议