Delaunay三角剖分

《Delaunay三角剖分》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、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步，当遍历了一次凸包后，凸包生成完成。二、环切边界法凸包三角剖分：在凸包数组中，每次寻找一个由相邻两条凸包边组成的三角形，在该三角形的内部和边界上都不包含凸包

2、上的任何其他点，然后去掉该点得到新的凸包链表，重复这个过程，最终对凸包数组中的点进行三角剖分成功。三、离散的内插：1）建立三角形的外接圆，找出外接圆包含待插入点的所有三角形，构成插入区域；2）删除插入区域内的三角形公共边，形成由影响三角形顶点构成的多边形；3）将插入点与多边形所有顶点相连，构成新的Delaunay三角形；4）重复1，2，3，直到所有非凸包上的离散点都插入完为止。功能实现流程：1.在绘图菜单栏下添加一个子菜单项为Delauney，并且在工具栏上添加一个工具项。设置text为Delaunay三角剖分，name为delaunay等属性，添加单击事件，并为单击事

3、件代码2.为事件函数添加如下代码Graphicsgra=panel1.CreateGraphics();Listpts=newList();foreach(Geometry_Tgeoinchoosegeos.Geofeatures){if(geo.GetType()==typeof(Point_T)){Point_Tpt=(Point_T)geo;pts.Add(pt);}}Listdeltins=DelauneyTin(pts);//根据多点构建delauney三角网foreach(Tintinindeltins){Poi

4、nt[]ctin=newPoint[3];for(inti=0;i<3;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;}}publ

5、icPoint_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]=newLine_T(p2,p3);lthree[2]=newLine_T(p3,p1);}}4.圆的数据结构publicclassCircle_T:Geometry_T{privatePoint_Tcpt;

6、publicPoint_TCpt{get{returncpt;}set{cpt=value;}}doubleradius;publicdoubleRadius{get{returnradius;}set{radius=value;}}publicCircle_T(){}publicCircle_T(Point_Tpt,doubler){cpt=pt;radius=r;}}5.实现Delaunay三角剖分算法1）publicListDelauneyTin(Listpts)//根据多点构建delauney三角网；分三步：构建凸包；凸包剖分；离散点

7、内插{Graphicsgra=panel1.CreateGraphics();Listdeltins=newList();Listenvpts=EnvelopeTin(pts);//构建凸包//for(inti=0;i