C Delaunay三角剖分 - 图文.docx

C Delaunay三角剖分 - 图文 Delaunay三角剖分在实际中运用的最多的三角剖分是Delaunay三角剖分首先，我们来了解一下Delaunay边Delaunay边的定义为：假设E中的一条边e〔其端点为a,b〕，假设e满意条件：存在一个圆经过a,b两点，圆内不含点集中任何其他的点，这一特性又称空圆特性，那么称之为Delaunay边：Delaunay三角剖分的定义为：假如点集的一个三角剖分只包含Delaunay边，那么该三角剖分称为Delaunay三角剖分要满意Delaunay三角剖分的定义，必需符合下面两个重要的准那么： 1〕空圆特性：Delaunay三角网是唯一的，在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在；2〕最大化最小角特性：在散点集可能形成的三角剖分中，Delaunay三角剖分所形成的三角形的最小角最大从这个意义上讲，Delaunay 三角网是“最接近于规那么化的”的三角网详细来说是指在两个相邻的三角形构成凸四边形的对角线，在相互交换后，六个内角的最小角不再增大经典的Delaunay剖分算法主要有两类[1]：1〕增量算法：又称为Delaunay空洞算法或加点法，其思路为从一个三角形起先，每次增加一个点，保证每一步得到的当前三角形是局部优化的三角形。

2〕局部变换法：又称为换边或换面法，其思路为构造非优化的三角网，然后对两个共边三角形形成的凸四边形迭代换边优化迄今为止关于Delaunay剖分已经出现了许多算法，主要有分治算法、逐步插入法、三角网生长法等其中三角网生长算法由于效率较低,目前较少采纳; 分治算法最为高效,但算法相比照较困难;逐点插入法实现简洁,但它的时间困难度差[2]特殊是近些年，随着计算机水平的不断提升，又出现了各种各样的改良算法本节将主要依据逐步插入法的原理，通过对赐予的数据高程点进展Delaunay三角剖分其根本步骤为：1〕获得点集坐标数组；2〕获得点集外围边界；3〕依据边界及内部点生成三角网现新建一个工程，并命名为“Delaunay三角剖分”，同时添加相关的引用及定义“启动CAD〔〕”函数1、获得点集坐标数组添加一个按钮，设置其Name和Text属性都为“获得点集坐标数组”，为其Click事务添加代码如下： private void 获得点集坐标数组_Click(object sender, EventArgs e) { Microsoft.VisualBasic.Interaction.AppActivate(AcadApp.Caption); AcadSelectionSet mySelectionSet; mySelectionSet = AcadDoc.SelectionSets.Add(\); Int16[] FilterType = new Int16[1]; object[] FilterData = new object[1]; FilterType[0] = 0; FilterData[0] = \; mySelectionSet.SelectOnScreen(FilterType, FilterData); double[] arrPoints = new double[3 * mySelectionSet.Count]; int count = 0; foreach (AcadObject acadObj in mySelectionSet) { if (acadObj.ObjectName == \) { count++; double[] PointCoord; PointCoord = (Double[])(((AcadPoint)acadObj).Coordinates); arrPoints[3*count - 3] = PointCoord[0]; arrPoints[3 * count - 2] = PointCoord[1]; arrPoints[3 * count - 1] = PointCoord[2]; } } MessageBox.Show(\共选择点的个数为：\ + count.ToString()); AcadDoc.SelectionSets.Item(\).Delete(); } 其中，arrPoints数组保存各点的坐标值。

2、获得点集外围边界依据前面获得的外围点集来获得外围边界，其主要思路为：1〕搜寻X坐标最小的点，在此称为startPoint，从该点起先搜寻下一点，本例中以逆时针方素来搜寻边界；2〕现定义一个虚拟点〔该点并不存在〕位置为startPoint正北方向，该点与startPoint形成一个向量Vector1，下一点〔判定是否为边界点的点，或称选取的点〕与startPoint也形成一个向量Vector2，那么判定该选取的点是外围边界点所要满意的条件为向量Vector2与向量Vector1之间的夹角最大；3〕按同样的方式，新形成的向量Vector1为新选取的外围边界点与上一个外围边界点形成的向量，向量Vector2为选取的点与新选取的外围边界点形成的向量，判定该选取的点是外围边界点所要满意的条件仍旧为向量Vector2与向量Vector1之间的夹角最大；4〕按此思路循环进展，直到找到一个边界点与startPoint一样为了数据查询、调用便利以及数据构造的管理，在调用任何一个点、边或三角形时只须要通过索引即可调取故在全局变量中定义如下类用于管理边和三角形： public class Edge { public int Start;//边的起点 public int End;//边的终点 public int LeftTri = -1;//左边三角形索引 public int RightTri = -1;//右边三角形索引 } public class Tri { public int NodeA;//第一个节点的索引 public int NodeB;//其次个节点的索引 public int NodeC;//第三个节点的索引 public int AdjTriA = -1;//第一个邻接三角形索引 public int AdjTriB = -1;//其次个邻接三角形索引 public int AdjTriC = -1;//第三个邻接三角形索引 } 此外，在全局变量中定义边和三角形数组〔由于在此用到了ArrayList，所以须要添加引用“using System.Collections;”〕，其代码如下： private ArrayList arrayEdges = new ArrayList(); private ArrayList arrayTris = new ArrayList();下面从startPoint起先通过找寻最大夹角来获得外围边界点，其代码如下： //获得点集外围边界 int i, startIndex = 0, tempIndex, lastIndex, pointCount = arrPoints.Length / 3; for (i = 1; i angleMax) { angleMax = angleTemp; edge.End = i; lengthMin = vector2Length; } else if (angleTemp == angleMax && vector2Length 0)//假如点j在向量vector1的左侧 { vector3[0] = arrPoints[3 * j] - arrPoints[3 * edge.End]; vector3[1] = arrPoints[3 * j+1] - arrPoints[3 * edge.End+1]; vector1Length=Math.Sqrt(vector1[0]*vector1[0]+vector1[1]*vector1[1]);vector2Length=Math.Sqrt(vector2[0]*vector2[0]+vector2[1]*vector2[1]);vector3Length=Math.Sqrt(vector3[0]*vector3[0]+vector3[1]*vector3[1]); angleV1V2Temp = Math.Acos((vector1[0] * vector2[0] + vector1[1] * vector2[1]) / (vector1Length * vector2Length)); angleV2V3Temp = Math.Acos((vector2[0] * vector3[0] + vector2[1] * vector3[1]) / (vector2Length * vector3Length)); if (angleV2V3Temp > angleV2V3Max) { angleV2V3Max = angleV2V3Temp; angleV1V2Max = angle。