基于平衡二叉树的三角网快速生成算法  

Algorithm of delaunay triangulation generation based on AVL tree

作　　者：邹徐文[1] 武百超[1] 崔继宪[1] 

机构地区：[1]辽宁工程技术大学测绘与地理科学学院,辽宁阜新123000

出　　处：《辽宁工程技术大学学报（自然科学版）》2007年第4期513-516,共4页Journal of Liaoning Technical University (Natural Science)

基　　金：辽宁省地理空间信息技术与应用重点实验室基金资助项目(200413)

摘　　要：为了研究更好的三角网构建的方法,对不规则三角网构建算法进行了研究,提出了一种基于平衡二叉树的Delaunay三角网生成算法,采用分割合并的思想,提高了搜索效率,将离散点集进行划分,通过对各个所分小块子网的合并,完成所论区域的三角剖分。分析了该算法涉及的相邻子网公切线查找、凸壳生成等关键问题。通过具体实验和同其他经典算法效率的比较,该方法具有明显的优越性。The algorithm of irregular triangulated network generation is researched and a new algorithm based on AVL Tree is proposed .Based on division-merging thinking ,scattered points are divided and delaunay triangulation is completed in study area .Some key problems are analyzed ,such as the finding on common tangent of adjacent sub-network, protruding polygon generation ,etc. Experiment result data is deduced by Compared with other irregular ways, the algorithm shows its superiority.

关 键 词：不规则三角网 平衡二叉树 数字高程模型 

分 类 号：P208[天文地球—地图制图学与地理信息工程]