在AutoCAD环境下不规则三角网构建及等高线生成

代 莉，陈春华，聂 焱

（湖北省测绘工程院，湖北武汉 430071）

在AutoCAD环境下不规则三角网构建及等高线生成

代 莉，陈春华，聂 焱

（湖北省测绘工程院，湖北武汉 430071）

对不规则三角网的生成进行了分析，在AutoCAD环境下使用三角形生成算法，将离散点构建成不规则三角网，并在此三角网的基础上生成相应的等高线。

数字高程模型；不规则三角网；Delaunay三角网；等高线

地球表面高低起伏，呈现为一种连续变化的曲面，这种曲面无法用平面地图来确切表示。于是我们就利用一种全新的数字地球表面的方法--数字高程模型（DigitalElevationModel，缩写DEM）表示，这种方法已经被普遍广泛采用。DEM是一定范围内规则格网点的平面坐标（X，Y）及其高程（Z）的数据集，它主要是描述区域地貌形态的空间分布，是通过等高线或相似立体模型进行数据采集（包括采样和量测），然后进行数据内插而形成的。DEM 是对地貌形态的虚拟表示，可派生出等高线、坡度图等信息，也可与DOM或其他专题数据叠加，用于与地形相关的分析应用，同时它本身还是制作DOM的基础数据。

1 不规则三角网生成的算法

在地理信息系统中，DEM最主要的三种表示模型是：规则格网模型，等高线模型和不规则三角网模型。目前常用的算法是通过等高线和高程点建立不规则的三角网 (Triangular Irregular Network,简称TIN),然后在TIN基础上通过线性和双线性内插建DEM。

不规则的三角网是由Peuker和他的同事于1978年设计的一个系统，它是根据区域的有限个点集将区域划分为相等的三角面网络，数字高程由连续的三角面组成，所有三角面相互邻接，互不相交，互不重叠，三角面的形状和大小取决于不规则分布的测点的密度和位置，能够避免地形平坦时的数据冗余，又能按地形特征点如山脊、山谷线、地形变化线等表示数字高程特征。TIN常用来拟合连续分布现象的覆盖表面。

Delaunay三角网，具有空外接圆，以及最小角最大的特性，可最大限度的保证网中三角形满足近似等边形状，在地形拟合方面表现最为出色，且 Delaunay三角网结构良好，数据结构简单，数据冗余度小，存储效率高，可适应各种分布密度的数据，因此常被用于TIN的生成。

根据构建三角网的步骤，可将三角网生成算法分为三类：①分而治之算法（由Shmaos和Hoey提出），其基本思路是使问题简化，把点集划分到足够小，使其易于生成三角网，然后把子集中的三角网合并生成最终的三角网，用局部优化（LOP，即LocalOptimization Procedure）算法保证其成为Delaunay三角网，它的优点是时间效率高，但需要大量递归运算，因此占用内存空间较多；②数据点渐次插入算法（由 Lawson提出），其思路很简单，先在包含所有数据点的一个多边形中建立初始三角网，然后将余下的点逐一插入，用LOP算法保证其成为Delaunay三角网。此算法虽然容易实现，但效率极低；③三角网生长算法，在这三种算法中，三角网生长算法在80年代以后的文献中已很少见，该算法是由M ichael J.M cCullagh,CharlesG.Ross提出的。

下面以图1中的离散点为例（该离散点均取自高程点），讨论三角形生长算法在AutoCAD中的实现。

图1 离散点分布图

1.1 数据结构设计

在不规则三角网生成的过程中，最重要的两个表就是三角形表和三角形的边表。三角形表是用来存放所有生成的三角形，存放的格式为：（点1的坐标，点2的坐标，点3的坐标，指针），点1、点2、点3为三角形的3个顶点，坐标格式为（X，Y，Z），且方向为逆时针。指针则是指向三角形三条边的邻接三角形，初始值为（-1，-1，-1）。三角形的边表存放已生成的三角形的三条边，存放格为（第一个点坐标，第二个点坐标），和三角形存放顺序一样，也是按逆时针。

1.2 初始三角形生成

首先要选择初始三角形的起始点。以离散点的坐标（X,Y）为参照，取X+Y值最小的那个点作为三角形的起始点。该起始点在图1的左下角。如图2所示点 A，就是遍历所有的点后，用比较算法得到的初始三角形的起始点。

图2 初始三角形起始点

然后寻找离点A最近的那个点B，就构成初始三角形的起始边（如图3所示）。

图3 初始三角形的起始边

根据Delaunay三角网的空外接圆性质，寻找第三个点。以AB边对角为参照对象，寻找最大的∠ACB，如图4所示就得到初始三角形ABC。

