C# Delaunay三角剖分
- 格式：doc
- 大小：318.50 KB
- 文档页数：15
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("NewSelectionSet001");
Int16[] FilterType = new Int16[1];
object[] FilterData = new object[1];
FilterType[0] = 0;
FilterData[0] = "POINT";
mySelectionSet.SelectOnScreen(FilterType, FilterData);
double[] arrPoints = new double[3 * mySelectionSet.Count];
int count = 0;
foreach (AcadObject acadObj in mySelectionSet)
{
if (acadObj.ObjectName == "AcDbPoint")
{
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("NewSelectionSet001").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 < pointCount; i++) //寻找X值最小的点号
{
if (arrPoints[3 * i] < arrPoints[3 * startIndex])
{ startIndex = i;
}
}
Edge edge = new Edge();
edge.Start = startIndex;
lastIndex = startIndex - 1;
tempIndex = startIndex;
double[] vector1 = new double[2], vector2 = new double[2];
vector1[0] = 0; vector1[1] = 100;
double vector1Length,
vector2Length,angleTemp,angleMax,lengthMin;
angleMax = 0;
while (lastIndex != startIndex)
{
vector1Length = Math.Sqrt(vector1[0] * vector1[0] + vector1[1] *
vector1[1]);
lengthMin = 300;
for (i = 0; i < pointCount; i++)//找边界
{
if (i != edge.Start)
{
vector2[0] = arrPoints[3 * i] - arrPoints[3 * tempIndex];
vector2[1] = arrPoints[3 * i+1] - arrPoints[3 *
tempIndex+1];
