# polygon triangulation

## Recommended Posts

taurean    122
I am looking for some simple code that deals with convex/concave/polygon with holes triangulation. I would like to simulate the stuff done by GLU's gluNewTess for my simulation environment. although, I find a lot for 2D, I am not able to find a neat one for 3D polygon triangulation. Also, I am not able to compare the existing ones. Could some one throw light onto my needs. ~ Matt

##### Share on other sites
Premandrake    175
Edit: Ah, I assumed you were looking to do triangulation of planar polygons, which appears to not be the case. Ah well, I'll leave this up here in case anyone finds it useful. I should read more carefully next time :).

There are a whole bunch of ways to do tesselation with holes, I'll present a relatively straight-forward and somewhat robust method.

First the easy part: triangulation of concave polygons. You can use a very simple method that goes like this (in pseudo-code):
Vertex FindConvexVertex(Polygon P) { // Two methods: // (1) Find the left-most vertex in the polygon, breaking ties by Y value. // (2) Find a vertex that makes a right turn}Vertex FindIntrudingVertex(Polygon P, Vertex vertex) { // What we are looking for here is a vertex that intrudes on the triangle formed // by the vertex (A) it's next neighbor (B) and it's previous neighbor (C). // So for example: //         A---------------------B //        /        __________---- //       /   #----- //      /     \ //     C-------* // The vertex marked # is an intruding vertex, and * is not.  Note that you will only // find intruding vertices in concave polygons. // // The method we can use for finding an intruding vertex is to find any points that lie // within the triangle formed  by ABC.  If there are multiple points, we want the one // that is furthest from the BC edge. Triangle ABC = Triangle(vertex, vertex.Next, vertex.Prev); Vertex best = null; foreach (vertex in P) {  if (vertex in ABC) {   if (best == null) best = vertex;    else if (vertex is further from BC than best) best = vertex;  } } // best can still be null here, that's fine return best;}Polygon Split(Vertex first, Vertex last) { // We want to return a polygon representing the polygon between the vertices first and last // So for example: //       A------B //      /        \ //     /          \ //    F            C //     \          / //      \        / //       E------D // // Given A as first and C as last, we return ABC.  Give C as first and A as last we return CDEFA. // Give C as first and F as last wer turn CDEF, etc. // Note that this is dependent on the winding order of your polygons. return Polygon(from first to last);}List<Triangle> Triangulate(Polygon P) { if (P has 3 vertices) return Triangle(P); Vertex convex = FindConvexVertex(P); Vertex intruding = FindIntrudingVertex(P, convex); if (intruding == null) {  // If there is no intruding vertex, we can split the convex vertex and it's two neigbors into  // a seperate triangle and continue onwards.  return Join(Triangulate(Split(convex.Prev, convex.Next)),              Triangulate(Split(convex.Next, convex.PreV))); } else {  // Otherwise we split the polygon along the intruding vertex, knowing eventually we will end up  // with a convex polygon we can partition into triangles.  return Join(Triangulate(Split(convex, intruding)),              Triangulate(Split(intruding, convex))); }}

Okay, so that's maybe not so simple :). It would have been much nicer to have images to demonstrate concepts there, but I hope the ascii art is useful.

The basic concept is to find a convex vertex, then using that vertex and the triangle formed by it's two edges, check for an intruding vertex (a vertex within the triangle). If you find an intruding vertex, split the polygon along the convex and intruding vertex and recursively triangle the two polygon halves. If there is no intruding vertex you can split off the convex vertex and it's two edges into a triangle and continue triangulating the rest.

##### Share on other sites
taurean    122
I still don't get you clearly. Is there any supporting text so that I could understand your pseudo-code well ?. Have you looked onto gluNewTess () ?

~ Matt

##### Share on other sites
Premandrake    175
I don't know off the top of my head where the algorithm I explained would be found in textbook form. And the reason you are not understanding is because I misunderstood your question and posted a response that is only useful for triangulation of 2D polygons (or planar 3d polygons). I didn't cover handling holes because I realized you wanted something different than what I was providing.