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