cdt.cpp

这是个生成约束delaunay triangulations源程序。对学习约束delaunay triangulations很有帮助！

#endif
   
   l=ls->l;
   m=ls->r;
   r=rs->r;

   ms=new Slab(l,r);

   //repeat merging
   while   (ls->q_head!=NULL
      ||   rs->q_head!=NULL)
   {
      //in this loop, all the quads above ls->q_head and rs->q_head has no intersection with these two
      
      //ls has no quad, just update ms with rs->q_head,then delete rs->q_head
      if   (ls->q_head==NULL)
      {
         //forward rs
         tmpq=rs->q_head;
         newq=new Quad(tmpq->top_v,tmpq->btm_v,tmpq->top_he,tmpq->btm_he,l,r);
         newq->top_y=tmpq->top_y;
         newq->btm_y=tmpq->btm_y;

         newq->computeCornorY(sep_array[l],sep_array[r]);

         ms->pushBackQuad(newq);

         rs->q_head=tmpq->next;
         delete tmpq;
      }
      else
      if   (rs->q_head==NULL)
      {
         //forward ls
         tmpq=ls->q_head;
         newq=new Quad(tmpq->top_v,tmpq->btm_v,tmpq->top_he,tmpq->btm_he,l,r);
         newq->top_y=tmpq->top_y;
         newq->btm_y=tmpq->btm_y;

         newq->computeCornorY(sep_array[l],sep_array[r]);

         ms->pushBackQuad(newq);

         ls->q_head=tmpq->next;
         delete tmpq;
      }
      else
      {
         WPointer w;
         bool   lgr;// left quad is above right quad
         w=getWindow(ls->q_head,rs->q_head,lgr);
         if   (w==NULL)
         {
            if   (lgr)
            {
               //forward ls
               tmpq=ls->q_head;
               newq=new Quad(tmpq->top_v,tmpq->btm_v,tmpq->top_he,tmpq->btm_he,l,r);
               newq->top_y=tmpq->top_y;
               newq->btm_y=tmpq->btm_y;

            newq->computeCornorY(sep_array[l],sep_array[r]);

               ms->pushBackQuad(newq);

               ls->q_head=tmpq->next;
               delete tmpq;

            }
            else
            {
               //forward rs
               tmpq=rs->q_head;
               newq=new Quad(tmpq->top_v,tmpq->btm_v,tmpq->top_he,tmpq->btm_he,l,r);
               newq->top_y=tmpq->top_y;
               newq->btm_y=tmpq->btm_y;

            newq->computeCornorY(sep_array[l],sep_array[r]);

               ms->pushBackQuad(newq);

               rs->q_head=tmpq->next;
               delete tmpq;

            }
         }
         else   
         {

            // they dont have to share top_he
            QPointer lq;
            QPointer rq;

            lq=ls->q_head;
            rq=rs->q_head;

            newq=new Quad();
            newq->l=l;
            newq->r=r;
            
            bool lwin;
            switch   (w->upsign)
            {
            case   -1:   
               newq->top_he=lq->top_he;
               newq->top_v=lq->top_v;
               newq->top_y=lq->top_y;
               break;
            case   0:
               newq->top_he=lq->top_he;
               lwin=lq->top_v->pos.y>rq->top_v->pos.y;
               if (lwin)
               {
                  newq->top_v=lq->top_v;
                  newq->top_y=lq->top_y;
               }
               else
               {
                  newq->top_v=rq->top_v;
                  newq->top_y=rq->top_y;
               }
               break;
            case   1:
               newq->top_he=rq->top_he;
               newq->top_v=rq->top_v;
               newq->top_y=rq->top_y;
               break;
            default:break;
            }
            //top_y is relative to top_v

            while   (w!=NULL)
            {
               // repeat until we find the bottom of this composite quad

               //triangulate window
               buildCDTOfWindow(w);

               if   (w->downsign==0)
               {
                  lq=ls->q_head;
                  rq=rs->q_head;

                  newq->btm_he=lq->btm_he;

                  bool rwin=lq->btm_v->pos.y>rq->btm_v->pos.y;
                  if (rwin)
                  {
                     newq->btm_v=rq->btm_v;
                     newq->btm_y=rq->btm_y;
                  }
                  else
                  {
                     newq->btm_v=lq->btm_v;
                     newq->btm_y=lq->btm_y;
                  }

                  //forward rs
                  tmpq=rs->q_head;
                  rs->q_head=tmpq->next;
                  delete tmpq;

                  //forward ls
                  tmpq=ls->q_head;
                  ls->q_head=tmpq->next;
                  delete tmpq;

                  w=NULL;
               }
               else
               {
                  if   (w->downsign==-1)
                  {
                     newq->btm_he=rs->q_head->btm_he;
                     newq->btm_v=rs->q_head->btm_v;
                     newq->btm_y=rs->q_head->btm_y;
                     //forward ls
                     tmpq=ls->q_head;
                     ls->q_head=tmpq->next;
                     delete tmpq;
                     if   (ls->q_head==NULL)
                     {
                        tmpq=rs->q_head;
                        rs->q_head=tmpq->next;
                        delete tmpq;
                        w=NULL;
                     }
                     else
                     {
                        w=getWindow(ls->q_head,rs->q_head,lgr);
                        if   (w==NULL)
                        {
                           tmpq=rs->q_head;
                           rs->q_head=tmpq->next;
                           delete tmpq;
                        }
                     }
                  }
                  else
                  {
                     newq->btm_he=ls->q_head->btm_he;
                     newq->btm_v=ls->q_head->btm_v;
                     newq->btm_y=ls->q_head->btm_y;
                     //forward rs
                     tmpq=rs->q_head;
                     rs->q_head=tmpq->next;
                     delete tmpq;
                     if   (rs->q_head==NULL)
                     {
                        tmpq=ls->q_head;
                        ls->q_head=tmpq->next;
                        delete tmpq;
                        w=NULL;
                     }
                     else
                     {
                        w=getWindow(ls->q_head,rs->q_head,lgr);
                        if   (w==NULL)
                        {
                           tmpq=ls->q_head;
                           ls->q_head=tmpq->next;
                           delete tmpq;
                        }
                     }
                  }
               }
            }
            newq->computeCornorY(sep_array[l],sep_array[r]);

            ms->pushBackQuad(newq);
         }
         //in this loop, all the quads above ls->q_head and rs->q_head has no intersection with these two
      }
   }
   //copy ms to ls
   ls->r=ms->r;
   ls->q_head=ms->q_head;
   ls->q_tail=ms->q_tail;
   //delete ms
   delete ms;
   //for
   ls->next=rs->next;
   //delete rs
   delete   rs;
}

