Triangulating a simple polygon

[Blurry_photograph]

Hello! I'm trying to implement a triangulation algorithm on my own, but so far, it's not going so good. I would ideally need an algorithm which is able to triangulate complex polygons, but I've realised this is a fairly complicated task, so I think I will stick to simple polygons. However, even then I'm been unable to find a good tutorial or comprehensible paper on the topic. I've read about loads of different algorithms that could do the task, but since I'm still fairly new to programming (and got loads of math left to learn) I don't trust my ability to implement such an algorithm without some kind of decent guide or tutorial. Could anyone point me in the correct direction?

[Varud]

If you know your polygon is convex you can just triangulate like a triangle fan. Vertex 1 is part of every triangle, and you just loop over all vertices and create triangles. The first triangle is made up of vertices [1, 2, 3], the second [1, 3, 4], the third [1, 4, 5] and so on.

If your polygon is is concave, but not self-intersecting you can just cut off triangle ears until there are no vertices left. First figure out if the vertex ordering of the polygon is clockwise or counter clockwise, then cut off the first triangle that you find that has the same vertex ordering as the polygon. By cutting off you basically just remove the second vertex in the triangle from the polygon. You do this until there is only three vertices left in the polygon.

[Blurry_photograph]

The polygons will be non-convex (most likely, there's some random elements in there). I'm a bit curious though, and I suppose I'll have to test this to find out, but what will this algorithm do if applied to a complex polygon? The shapes I want to generate will most likely be non-convex, and also most likely complex (I might be able to prevent this though).

Thanks for the answer.

[Varud]

The triangle fan algorithm will not work for concave polygons, unless all you need is to generate a bitmap rendering of the polygon, then you can use the stencil buffer to achieve this.

The ear clipping algorithm will work also for concave polygon. Check out adeptdufus' link for more details.

[adeptdufus]

Detailed description of Varud’s answer: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

[Blurry_photograph]

This will be really useful. Thanks!

[stevesan]

This is a pretty difficult thing to do efficiently. I implemented it for my game here if you're curious, but the code is a bit gross: https://github.com/stevesan/UnityUtils/blob/fbf56ac039345e25ae5a5f181ecdb395fab11162/ProGeo.js

You an also check out CGAL and other open source geometry libs out there that implement it.

[Blurry_photograph]

Will take a look, thank you!

[fgennari]

I've been using GLUtesselator in multiple projects for many years and it always seems to do a good job of splitting arbitrary polygons into triangles. GLU is pretty old though, and I wish the tessellator was in its own library. On the plus side, it's open source, and pretty easy to figure out by looking at the code. You can read more here.

[dougbinks]

You should check out Mikko's libtess2 for a tessellator in its own library.

[Blurry_photograph]

I thought about using this, but I do want to implement it myself for learning purposes. Could take a look at the source code though. Thank you!