# The Algorithm

There 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 Polygons

This 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 = pTemp
```

The created triangle soup will be a complete triangulation of the polygon, but it only works with convex polygons!
## For Concave Polygons

A 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;
```

## Polygons With Holes

Again, this one is beyond the scope of this article, but the general trick to solving this case is to decompose the polygon into a set of monotone polygons:# Conclusion

That's about it for most simple polygons you'll probably be creating in various art editors. For the most part, you shouldn't need any more than a concave polygon triangulator. On a more case-specific note, I actually did need a more advanced triangulator, complete with support for triangulating bezier curves and the like. In the end, though, I decided to go with tile-based worlds and rasterized graphics, as they tended to end up looking better anyways :P Well, the little thingy on the site says that I should write articles, no matter how trivial. In my defense, I know that I spent*much*more time than I should have needed to trying to figure out ear clipping. The same goes for monotone triangle decomposition, but that was just a matter of figuring out the state transitions. Anyway, hope someone finds this helpful.

## Create an account or sign in to comment

You need to be a member in order to leave a comment

## Create an account

Sign up for a new account in our community. It's easy!

Register a new account## Sign in

Already have an account? Sign in here.

Sign In Now