monoPolyPart.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions
directedLine *	monoPolyPart (directedLine *polygon)

Function Documentation

monoPolyPart()

directedLine* monoPolyPart

(

directedLine *

polygon

)

Definition at line 80 of file monoPolyPart.cc.

{
  //handle special cases:
  if(polygon == NULL)
    return NULL;
  if(polygon->getPrev() == polygon)
    return polygon;
  if(polygon->getPrev() == polygon->getNext())
    return polygon;
  if(polygon->getPrev()->getPrev() == polygon->getNext())
    return polygon;

  //find the top and bottom vertexes
  directedLine *tempV, *topV, *botV;
  topV = botV = polygon;
  for(tempV = polygon->getNext(); tempV != polygon; tempV = tempV->getNext())
    {
      if(compV2InY(topV->head(), tempV->head())<0) {
    topV = tempV;
      }
      if(compV2InY(botV->head(), tempV->head())>0) {
    botV = tempV;
      }
    }

  //initilization
  directedLine *A, *B, *C, *D, *G, *H;
  //find A:the first u_maximal vertex on the left chain
  //and C: the left most vertex between top and A
  A = NULL;
  C = topV;
  for(tempV=topV->getNext(); tempV != botV; tempV = tempV->getNext())
    {
      if(tempV->head()[0] < C->head()[0])
    C = tempV;

      if(is_u_maximal(tempV))
    {
      A = tempV;
      break;
    }
    }
  if(A == NULL)
    {
      A = botV;
      if(A->head()[0] < C->head()[0])
    C = A;
    }
      
  //find B: the first u_minimal vertex on the right chain
  //and  D: the right most vertex between top and B
  B = NULL;
  D = topV;
  for(tempV=topV->getPrev(); tempV != botV; tempV = tempV->getPrev())
    {
      if(tempV->head()[0] > D->head()[0])
    D = tempV;
      if(is_u_minimal(tempV))
    {
      B = tempV;
      break;
    }
    }
  if(B == NULL)
    {
      B = botV;
      if(B->head()[0] > D->head()[0])
    D = B;
    }

  //error checking XXX
  if(C->head()[0] >= D->head()[0])
    return polygon;

  //find G on the left chain that is right above B
  for(tempV=topV; compV2InY(tempV->head(), B->head()) == 1;  tempV=tempV->getNext());
  G = tempV->getPrev();
  //find H on the right chain that is right above A
  for(tempV=topV; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
  H = tempV->getNext();
  
  //Main Loop
  directedLine* ret = NULL;
  directedLine* currentPolygon = polygon;
  while(1)
    {
      //if both B and D are equal to botV, then this polygon is already 
      //u-monotone
      if(A == botV && B == botV)
    {
      ret = currentPolygon->insertPolygon(ret);
      return ret;
    }
      else //not u-monotone
    {
      directedLine *ret_p1, *ret_p2;
      if(compV2InY(A->head(),B->head()) == 1) //A is above B
        {
          directedLine* E = NULL;
          for(tempV = C; tempV != D; tempV = tempV->getPrev())
        {
          if(tempV->head()[0] >= A->head()[0])
            {
              E = tempV;
              break;
            }
        }

          if(E == NULL)
        E = D;
          if(E->head()[0]> H->head()[0])
        E = H;
          //connect AE and output polygon ECA
          polygon->connectDiagonal_2slines(A, E,
                           &ret_p1,
                           &ret_p2,
                           NULL);
          ret = ret_p2->insertPolygon(ret);
          currentPolygon = ret_p1;

          if(E == D)
        D = ret_p1;
          if(E == H)
        H = ret_p1;
              if(G->head()[1] >= A->head()[1])
        G = A;
          //update A to be the next u-maxiaml vertex on left chain
          //and C the leftmost vertex between the old A and the new A
          C = A;
          for(tempV = A->getNext(); tempV != botV; tempV = tempV->getNext())
        {

          if(tempV->head()[0] < C->head()[0])
            C = tempV;
          if(is_u_maximal(tempV))
            {
              A = tempV;
              break;
            }
        }

          if(tempV == botV)
        {
          A = botV;
          if(botV->head()[0] < C->head()[0])
            C = botV;
        }
          //update H

              if(A == botV)
        H = botV;
              else
        {
          for(tempV = H; compV2InY(tempV->head(), A->head()) == 1; tempV = tempV->getPrev());
          H = tempV->getNext();
        }

        }
      else //A is below B
        {

          directedLine* F = NULL;
          for(tempV = D; tempV != C; tempV = tempV->getNext())
        {
          if(tempV->head()[0] <= B->head()[0])
            {
              F = tempV;
              break;
            }
        }
          if(F == NULL)
        F = C;
          if(F->head()[0] < G->head()[0])
        F = G;

          //connect FB
          polygon->connectDiagonal_2slines(F, B, 
                           &ret_p1,
                           &ret_p2,
                           NULL);
          ret = ret_p2->insertPolygon(ret);
          currentPolygon = ret_p1;
          B = ret_p1;
          if(H ->head()[1] >= B->head()[1])
        H = ret_p1;

          //update B to be the next u-minimal vertex on right chain
          //and D the rightmost vertex between the old B and the new B
          D = B;
          for(tempV = B->getPrev(); tempV != botV; tempV = tempV->getPrev())
        {
          if(tempV->head()[0] > D->head()[0])
            D = tempV;
          if(is_u_minimal(tempV))
            {
              B = tempV;
              break;
            }
        }
          if(tempV == botV)
        {
          B = botV;
          if(botV->head()[0] > D->head()[0])
            D = botV;
        }
          //update G
              if(B == botV)
        G = botV; 
              else
        {
          for(tempV = G; compV2InY(tempV->head(), B->head()) == 1;  tempV = tempV->getNext());
          G = tempV->getPrev();
        }
        } //end of A is below B
    } //end not u-monotone  
    } //end of main loop
}

Referenced by monoTriangulationRecGenOpt().