Trianguláció

Top  Previous  Next

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

}