[图形学]Delaunay三⾓剖分算法附C++实现 完整代码已上传：
将离散点构成三⾓⽹，这种三⾓⽹称为Delaunay三⾓⽹ Delaunay剖分具备的优异特性有（来⾃）：
1.最接近：以最近的三点形成三⾓形，且各(三⾓形的边)皆不相交。
2.唯⼀性：不论从区域何处开始构建，最终都将得到⼀致的结果。 3.最优性：任意两个相邻三⾓形形成的的对⾓线如果可以互换的话，那么两个三⾓形六个内⾓中最⼩的⾓度不会变⼤。 4.最规则：如果将中的每个三⾓形的最⼩⾓进⾏升序排列，则Delaunay三⾓⽹的排列得到的数值最⼤。
5.区域性：新增、删除、移动某⼀个顶点时只会影响临近的三⾓形。
6.具有的外壳：三⾓⽹最外层的边界形成⼀个凸多边形的外壳。
⾸先看我的程序结果（）：
下⾯介绍Delaunay三⾓剖分算法：
⼆. 凸包切分
在凸包链表中每次寻⼀个由相邻两条凸包边组成的三⾓形，在该三⾓形的内部和边界上都不包含凸包上的任何其它点。将这个点去掉后得到新的凸包链表。重复这个过程，直到凸包链表中只剩三个离散点为⽌。将凸包链表中的最后三个离散点构成⼀个三⾓形，结束凸包三⾓剖分过程，这⼀过程只对凸包中的点进⾏处理。
List<Triangle> DivideHull(List<Point> pts)
科普展品制作{
List<Point> hpts;
for(int i = 0; i< pts.size() ; i++)
hpts.push_back(pts[i]);
List<Triangle> tins; //保存得到的三⾓形
while(hpts.size() >2) //⼀直到最后剩下离散的三个点
{
int tag = 0;
float minangle = 180; //每次构成相邻的边，优先⾓度最⼩的三⾓形
for(int i = index; i< hpts.size() ; i++)
{
float tri_angle = 180.0;
if(i == 0){
tri_angle = Gemetry::angle3D(hpts.last(),hpts[i],hpts[i+1]);
}
else if(i == hpts.size()-1){
tri_angle = Gemetry::angle3D(hpts[i-1],hpts[i],hpts[0]);
}
else{
tri_angle = Gemetry::angle3D(hpts[i-1],hpts[i],hpts[i+1]);
}
if(tri_angle < minangle)
{
tag = i;
minangle = tri_angle;
}
}
int tagb = tag-1;
int tage = tag+1;
if(tag == 0)
tagb =hpts.size()-1;
if(tag == hpts.size()-1)
tage = 0;
tins.push_back(Triangle(hpts[tagb],hpts[tag],hpts[tage]));
}
return tins;
}
过滤器球阀三. 离散点内插
算法流程：
1、选择⼀个尚未构成三⾓形的离散点
2、在已经⽣成的三⾓形中，出该离散点的三⾓形，有两种情况：在三⾓形内部和在三⾓形边上。
3、如果离散点在三⾓形的内部，则将该三⾓形以及三⾓形的边删除，然后将三个顶点以及离散点分别连接，形成三个新的三⾓形。如果离散点在三⾓形的边上，记录点所在的边E，根据拓扑关系，出该边的左右相邻三⾓形T1，T2，添加四条新边和四个新三⾓形NT，删除T1，T2以及边E，基本上操作是相同的。
对于新⽣成的三⾓形，不能直接加⼊到三⾓形数组⾥，需要挨个对其边进⾏空外接圆检测。具体做法为：对于新⽣成的三⾓形的边E，出该边相邻的两个三⾓形，判断该边⼀侧的对⾓的顶点是否位于另外⼀个三⾓形的外接圆的⾥⾯。如果是，则将边E删除，再将两个对⾓连接起来，形成两个新的三⾓形T3，T4。
对于新⽣成三⾓形T3，T4，同样需要进⾏空外接圆检测，⼀直迭代下去，直到所有新⽣成的三⾓形都通过空外接圆检测为⽌。
4、重复1、2、3，直到所有⾮凸壳离散点都插⼊完为⽌。
List<Triangle> getDelaunay(List<Triangle> hulltins, List<Point> pts)
{
for(int i = 0; i<pts.size(); i++)
{
List<Triangle> delTin; //保存要删除的三⾓形
for(int j =0; j< hulltins.size(); j++)
单点系泊系统
{
if(hulltins[j].isInTriangle(pts[i]) == true) //该点在三⾓形内部
{
delTin.push_back(hulltins[j]);
}
if(hulltins[j].isOnTriangle(pts[i]) == true){ //点在三⾓形边上
delTin.push_back(hulltins[j]);
}
List<Line> borderLines;//保存离散点的相邻边mvkkk
List<Triangle> newTri;//保存新得到的三⾓形，之后⽤于检测空圆
if(delTin.size() == 1) //在三⾓形内部
{
Line l1 = delTin[0].l1;
环氧环己烷
Line l2 = delTin[0].l2;
Line l3 = delTin[0].l3;
borderLines.push_back(l1);
borderLines.push_back(l2);
borderLines.push_back(l3);
for(int j = 0; j< borderLines.size();j++)
{
newTri.push_back(Triangle(borderLines[j].p1,borderLines[j].p2,pts[i]));
}
}else if(delTin.size() == 2)//在三⾓形边上，则要到四条相临边，去掉重复的边
{
Line l[3];
l[0] = delTin[0].l1;
l[1] = delTin[0].l2;
l[2] = delTin[0].l3;
int index = 0;//保存重复边的下标
//四条相临边，去掉重复的边
for( int m =0;m< 3; m++)
if(delTin[1].containsLine(l[m]) ==0)
{
borderLines.push_back(l[m]);
}else
{
index = delTin[1].containsLine(l[m])-1;
}
for( int m =0;m< 3; m++)
{
if(m!=index)
borderLines.push_back(delTin[1].l[m]);
}
for(int j = 0; j< borderLines.size();j++)
{
{
newTri.push_back(Triangle(borderLines[j].p1,borderLines[j].p2,pts[i]));
}
}
// 对新得到的三⾓形进⾏检测空圆
delTin.clear();//之后保存需要删除的新⽣成的三⾓形
for( int s = 0; s< newTri.size(); s++){ //每⼀个三⾓形
for(int j = 0; j< 3 ; j++){ //每⼀条边
Line line = newTri[s].l[j];
for( int m = 0; m< hulltins.size() ; m++)//在三⾓形数组⾥搜索包含该边的三⾓形
{
{
if(hulltins[m].containsLine(line) )//如果三⾓形包含该边
{
Circle tinCircle = Circle::genTriCircle(hulltins[m]);
if(tinCircle.isInCircle(vec3(pts[i]))) //如果当前离散点在三⾓形的外接圆上
{
delTin.push_back(newTri[s]); //后⾯要删除该三⾓形
int x = hulltins[m].containsLine(line)-1;
//对于这个三⾓形的三个边，去掉重复边还有两个边，分别于当前离散点构成⼀个新的三⾓形 for( int k = 0; k<3;k ++)
{
if(x!=k){
newTri.push_back(Triangle(hulltins[m].l[k].p1,hulltins[m].l[k].p2,pts[i])); //对于
}
}
}
}
}
}
}
}
//最终把新的三⾓形加⼊到三⾓形数组⾥
for( int m =0; m< newTri.size() ; m++)
{
hulltins.push_back(newTri[m]);
}
for( int m = 0; m< delTin.size() ; m++)
{
}地热供暖设备
}
return hulltins;
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议