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.