图4 初始三角形ABC

数据结构中要求所有的三角形按逆时针的方向存储。那么就要判断点C在AB边的位置，如果在AB边的右边的话，就交换B、C两点。那么初始三角形修改如图5所示。

图5 修改后的初始三角形

以初始三角形为例，三角形的存储格式为（点 A坐标，点B坐标，点C坐标，（-1，-1，-1））。边表的存储格式为（（点A，点B），（点B，点C），（点C，点A））。

1.3 扩展三角形

以图5中的初始三角形为例。先从AB边扩展，首先要选择在AB边右边的点。用公式：(ym-ya)*(xb-xa)-(yb-ya)*(xm-xa)来判断点的位置，（xa，ya）为点 A的坐标，（xb，yb）为点B的坐标，（xm，ym）为扩展点M的坐标。若值大于 0，点在直线的左边；若值等于 0，点在直线上；若小于0，点在直线右边。再根据Delaunay三角网的空外接圆性质，确定扩展三角形的第三个点M。同时还要判断扩展三角形的边AM,MB是否存在于边表。

在这里，边表的作用就是判断是否存在重复的三角形。以边 AB为例，由于方向性的问题，在相邻三角形中的同一条边存储格式分别为(A，B)和(B，A)，也就是说不会有第三个三角形会有AB或BA这条边；否则就会出现三角形重复或者三角形相交的问题。

满足以上条件，就可以确定扩展三角形的点 M。将该扩展三角形添加到三角形表中，同时也将三角形的三条边添加到边表中，还要修改对应三角形的指针。若没有符合条件的点M，则直接处理下一条边。

BC边的扩展同AB边一样。

两边均处理完后，再从三角形表中取出下一个三角形，按上述方法扩展，直至所有三角形扩展完毕。

如图6所示，即为图1的离散点得到的三角网。

2 等高线生成

三角形表中存放了不规则三角网中所有的三角形，以及指向相邻三角形的指针。根据三角形 3个顶点的Z值，就可以判断某一高程值的等高线是否穿过该三角形。若等高线经过该三角形，就要判断等高线经过的是三角形的哪两条边并计算交点的坐标，交点坐标可以根据插值公式得到。根据指针，就可以继续判断相邻的下一个三角形，直至遍历三角网中所有的三角形。最后将所有交点按顺序连接起来就可以得到该高程值的等高线。

要生成全图的等高线，就需要高程范围，这个可以直接遍历全图的高程点得到。

如图7所示，为在图6的不规则三角网的基础上生成的5m等高距的等高线。

图6 不规则三角网

图7 等高线

3结语

本算法在AutoCAD中已经实现并调试完成。利用三角形生长算法实现Delaunay三角网构建并不是最优的算法，存在计算的时间复杂性不能彻底解决的问题，也就是说离散点越多，生成Delaunay三角网花费的时间也就越多。且算法中选取的离散点为实际测图中的高程点，若要得到更贴合地面形态的 TIN，就要求测图中的高程点为特征点。若要提高运算速度又要更好地贴合地面形态，需要在今后的工作中进一步探索和研究。

[1] 南胜.基于不规则三角网(TIN)数模建构的优化算法[J].浙江测绘,2007(1):5-7

[2] 王建雄.CAD环境下基于不规则三角网的DEM算法及实现[J].云南农业大学学报,2005,20(4):573-576

[3] 蒋瑜,杜斌,卢军,等.基于Delaunay三角网的等值线绘制算法[J].计算机应用研究,2010,27(1):101-103

[4] 马智民,罗斌.Delaunay三角网构建DEM整体优化算法[J].长安大学学报:自然科学版,2008,28(3):44-48

[5] 任振娜,李斌兵,周浩,等.应用等高线构Delaunay三角网算法的研究与实现[J].工程图学学报,2006(6):54-58

[6] 张巧凤,张锦.基于MapX二次开发生成Delaunay三角网[J].测绘工程，2005,14(1):59-62

[7] 芮一康,王结臣.Delaunay三角形构网的分治扫描线算法[J].测绘学报,2007,3：358-362

Construction of TIN and Generation of Contour Lineon AutoCAD

by DAILi

The generation of TIN was being analysed.According to algorithm of triangle generation,construct the TIN while based on discrete point in Auto CAD,and generated contour line of arbitrary height the same.

DigitalElevation Model，Triangular Irregular Network，Delaunay triang ularnet work，contour line （Page:40）

P208

B

1672-4623(2011)02-0040-03

2010-10-08

项目来源：精密工程与工业测量国家测绘局重点实验室2009年开放基金资助项目（PF2009-D,PF2009-23)

代莉，工程师，研究方向为测绘工程。