# Polygonal Triangulation - algorithm with O(n log n) complexity

I wish to triangulate a polygon I only have the outline of (p0, p1, p2 ... pn) like described in this question: How do you triangulate an arbitrary polygon? and this webpage: http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html

I do not wish to learn the subject and have a deep understanding of it at the moment. I only want to see an effective algorithm that can be used out of the box. The one described in the site seems to be of somewhat high complexity O(n) for finding one ear. I heard this could be done in O(n log n) time. Is there any well known easy to use algorithm that I can translate port to use in my engine that runs with somewhat reasonable complexity?

The reason I need to triangulate is that I wish to feel out a 2d-outline and render it 3d. Much like we fill out a 2d-outline in paint. I could use sprites. This would not serve cause I am planning to play with the resulting model on the z-axis, giving it different heights in the different areas.

I would love to try the books that were mentioned, although I suspect that is not the answer most readers are hoping for when they read this Q & A format. Mostly I like to see a code snippet I can cut and paste with some modifications and start running.

Not sure if this is the answer you seek, since you mention 3D. But I used Poly2Tri once to convert parametric curved shapes to triangles and it worked fine. I'm saying this because you need an easy implementation, and using this library I did it in an afternoon.

Farseer physics have the implementation of 5 different decomposers, which two of them decompose it in triangles. You can check them here http://farseerphysics.codeplex.com/SourceControl/changeset/view/99885#1436514

They're under the folder

>SourceFiles
>Common
>Decomposition

• I will look there and update you when I get more work done. – AturSams Oct 14 '12 at 21:30

I have actually implemented it myself with a simple scanline algorithm. It doesnt grant the best results, but its good enough for me. From what I remember:

1. You just have to sort your vertices along the X.

2. Create column spans with the ordered vertices (thus, making it monotone polygons).

3. And finally, find the diagonals lines connecting the vertices along the spans.

Is it clear?

EDIT: Please dont mind the mess: http://code.google.com/p/bzk3/source/browse/#svn%2Ftrunk%2Fsource%2Fcommon%2Fsrc%2Fbr%2Fodb%2Flibsvg (look for it at svn/trunk/source/common/src/br/odb/libsvg/)

In fact, I used to provide a standalone runnable jar just for that. More details at: https://sites.google.com/site/montysprojects/current-projects/svgtriangulator

• Yes you can and should :P – Gustavo Maciel Oct 15 '12 at 23:36
• Edit the answer and put the links in there, it will be easier to spot them :D – Gustavo Maciel Oct 16 '12 at 4:52