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

针对现有多边形三角剖分算法不能同时兼顾算法的简单有效性、适用性以及剖分三角网质量的问题,提出一种基于边优先的任意多边形最优化三角剖分算法:首先直接对多边形的边进行构网,最后再对生成的非约束边进行构网,最终完成整个多边形的三角剖分。剖分得到的三角网为约束Delaunay三角网,网形稳定、最优,算法简单,执行效率较高,且适用于任意复杂多边形。实验证明了该算法的合理性和有效性,较好地解决了现有多边形三角剖分算法存在的问题。

An optimal triangulation algorithm for general polygon based on edge prior

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.