A comparison of Ear Clipping and a new Polygon Triangulation Algorithm

Abstract: The simple polygon triangulation is an classic problem in computational geometry and the techniques are widely used in many field. Many existing techniques have short running time but are hard to implement, some are easy to achieve, however, the output quality always bad and are time consuming. This paper propose a diagonal inserting algorithm which is easy to implement and can enhance the final quality. This presented algorithm was implemented and compared with the ear clipping technique which is simple to carry out and long-standing in the triangulation history. These two algorithms were tested on various polygons and an analysis concerning the quality, speed and the standard deviation of the output triangles` size is done.