/* return 0 means no error*/
int   Mesh::mergeSlabs()
{

   SPointer   tmps;
   // merge the list until there is only one slab 
#ifdef   OUTPUT
         printf("\nCurrent slab list:\n");
         printSlab(s_head);
#endif
   while   (s_head->next!=NULL)
   {
      tmps=s_head;
      // one scan of list, merging each two consecutive slabs
      while(tmps!=NULL   && tmps->next!=NULL)
      {
         mergeSlabPair(tmps);
         // now the ts is already the merged slab
         tmps=tmps->next;

#ifdef   OUTPUT
         printf("\nCurrent slab list:\n");
         printSlab(s_head);
#endif
      }
   }   

#ifdef   OUTPUT
         printf("\n The final slab:\n");
         printSlab(s_head);
         printf("\n");
#endif
   //...
   return 0;
}

/* return 0 means no error*/
int   Mesh::buildCDT()
{
   initSlabs();
   return mergeSlabs();
}

MeshPointer   Mesh::copy()
{
   MeshPointer m=new Mesh();
   m->maxs.x=maxs.x;
   m->maxs.y=maxs.y;
   m->mins.x=mins.x;
   m->mins.y=mins.y;

   if   (vlt!=NULL)
   {
      m->vlt=new Vertex(mins.x-3*OFFSET,maxs.y+OFFSET,-2);
      m->vlb=new Vertex(mins.x-2*OFFSET,mins.y-OFFSET,-1);

      //index is v_num+1,v_num
      m->vrt=new Vertex(maxs.x+3*OFFSET,maxs.y+OFFSET,v_num+1);
      m->vrb=new Vertex(maxs.x+2*OFFSET,mins.y-OFFSET,v_num);

      // 2 long horizontal lines
      sky_e=addEdge(vlt,vrt,VIRTUAL);
      eth_e=addEdge(vlb,vrb,VIRTUAL);
   }

   m->v_num=this->v_num;
   m->v_array=new VPointer[v_num];
   for   (int vi=0;vi<v_num;vi++)
   {
      m->v_array[vi]=new   Vertex(this->v_array[vi]->pos.x,this->v_array[vi]->pos.y,vi);
   }

   if   (sep_array!=NULL)
   {
      m->sep_array=new double[v_num+1];
      for   (int si=0;si<v_num;si++)
      {
         m->sep_array[si]=this->sep_array[si];
      }
      m->sep_array[v_num]=sep_array[v_num];
   }


   EListPointer   el;
   int   i1,i2;
   el=e_head;
   while   (el!=NULL)
   {
      if   (el->e->type!=VIRTUAL)
      {
         i1=el->e->he[1]->v->getIndex();
         i2=el->e->he[0]->v->getIndex();
         m->addEdge(m->v_array[i1],m->v_array[i2],el->e->type);
      }
      el=el->next;
   }
   return   m;
}

