基于边优先的任意多边形最优三角剖分  

An optimal triangulation algorithm for general polygon based on edge prior

作　　者：翟仁健[1] 武芳[1] 薛本新[2] 

机构地区：[1]解放军信息工程大学测绘学院,郑州450052 [2]总参测绘信息中心,北京100088

出　　处：《测绘科学》2008年第1期122-125,共4页Science of Surveying and Mapping

基　　金：国家自然科学基金(40471115、40671162)

摘　　要：针对现有多边形三角剖分算法不能同时兼顾算法的简单有效性、适用性以及剖分三角网质量的问题,提出一种基于边优先的任意多边形最优化三角剖分算法:首先直接对多边形的边进行构网,最后再对生成的非约束边进行构网,最终完成整个多边形的三角剖分。剖分得到的三角网为约束Delaunay三角网,网形稳定、最优,算法简单,执行效率较高,且适用于任意复杂多边形。实验证明了该算法的合理性和有效性,较好地解决了现有多边形三角剖分算法存在的问题。Aiming at the problem that present polygon triangulation algorithms can't simultaneously give attention to briefness, efficiency, applicability and quality of triangulation, a new optimal triangulation algorithm for general polygon based on edge prior is proposed.Firstly, the algorithm creates triangles for edges of polygon, and then for non-constrained edges, at last, the triangulation for polygon is accomplished.The results of the triangulation are constrained Delaunay triangulation meshes.The shape of the meshes is stable, optimized.The algorithm is simple, with high efficiency and the same with random complicated polygons.The experiment results prove the rationality and efficiency of the algorithm, and have a better solution for the problems that existed in present polygon triangulation algorithms.

关 键 词：任意多边形 三角剖分 约束特征边 

分 类 号：TP391[自动化与计算机技术—计算机应用技术] P208[自动化与计算机技术—计算机科学与技术]