Delaunay三角剖分建模方法.doc

Delauney三角网剖分

算法原理：分为三步：

一、凸包生成：1）求出如下四点：min(x-y)、min(x+y)、max(x-y)、max(x+y)并顺次放入一个数组，组成初始凸包；2）对于凸包上的点I，设它的后续点为J，计算矢量线段IJ右侧的所有点到IJ的距离，求出距离最大的点K；3）将K插入I,J之间，并将K赋给J；4）重复2，3步，直到点集中没有在IJ右侧的点为止；5）将J赋给I，J取其后续点，重复2，3，4步，当遍历了一次凸包后，凸包生成完成。

二、环切边界法凸包三角剖分：在凸包数组中，每次寻找一个由相邻两条凸包边组成的三角形，在该三角形的内部和边界上都不包含凸包上的任何其他点，然后去掉该点得到新的凸包链表，重复这个过程，最终对凸包数组中的点进行三角剖分成功。

三、离散的内插：1）建立三角形的外接圆，找出外接圆包含待插入点的所有三角形，构成插入区域；2）删除插入区域内的三角形公共边，形成由影响三角形顶点构成的多边形；3）将插入点与多边形所有顶点相连，构成新的Delaunay三角形；4）重复1，2，3，直到所有非凸包上的离散点都插入完为止。

功能实现流程：

1.在绘图菜单栏下添加一个子菜单项为Delauney，并且在工具栏上添加一个工具项。设置text为Delaunay三角剖分，name为delaunay等属性，添加单击事件，并为单击事件代码

2.为事件函数添加如下代码

Graphicsgra=panel1.CreateGraphics();

ListPoint_Tpts=newListPoint_T();

foreach(Geometry_Tgeoinchoosegeos.Geofeatures)

{

if(geo.GetType()==typeof(Point_T))

{

Point_Tpt=(Point_T)geo;

pts.Add(pt);

}

}

ListTindeltins=DelauneyTin(pts);//根据多点构建delauney三角网

foreach(Tintinindeltins)

{

Point[]ctin=newPoint[3];

for(inti=0;i3;i++)

{

cp=newPoint((int)tin.Pthree[i].X,(int)tin.Pthree[i].Y);

ctin[i]=cp;

}

gra.DrawPolygon(Pens.Red,ctin);

}

3．三角形TIN的数据结构

publicclassTin

{

Point_T[]pthree=newPoint_T[3];

Line_T[]lthree=newLine_T[3];

publicLine_T[]Lthree

{

get{returnlthree;}

set{lthree=value;}

}

publicPoint_T[]Pthree

{

get{returnpthree;}

set{pthree=value;}

}

publicTin()

{}

publicTin(Point_Tp1,Point_Tp2,Point_Tp3)

{

pthree[0]=p1;

pthree[1]=p2;

pthree[2]=p3;

lthree[0]=newLine_T(p1,p2);

lthree[1]=