I've been reading up on triangulating polygons with O(n log n) complexity, but despite there apparently being dozens of papers on the topic, I've yet to find one that accurately describes the algorithm. An extremely vague explanation of the algorithm is: 1) Use plane sweeping to find the trapezoidal decomposition of the polygon 2) Insert diagonals which decompose the polygon into monotone subdivisions 3) Triangulate each monotone segment The details are very complicated and each website I've read has described the process differently. In fact none of the websites I've seen have provided information on all the steps. I now understand how to triangulate monotone polygons (step 3) and I'm pretty sure I've worked out how to decompose the polygon into trapezoids in O(n log n) time using binary trees. (step 1) However I'm at a loss at how to insert the diagonals in constant time and then iterate over the monotone segments. The polygon with diagonals added becomes like a graph, and there's seperate paths of traversal which each have their own version of the monotone triangulation algorithm running. This thing is even harder to implement in code than it is to understand the algorithm, and I'm not even sure if I'm understanding that correctly. Does anyone have a detailed description of the whole process which provides enough information to solve using code?

Are you familiar with sweep-line algorithms in general? It's a tricky idea, because you have to maintain a sorted set of segments without ever actually sorting them and without an actual defined ordering over them.

I tried to do this myself as well (for path finding via navmesh etc) and ended up just using GLU (OpenGL) tesselation.

If you're interested in that, you can search for the following: GLUtesselator, gluTessCallback, gluTessBeginPolygon and friends, it's fairly straight forward on how to grab the list of triangles from this but I can show you code if you give up :)

If you're interested in doing the tesselation youself for sure, good luck. I'd like to know if you ended up with something that works! (I'm in the same boat)

I've already decided to implement a simpler algorithm, but with worse time complexity. It's roughly O(n^2). Here's how I'm doing it:

1) Remove sequential line segments with the same gradient, so at any vertex v, the triangle {v-1, v, v+1} has nonzero area.
2) Find the vertex with the minimum x coord (done at the same time as step 1)
3) Find the winding (clockwise or counter-clockwise) of the triangle at (minimum x coord). This establishes the overall winding of the polygon.
4) For each vertex, iterating backwards: (for performance)
- If the triangle at current vertex {v-1,v,v+1} has the same winding as the polygon winding (found in step 3), then:
.......... Check if any other vertex is inside this triangle. If not, then output the triangle and erase current vertex from the set.
5) Continue until all triangles have been formed

I'm choosing to store the vertices using a vector, so it takes linear time to erase elements. But iterating backwards means that elements are extremely likely to be removed from the end first, which will be much faster than say, removing from a link list. In fact, I'm hoping that the simplicity of the solution (no dynamic memory management during) will result in it running faster than the O(n log n) algorithms for the majority of input. The vast majority of surfaces in CAD have only 4 vertices in the plane after all.

You can find an implementation of an O(n*log(n)) algorithm here.