Algorithms for triangulating simple polygons

摘要

Decomposition of simple polygons into simpler components is one of the basic tasks in computational geometry. The most important simple polygon decomposition is triangulation. The paper presents an overview of simple polygon triangulation algorithms which can be classified into three groups: algorithms based on diagonal inserting, algorithms based on Delaunay triangulation and algorithms using Steiner points. From each group the most important algorithms and their features are presented. The last part of the paper summarizes the common features of the groups and presents the comparison of four algorithms that are based on diagonal insertion.