用c 实现Delaunay三角剖分.doc

Delaunay三角剖分

voidmain(PointLink*ptUpOutline,PointLink*ptDownOutline)
{
//首先分别对上下轮廓线的点集进行三角化，ptUpOutline,ptDownOutline为对应点集
TrianglizationInPlan(ptUpOutline);
TrianglizationInPlan(ptDownOutline);

//根据两层三角化的结果进行Delaunay剖分，得到四面体链表
GetTetrahedron(UpTriangle,DownTriangle);

//后处理用于删除不正确的四面体
PostProcess();
}

其中：
1．函数TrianglizationInPlan()用于平面三角化
voidTrianglizationInPlan(PointLink*Head)
{
//对不符合Delaunay剖分的边进行细分
boolOver=1;
while(Over)
{
First=Head;
Second=First->next;
while(Second){
if(!NotIncludeOtherPoint(First->Point,Second->Point,Head)){
PointLink*Point=newPointLink;
First->next=Point;
Point->next=Second;
Over=false;
}
First=Second;
Second=Second->next;
}
}
//对平面进行三角化，保存结果到TriangleLink的链表
Trianglization(Head);
}

2．函数GetTetrahedron()进行Delaunay剖分得到四面体链表
voidGetTetrahedron(TriangleLink*First,TriangleLink*Second)
{
Cur=First;
while(Cur){
Temp1=Cur->Triangle;
Center=GetCenter(Temp1);
Cur=ContourUp;
while(Cur){
//初始化min
if(Cur==ContourUp) {
min=Center.distance(Cur->Point);
Value=min;
Result=Cur->Point;
}
//找距离最小的点
else {
Value=Center.distance(Cur->Point);
if(min>Value){
min=Value;
Result=Cur->Point;
}
}
Cur=Cur->next;
}
TetrahedronLink*T1=newTetrahedronLink;
T1->volume.Point[0]=Cur->Triangle.Point[0];
T1->volume.Point[1]=Cur->Triangle.Point[1];
T1->volume.Point[2]=Cur->Triangle.Point[2];
T1->volume.Point[3]=Result;
T1->type=1;
ResultCur->next=T1;
T1->next=0;
ResultCur=T1;
Cur=Cur->next;
}

Cur=Second;
while(Cur){
Temp1=Cur->Triangle;
Center=GetCenter(Temp1);
//逐个比较找到离圆心最近的点
Cur=ContourDown;
while(Cur){
//初始化min
if(Cur==ContourDown){
min=Center.distance(Cur->Point);
Value=min;
Result=Cur->Point;
}
else //找距离最小的点{
Value=Center.distance(Cur->Point);
if(min>Value){
min=Value;
Result=Cur->Point;
}
}
Cur=Cur->next;
}
TetrahedronLink*T2=newTetrahedronLink;
T2->volume.Point