Triangulation by Ear Clipping

Ears: a part of the polygon where the vertices form a triangle.

Indexes points of the triangle and locates a valid "ear." Then captures that as the triangle and collapses an edge to remove the triangle. Repeat until the entire shape has been triangulated.

Some intricate rules for processing polygons with one or more holes within. Depending on the complexity of the shape and how many holes are present requires a different algorithm. This ultimately splits the polygon in to smaller ones that no longer contain holes but are still overlaid to appear identical to the artist's intent.

Makes reference to two other papers with more efficient triangulators but are much harder to implement: B. Chazelle. Triangulating a simple polygon in linear time. Discrete Comput. Geom., 6:485–524, 1991. [2] B. Chazelle and J. Incerpi. Triangulation and shape complexity. ACM Trans. on Graphics, 3:135–152, 1984.