Algorithm to convert vertices of a triangular strip to polygon

Question

I have an array with vertices representing a triangular strip. I need to convert it into polygon. There are many solution to do the reverse, but I failed to find one for the above problem. Or it could be too easy and I just cannot see it. Please help.

OpenGL=compatible, see http://en.wikipedia.org/wiki/Triangle_strip

Example: for this strip http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png I need output A B D F E C or A C E F D B

Answer 1

There may be a shortcut if your shape has a particularly simple structure, but in general I think you want to do the following

• Create a list of vertices and edges from your list of triangles. This involves detecting shared points (hopefully they are exact matches so you can find them by hashing instead of needing some sort of fuzzy search) and shared lines (that's easy--just don't draw two edges between the same pair of shared vertices).
• Find the upper-left-most point.
• Find the edge that travels as upper-left-most as possible, and is in the counterclockwise direction.
• Walk to the next vertex.
• Find the next edge that doubles back on the previous one as much as possible.
• Keep going until you hit the upper-left-most point again.

Answer 2

I believe the following should work:

Walk through the list of vertices. Add the first point to your polygon. Push the second point on the stack. Add the third point to the polygon. Continue alternating between pushing points on the stack and adding them to the polygon until you reach the end of the list. When you get to the end of the list, pop the points of the stack and add them to the polygon.

Answer 3

I'll assume your triangle strip is always connected the same way (which I believe is true for OpenGL).

• The "bottom" vertices are always two apart: A, C, E, ...
• The "top" vertices are always two apart: B, D, F, ...

Take the "bottom" list and append the reverse of the "top" list. (ACEFDB for the example)

---

Or, more directly, using a zero-based index instead of letters:

// do "bottom"
for ( i = 0; i < N; i += 2 )
  addVertex( i )

// do "top"
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2;
for ( i = largestOddNumberLessThanN; i >= 0; i -= 2 )
  addVertex( i )