Monotone Polygon Triangulation

This is a small toy (made with Dart, compiled to JavaScript), to illustrate the algorithm to triangulate a Monotone Polygon. With this one, it only works for X-Monotone Polygons. You'll find the algorithm starting at page 20 in these lecture notes. For best results I recommend drawing a Simple Polygon. If you give it one that is not, the triangulation may be a little unexpected.

You can find the source code for this program here on GitLab.

Controls:

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.

Algorithm:

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).

Case 1: The current Point (p) is on an opposite side of the Reflex Chain

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.

Case 2a: The current Point (p) is visible to some (or all) Points on 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.

Case 2b: The current Point (p) is not visible to any Points on the Reflex Chain.

Just add p to the Reflex Chain.