The AlgorithmThere are many different ways to decompose polygons into triangles. Typically though you only implement an algorithm that's advanced enough to suit your needs. For example, convex polygons are easier to triangulate than concave ones, and polygons with a hole in the middle of it are a little complicated to get right (and are also beyond the scope of this article: I'll be covering ear clipping at the most in this article. Maybe for another article). If you know that you'll only ever be using convex polygons, then only implement the algorithm for convex polygon triangulation. No need to go overboard :)
For Convex PolygonsThis one is by far the easiest. A convex polygon is one where there are no interior angles greater than 180 degrees in the polygon. For this case, you can pick any vertex in the polygon and create a triangle fan outward. Pretty simple:
create a stack with all of the vertecies in CW/CCW order; pop the top vertex off the stack and store in p0; pop the top vertex off the stack and store in pHelper; while the stack is not empty pop the top vertex off the stack and store in pTemp; create a triangle with vertices p0, pHelper, pTemp; let pHelper = pTempThe created triangle soup will be a complete triangulation of the polygon, but it only works with convex polygons!
For Concave PolygonsA concave polygon is a polygon that has at least one interior angle greater than 180 degrees. This also means that, for any concave polygon, there is at least one line that you can draw that will intersect the polygon at least 4 times.
create a list of the vertices (perferably in CCW order, starting anywhere) while true for every vertex let pPrev = the previous vertex in the list let pCur = the current vertex; let pNext = the next vertex in the list if the vertex is not an interior vertex (the wedge product of (pPrev - pCur) and (pNext - pCur) <= 0, for CCW winding); continue; if there are any vertices in the polygon inside the triangle made by the current vertex and the two adjacent ones continue; create the triangle with the points pPrev, pCur, pNext, for a CCW triangle; remove pCur from the list; if no triangles were made in the above for loop break;