曲线约束Delaunay三角剖分及在地形构建中的应用  

CURVE CONSTRAINED DELAUNAY TRIANGULATION ALGORITHM AND ITS APPLICATION IN TERRAIN CONSTRUCTION

作　　者：孙劲光[1] 周勃[2] 

机构地区：[1]辽宁工程技术大学电子与信息工程学院,辽宁葫芦岛125105 [2]辽宁工程技术大学研究生学院,辽宁葫芦岛125105

出　　处：《计算机应用与软件》2015年第12期25-28,41,共5页Computer Applications and Software

基　　金：国家科技支撑计划项目(2013BAH120f00)

摘　　要：针对采用约束Delaunay三角剖分算法构建地形时如何确保地形数据中的曲线约束条件在剖分结果中存在的问题,提出提取能够反映地形自身几何特征的特征点的方法对约束曲线进行直线段逼近,并对允许逼近误差的取值给予分析和验证。实现了使用较少的点对约束曲线进行最大程度逼近;在解决约束直线段不在Delaunay三角剖分中的问题时,提出在原约束曲线上进行加特征点细分的方法;针对地形数据量大构网时间长的问题,改进Delaunay三角网格生成算法。实验结果表明算法能够确保约束曲线在网格中存在,提高了对原曲线的逼近程度且提高了运算效率。算法可以实现对复杂区域的正确处理。In order to make sure the conditions of constrained curves of terrain data existing in subdivision result when using constrained Delaunay triangulation algorithm to construct the terrain,we presented the method of extracting the feature points capable of reflecting the geometrical features of terrain itself to approach the constrained curves＇ straight line sections,and to analyse and verify the values granting the approximation errors. We realised to use fewer points to approach the constrained curve to the most extent. In order to solve the problem that the constrained straight line did not exist in Delaunay triangulation mesh,we put forward a method to subdivide the added feature points on the original constrained curves. In light of the problems of large terrain data amount and long mesh construction time,we improved the Delaunay triangular mesh generation algorithm. Experimental results showed that the algorithm can ensure the existence of the constrained curves in mesh,and improved the approximation degree on original curves as well as improved the operation efficiency. The algorithm can achieve the correct processing on complex region.

关 键 词：地形重构 特征点提取 曲线约束Delaunay 离散误差 曲线离散化 Delaunay三角网格 

分 类 号：TP391.14[自动化与计算机技术—计算机应用技术]