Monotone Polygon Triangulation
You can find the source code for this program here on GitLab.
Use the Left Mouse Button to add Points to the Polygon. Right Click to remove the last added Point.
If the Polygon turns red, that means that it isn't X Monotone and will not triangulate.
At least four Points are needed to Triangulate.
The Points with a green ring around them are part of the Upper Chain, where as the ones with a purple ring around them are from the Lower Chain. If a ring is filled in with red, that means it's part of the Reflex Chain at that step. The vertical red line marks which Point is currently being tested.
The boxes below highlight which case of the algorithm the current Point is hitting.
First split the Polygon into two chains, an Upper Chain that contains the topmost Points, and a Lower Chain that contains the bottommost Points.
With respect to an ascending X axis value, push the first two Points from the Upper & Lower Chains onto the Reflex Chain (Which is a LIFO).
v = topmost Point on the Reflex Chain.
Draw a diagonal from each Point on the Reflex Chain to p.
Clear the Reflex Chain.
Push v back onto the Reflex Chain.
Push p onto the Reflex Chain.
Draw a diagonal from each Point on the Reflex Chain that is visible to p.
Remove all of the Points from the Reflex Chain where there was a diagonal drawn, except for the last one.
Add p to the Reflex Chain.
Just add p to the Reflex Chain.