In 2D and without holes, this is fairly easy. First, you need to break your polygon to one or more monotone polygons.
The monotone polygons are pretty simple to turn into tristrips, just sort the values by y, find the top-most and bottom-most vertex, and then you have lists of vertices to the right and to the left (because vertices come in some defined, say clockwise, order). Then you start with top-most vertex and add vertices from the left and from the right sides in alternating manner.
This technique will work for any 2D polygons without self-intersecting edges, which includes some cases of polygons with holes (the holes must be correctly wound though).
You can try and play with this code:
glMatrixMode(GL_PROJECTION);
glLoadIdentity();
glMatrixMode(GL_MODELVIEW);
glLoadIdentity();
glTranslatef(-.5f, -.5f, 0);
std::vector<Vector2f> my_polygon;
my_polygon.push_back(Vector2f(-0.300475f, 0.862924f));
my_polygon.push_back(Vector2f(0.302850f, 1.265013f));
my_polygon.push_back(Vector2f(0.811164f, 1.437337f));
my_polygon.push_back(Vector2f(1.001188f, 1.071802f));
my_polygon.push_back(Vector2f(0.692399f, 0.936031f));
my_polygon.push_back(Vector2f(0.934679f, 0.622715f));
my_polygon.push_back(Vector2f(0.644893f, 0.408616f));
my_polygon.push_back(Vector2f(0.592637f, 0.753264f));
my_polygon.push_back(Vector2f(0.269596f, 0.278068f));
my_polygon.push_back(Vector2f(0.996437f, -0.092689f));
my_polygon.push_back(Vector2f(0.735154f, -0.338120f));
my_polygon.push_back(Vector2f(0.112827f, 0.079634f));
my_polygon.push_back(Vector2f(-0.167458f, 0.330287f));
my_polygon.push_back(Vector2f(0.008314f, 0.664491f));
my_polygon.push_back(Vector2f(0.393112f, 1.040470f));
// from wiki (http://en.wikipedia.org/wiki/File:Polygon-to-monotone.png)
glEnable(GL_POINT_SMOOTH);
glEnable(GL_LINE_SMOOTH);
glEnable(GL_BLEND);
glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA);
glLineWidth(6);
glColor3f(1, 1, 1);
glBegin(GL_LINE_LOOP);
for(size_t i = 0, n = my_polygon.size(); i < n; ++ i)
glVertex2f(my_polygon[i].x, my_polygon[i].y);
glEnd();
glPointSize(6);
glBegin(GL_POINTS);
for(size_t i = 0, n = my_polygon.size(); i < n; ++ i)
glVertex2f(my_polygon[i].x, my_polygon[i].y);
glEnd();
// draw the original polygon
std::vector<int> working_set;
for(size_t i = 0, n = my_polygon.size(); i < n; ++ i)
working_set.push_back(i);
_ASSERTE(working_set.size() == my_polygon.size());
// add vertex indices to the list (could be done using iota)
std::list<std::vector<int> > monotone_poly_list;
// list of monotone polygons (the output)
glPointSize(14);
glLineWidth(4);
// prepare to draw split points and slice lines
for(;;) {
std::vector<int> sorted_vertex_list;
{
for(size_t i = 0, n = working_set.size(); i < n; ++ i)
sorted_vertex_list.push_back(i);
_ASSERTE(working_set.size() == working_set.size());
// add vertex indices to the list (could be done using iota)
for(;;) {
bool b_change = false;
for(size_t i = 1, n = sorted_vertex_list.size(); i < n; ++ i) {
int a = sorted_vertex_list[i - 1];
int b = sorted_vertex_list[i];
if(my_polygon[working_set[a]].y < my_polygon[working_set[b]].y) {
std::swap(sorted_vertex_list[i - 1], sorted_vertex_list[i]);
b_change = true;
}
}
if(!b_change)
break;
}
// sort vertex indices by the y coordinate
// (note this is using bubblesort to maintain portability
// but it should be done using a better sorting method)
}
// build sorted vertex list
bool b_change = false;
for(size_t i = 0, n = sorted_vertex_list.size(), m = working_set.size(); i < n; ++ i) {
int n_ith = sorted_vertex_list[i];
Vector2f ith = my_polygon[working_set[n_ith]];
Vector2f prev = my_polygon[working_set[(n_ith + m - 1) % m]];
Vector2f next = my_polygon[working_set[(n_ith + 1) % m]];
// get point in the list, and get it's neighbours
// (neighbours are not in sorted list ordering
// but in the original polygon order)
float sidePrev = sign(ith.y - prev.y);
float sideNext = sign(ith.y - next.y);
// calculate which side they lie on
// (sign function gives -1 for negative and 1 for positive argument)
if(sidePrev * sideNext >= 0) { // if they are both on the same side
glColor3f(1, 0, 0);
glBegin(GL_POINTS);
glVertex2f(ith.x, ith.y);
glEnd();
// marks points whose neighbours are both on the same side (split points)
int n_next = -1;
if(sidePrev + sideNext > 0) {
if(i > 0)
n_next = sorted_vertex_list[i - 1];
// get the next vertex above it
} else {
if(i + 1 < n)
n_next = sorted_vertex_list[i + 1];
// get the next vertex below it
}
// this is kind of simplistic, one needs to check if
// a line between n_ith and n_next doesn't exit the polygon
// (but that doesn't happen in the example)
if(n_next != -1) {
glColor3f(0, 1, 0);
glBegin(GL_POINTS);
glVertex2f(my_polygon[working_set[n_next]].x, my_polygon[working_set[n_next]].y);
glEnd();
glBegin(GL_LINES);
glVertex2f(ith.x, ith.y);
glVertex2f(my_polygon[working_set[n_next]].x, my_polygon[working_set[n_next]].y);
glEnd();
std::vector<int> poly, remove_list;
int n_last = n_ith;
if(n_last > n_next)
std::swap(n_last, n_next);
int idx = n_next;
poly.push_back(working_set[idx]); // add n_next
for(idx = (idx + 1) % m; idx != n_last; idx = (idx + 1) % m) {
poly.push_back(working_set[idx]);
// add it to the polygon
remove_list.push_back(idx);
// mark this vertex to be erased from the working set
}
poly.push_back(working_set[idx]); // add n_ith
// build a new monotone polygon by cutting the original one
std::sort(remove_list.begin(), remove_list.end());
for(size_t i = remove_list.size(); i > 0; -- i) {
int n_which = remove_list[i - 1];
working_set.erase(working_set.begin() + n_which);
}
// sort indices of vertices to be removed and remove them
// from the working set (have to do it in reverse order)
monotone_poly_list.push_back(poly);
// add it to the list
b_change = true;
break;
// the polygon was sliced, restart the algorithm, regenerate sorted list and slice again
}
}
}
if(!b_change)
break;
// no moves
}
if(!working_set.empty())
monotone_poly_list.push_back(working_set);
// use the remaining vertices (which the algorithm was unable to slice) as the last polygon
std::list<std::vector<int> >::const_iterator p_mono_poly = monotone_poly_list.begin();
for(; p_mono_poly != monotone_poly_list.end(); ++ p_mono_poly) {
const std::vector<int> &r_mono_poly = *p_mono_poly;
glLineWidth(2);
glColor3f(0, 0, 1);
glBegin(GL_LINE_LOOP);
for(size_t i = 0, n = r_mono_poly.size(); i < n; ++ i)
glVertex2f(my_polygon[r_mono_poly[i]].x, my_polygon[r_mono_poly[i]].y);
glEnd();
glPointSize(2);
glBegin(GL_POINTS);
for(size_t i = 0, n = r_mono_poly.size(); i < n; ++ i)
glVertex2f(my_polygon[r_mono_poly[i]].x, my_polygon[r_mono_poly[i]].y);
glEnd();
// draw the sliced part of the polygon
int n_top = 0;
for(size_t i = 0, n = r_mono_poly.size(); i < n; ++ i) {
if(my_polygon[r_mono_poly[i]].y < my_polygon[r_mono_poly[n_top]].y)
n_top = i;
}
// find the top-most point
glLineWidth(1);
glColor3f(0, 1, 0);
glBegin(GL_LINE_STRIP);
glVertex2f(my_polygon[r_mono_poly[n_top]].x, my_polygon[r_mono_poly[n_top]].y);
for(size_t i = 1, n = r_mono_poly.size(); i <= n; ++ i) {
int n_which = (n_top + ((i & 1)? n - i / 2 : i / 2)) % n;
glVertex2f(my_polygon[r_mono_poly[n_which]].x, my_polygon[r_mono_poly[n_which]].y);
}
glEnd();
// draw as if triangle strip
}
This code is not optimal, but it should be easy to understand. At the beginnig, a concave polygon is created. Then a "working set" of vertices is created. On that working set, a permutation is calculated which sorts the vertices by their y coordinate. That permutation is then looped through, looking for split points. Once a split point is found, a new monotone polygon is created. Then, the vertices used in the new polygon are removed from the working set and the whole process repeats. Finally, the working set contains the last polygon which could not be split. At the end, the monotone polygons are rendered, along with triangle strip ordering. It is a little bit messy, but I'm sure you will figure it out (this is C++ code, just put it inside a GLUT window and see what it does).
Hope this helps ...
