利用自适应分块的任意多边形三角剖分算法

An Optimal Triangulation Algorithm for General Polygon Based on Adaptive Partitioning

三角剖分算法是计算几何领域中的重要课题之一,针对现有多边形三角剖分算法大多不能同时兼顾算法的简单有效性、适用性以及三角网的质量问题,提出一种基于自适应分块的任意多边形三角剖分算法。多边形的自适应分块区别于传统的格子分块,它充分顾及了多边形边作为剖分三角网约束边这一特点,通过选择原始多边形一定数量的边,并对这些边构建最优三角形,将原始多边形分割成若干个小的简单多边形,这些简单多边形之间通过三角形进行连接。至此,原始多边形的三角剖分直接转化为这些简单多边形的三角剖分,这样由一条边寻找一顶点构建最优三角形,直接在该边所在的简单多边形内进行搜索,大大减少了点的搜索范围,提高了算法效率。利用基于边优先的多边形三角剖分算法对分块后的小多边形进行三角剖分,从而完成整个多边形的三角剖分。算法具有适用性广,剖分三角形网形稳定、最优,思路简单,易于实现,执行效率高的特点,最后通过实验证明了本算法的科学性和先进性。

Triangulation algorithm is an important research field of computational geometry. Aiming at the problem that the existing triangulation algorithms can＇t give attention to briefness but efficiency, applicability and quality of triangulations, a new optimal triangulation algorithm for general polygon based on adaptive partitioning was proposed. The method of adaptive partitioning for polygon differed from the method of grid partitioning in which it thought about characteristic of edges of polygon acting as the constrained edges of triangulation networks, and created optimal triangles from selecting a few edges of the original polygon. These triangles divided original polygon into a lot of simple small polygons which were joined by the triangles. Thus, triangulation for original polygon was transformed into triangulation for small simple polygons, and the work of creating optimal triangles which realized by searching a vertex based on an edge of polygon could be accomplished in the simple small polygon. In this way, the process greatly reduced searching range of vertex, and improved the efficiency of the algorithm highly. Triangulation of the simple small polygon was achieved by the triangulation algorithm based on constrained edge considered primarily. Results of the triangulation were constrained Delaunay triangulation networks, shape of the networks were stable and optimized. The algorithm was simple, with high efficiency and could be applied to any complicated polygons. Finally, the scientificalness and efficiency of the algorithm were proved by the application experiment.