Simple 2d polygon triangulation

You are doing a version of "ear clipping" approach to triangulation, see: http://en.wikipedia.org/wiki/Polygon_triangulation

Your algorithm fails if another polygon vertex (say from the other side of the polygon) ends up inside the triangle 'ear' you form. Consider this example:

Your algorithm will choose A first, and make a triangle with the two adjacent edges (connected with the dashed line). But this triangle includes another vertex (B) and is clearly incorrect.

The generalized ear clipping approach depends on finding ears you can clip off that do not have any included vertices.

Simple Convex Polygons are O(n)

This is when you want to handle simple polygons like rectangles, pentagons, hexagons and so on. Here you just take a starting point and connect it to all other vertices. This algorithm is trivial and what I really wanted was a more general solution that could handle concave and polygons with holes.

In order to deal with more complex polygons like the one Payne provided...

Arbitrary Polygon to Triangle in O(n log n)

While there are algorithms that run faster, the faster algorithms become very complicated. Kirkpatrick et al. found an algorithm to run in O(n log log n) and Chazelle did it in O(n). However, the easiest thing to implement is probably the Seidel algorithm that runs in O(n log n).

The algorithm is a 3-step process

1. Decompose the polygon into trapezoids
2. Decompose the trapezoids into monotone polygons
3. Decompose the monotone polygons into triangles

C source

If you're interested in C source it can be obtained from University of North Carolina at Chapel Hill. In general the code quality is good, handles holes, but will probably need to be massaged to your needs.