基于线性和岛屿约束的Delaunay三角网构建算法研究  

Study on the Algorithm for Constructing Two-Dimensional Delaunay TIN Based on Constraints of Linear and Islands

作　　者：张咏[1] 侯恩科[2] 董汉军[1] 

机构地区：[1]西安科技大学测绘科学与技术学院,陕西西安710054 [2]西安科技大学地质与环境工程学院,陕西西安710054

出　　处：《地理与地理信息科学》2010年第4期37-41,共5页Geography and Geo-Information Science

基　　金：国家自然科学基金项目(40972204)

摘　　要：针对基于线性和岛屿约束的Delaunay三角网构建算法的不足,从减少算法计算机实现步骤出发,研究改进了线段相交判断、首三角形确定等影响域多边形搜索相关算法;在分析当前存在的多边形三角剖分算法基础上,给出了存在重复点(悬边)的多边形三角剖分算法;在影响域多边形搜索阶段充分利用多边形间的拓扑关系信息,消除了岛屿约束内部三角形删除时需遍历三角形数据的不足。算法涵盖线性和岛屿约束的构建,综合性强,效率高且易于实现。There are many algorithms for constrained Delaunay triangular irregular network at present,but there are some deficiencies for these algorithms.Therefore,the algorithm is studied starting from computer implementation steps on constraints of linear and island in this paper.New improvements of algorithm for line intersection are to reduce the steps in the realization of the computer and to raise operational efficiency.Searching algorithm of the triangle containing the first point has been simplified and expanded.On the analysis of the current existence of the polygon triangulation algorithm,the detailed polygon triangulation algorithm is given,which is containing duplicate points,so it is concise and easy to complete.Constraint of island is on the full use of polygon topology information in the polygon search phase,which can avoid scanning internal triangle data and improve eliminating efficiency.The algorithm has wide range of applications,and is integrated,efficient and easy to implement.

关 键 词：约束三角网 悬边 岛屿 多边形三角剖分 

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