Ear-Clipping Triangulation
While not the most efficient triangulation algorithm, it is the most intuitive. An ear of a polygon is a vertex V, such that the line segment between the two neighbors of V lies entirely inside the polygon. In fact, every simple polygon with more than three vertices has at least two ears. Here you can check out the proof of the Two Ear theorem. Meanwhile, we will move counter-clockwise along the polygon and repeatedly cut off ears one by one until we are left with only one triangle. Enjoy this small demo!
Click on the canvas to place some vertices. When you press "Start!" I will connect origin to the last point. You should avoid overlaps, otherwise
results will be weird.
And here's a bull polygon for you to try. But I would recommend being careful when clipping bull's ears.