Triangulating Arbitrary Polygons

By combining the algorithm for splitting polygons to monotone pieces with an algorithm for triangulating monotone polygons, we can triangulate arbitrary polygons.

The following image shows a triangulated polygon. The monotone pieces are shown in different colors and each of these pieces is triangulated independently.