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.



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.



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.