Triangulation of Concave Polygons

Abstract

In application fields such as pattern recognition, computer graphics, computer-aided design, and solid modeling, the task to triangulate simple polygons is very helpful. The triangulation of simple polygons is one of the most fundamental fields in computational geometry. A simple polygon can be decomposed into triangles, trapezoids, and convex polygons. Traditional clipping polygon algorithms will make mistakes because they cannot separate the clipping polygons independent when clipping concave polygons. We let all the polygons become convex polygons. The problem will be solved by polygon triangulation because triangles are always convex polygons. Two lemmas are proposed in this paper. The first lemma is used for reducing diagonals used and triangles formed in the triangulation especially for the simple concave polygon when several vertices of the polygon are collinear. The second lemma is the basis for a definite triangulation procedure for concave polygons. The procedure is continuously partitioning triangles from reflex vertices. The complexity of the partitioning procedure is in linear time.