Mesh mesh;
Mesh*   oldMesh;

double   maxx,maxy,minx,miny;
double   ratio;

void   olddisplay(){
   glClear(GL_COLOR_BUFFER_BIT);
   glLoadIdentity();

   gluOrtho2D(minx,maxx,miny,maxy);

   /*
   //display
   SPointer   tmps;
   while   (mesh.s_head->next!=NULL)
   {
      tmps=mesh.s_head;
      // one scan of list, merging each two consecutive slabs
      while(tmps!=NULL   && tmps->next!=NULL)
      {
         mesh.mergeSlabPair(tmps);
         // now the ts is already the merged slab
         tmps=tmps->next;
         mesh.display();
      }
   }
   */
   oldMesh->display();
   glFlush();
}

void   display(){
   glClear(GL_COLOR_BUFFER_BIT);
   glLoadIdentity();

   gluOrtho2D(minx,maxx,miny,maxy);

   /*
   //display
   SPointer   tmps;
   while   (mesh.s_head->next!=NULL)
   {
      tmps=mesh.s_head;
      // one scan of list, merging each two consecutive slabs
      while(tmps!=NULL   && tmps->next!=NULL)
      {
         mesh.mergeSlabPair(tmps);
         // now the ts is already the merged slab
         tmps=tmps->next;
         mesh.display();
      }
   }
   */
   mesh.display();
   glFlush();
}

void   reshape(int w,int h)
{
//      glViewport(0,-hh+h/2,(GLsizei)w,hh+h/2);
      if   (ratio<h/w)
      {
         GLsizei hh=(int)(w*ratio/2);
         glViewport(0, (GLsizei)h/2-hh, w, (GLsizei)h/2+hh); /* Set Viewport */
      }
      else
      {
         GLsizei ww=(int)(h/ratio/2);
         glViewport((GLsizei)w/2-ww, 0, (GLsizei)w/2+ww, h); /* Set Viewport */
      }

}

void   init(void)
{ glClearColor(.0,.0,.0,1.0);
   glShadeModel(GL_FLAT);

   maxx=mesh.maxs.x;
   maxy=mesh.maxs.y;
   minx=mesh.mins.x;
   miny=mesh.mins.y;

   ratio=(maxy-miny)/(maxx-minx);

   double cx,cy;
   cx=(maxx+minx)/2;
   cy=(maxy+miny)/2;

   double s=1.2;
   maxx=cx+(maxx-cx)*s;
   minx=cx+(minx-cx)*s;
   maxy=cy+(maxy-cy)*s;
   miny=cy+(miny-cy)*s;
}

//main program
int   main(int argc,char* argv[]){
   if   (argc   <2 || argc >3)
   {
      printf("Usage: ./cdt.exe source_file_name [destine_file_name]\n");
      return(-1);
   }
   else
   {
      int   value=mesh.import2OFFFile(argv[1]);


      if   (value==0)
      {
         oldMesh=mesh.copy();
         glutInit(&argc,argv);
         glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
         glutInitWindowSize(250,250);
         glutInitWindowPosition(100,100);
         glutCreateWindow("Before Triangluated");
         init();
         glutDisplayFunc(olddisplay);
//         glutReshapeFunc(reshape);
//         glutMainLoop();

         mesh.buildCDT();
         if (argc==2)
         {
   //         writeResult(argv[1],NULL);
            mesh.export2OFFFile(argv[1],NULL);
         }
         else
         {
   //            writeResult(argv[1],argv[2]);
            mesh.export2OFFFile(argv[1],argv[2]);
         }
//         glutInit(&argc,argv);
//         glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
         glutInitWindowSize(250,250);
         glutInitWindowPosition(400,100);
         glutCreateWindow("After Triangluated");
//         init();
         glutDisplayFunc(display);
//         glutReshapeFunc(reshape);
         glutMainLoop();
      }
   }
   return 1;
}