一种三角网的快速生成算法.pdf

《一种三角网的快速生成算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第1期矿山测量NO．12010年2月MINESURVEYINCFeb．2O10doi：10．3969／j．1ssn．1001—358X．2O10．01．012一种三角网的快速生成算法武百超，吴捷．崔继宪(1．东北林业大学土木工程学院，哈尔滨150040；2．黑龙江科技学院，哈尔滨150027：3．煤炭科学研究总院唐山研究院，河北唐山063000)摘要：提出了一种基于平衡二叉树的Delaunay三角网生成算法。采用分割合并的思想，将离散点集进行划分，通过对各个所分小块子网的合并，完成三角网的构建。同时，分

2、析了该算法涉及的相邻子网公切线查找、凸壳生成，分层等关键问题，最后依据实验数据进行了验证。关键词：不规则三角网；平衡二叉树；数字高程模型中图分类号：P208文献标识码：B文章编号：1001—358X(2010)01—0043—03改进应用于生成Delaunay三角网。其后，Lee、1引言Guibas、Dwyer和Katajainen等不断进行了改进。本数字地面模型(DTM)是地表地理位置和其相关文提出了基于平衡二叉树(AVL)的三角网生成的分的地表属性信息的数字化表现，当地表属性值为高治算法。程时，表示

3、数字高程模型(DigitalElevationModel，分割一合并算法的基本思想：首先将点集数据DEM)，以不规则三角网(IrregularTriangulatedNet—进行排序、分割，递归地把点集划分为足够小、互不work，TIN)为表现形式的数字地面模型与以网格表相交的子集，在每一个子集内构建Delaynay三角网。现的形式相比，更能反映原始地形的细节，而且具有由于点集分布的不均匀性，如何对点集进行分割是地表重构精度高及不规则区域数据点分布适应能力一个关键问题，它直接影响其后子集的合并效率，根强

4、的特点。1934年，俄国数学家B．Delaunay由V据分割、合并方法的不同，可以分为单向、双向、四又一图演化出了更易于分析应用的Delaunaytriangula—树等。Lee和Schachter按照点集的X值进行单向排tion(简称Delaunay三角网)。序、分割，这样容易形成狭长的三角形，在合并进行Delaunay三角网就是连接V一图的所有相邻LOP处理时，交换边的概率较大，严重影响整个构建Vornonoi多边形的中心所生成的三角网。Delaunay三角网的效率；Dwyer在此基础上进行了改进，

5、他首三角网具有以下性质：(1)唯一性；(2)空圆特先把点集分割成n／log(n)个子集，对每个子集构建性；(3)最大最小角特性；由于以上性质决定了Delaunay子三角网，然后对每行的子集进行横向纵Delaunay三角网具有极大的应用价值；同时，它也是向、合并，进而构建整个三角网；Katajainer和Koppin—二维面三角网中唯一的、最好的，在地形拟合方面en对Dwyer的算法进行改进，按照四叉树的方式进表现最为出色，因此常常被用于TIN的生成。到目行点集分割与子三角网合并，但是由于四叉树的叶前为止

6、，最终被人们广泛接受和采用的自动建立子节点内的点分布不均匀，可能出现0或1的情况，Delaunay三角网的算法基本可归为3类：分而治这样会影响Delaunay子三角网的合并效率。本文采之算法、逐点插入法和三角网生长法。其中三角网用基于平衡二叉树(AVLTree)的Delaunay三角网生生长算法由于算法效率较低，目前较少采用；逐点成算法。AVL树又称为高度平衡的二叉搜索树，它插入法虽然实现较简单，占用内存较小，但它的时是1962年俄罗斯两位科学家G．M．Adelson—Velsky间复杂度差，效率较低；

7、分割合并算法最为高效，与E．M．Lands共同提出的一种数据结构，取其发明由于其深度递归，对内存要求较高，算法相对较为人名字的首字母而得名。复杂。下面对分割一合并算法进行讨论：Shamos和2基于AVLTree的Delaunay三角网生成算法原理Hoey首次提出了分割合并算法思想，并给出了一个生成V图的算法；它后来被lewis和Robinson加以采用分割一合并算法的前提是对数据进行分41第1期矿山测量201O年2月割，并能进行效率较高的搜索，平衡二叉树(AVL)显——一一然符合这两点，本文采用基于平衡

8、二叉树的Delau—、、、／nay三角网生成算法。其基本思想是：①指定分割的·C．·＼R／．s／L／H阈值，即使每个子集包含的点不超过给定的阈值；②，‘／U一一·j首先按照x方向、然后y方向进行点集排序、分割，、／如此反复进行，直至所有子集都满足条件为止；其间，伴随平衡二叉树的生成，以及节点的插人；③基图1公切线查找流程图于所产生的AVL树，首先对叶子节点进行访问，生小值点；F为右网的纵坐标极大值点，I为右网的纵成各个叶子节点的子三角网，随