Scattered set of 2D vertices to triangle strip

Question

I need to draw a convex polygon, given by 6 unordered vertices.

The drawing should be done using GL_TRIANGLE_STRIP, and two of the vertices are given to me at the first and last vertices.

How can I re-order the vertices efficiently so I can draw the polygon with OpenGL and GL_TRIANGLE_STRIP?

Answer 1

Separate all vertices using the line from the first vertex to the last one. There should be equally many on both sides. If not, the polygon is either not convex or the given start and end vertex are wrong.

Sort both sets by dot(lineDirection, vertex - firstVertex). This effectively projects the vertices on the line. Then start at the start vertex and alternate between two sets in the given order.