src/glu/sgi/libnurbs/nurbtess/directedLine.cc

   1 /*
   2 ** License Applicability. Except to the extent portions of this file are
   3 ** made subject to an alternative license as permitted in the SGI Free
   4 ** Software License B, Version 1.1 (the "License"), the contents of this
   5 ** file are subject only to the provisions of the License. You may not use
   6 ** this file except in compliance with the License. You may obtain a copy
   7 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600
   8 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at:
   9 **
  10 ** http://oss.sgi.com/projects/FreeB
  11 **
  12 ** Note that, as provided in the License, the Software is distributed on an
  13 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS
  14 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND
  15 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A
  16 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT.
  17 **
  18 ** Original Code. The Original Code is: OpenGL Sample Implementation,
  19 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics,
  20 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc.
  21 ** Copyright in any portions created by third parties is as indicated
  22 ** elsewhere herein. All Rights Reserved.
  23 **
  24 ** Additional Notice Provisions: The application programming interfaces
  25 ** established by SGI in conjunction with the Original Code are The
  26 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released
  27 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version
  28 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X
  29 ** Window System(R) (Version 1.3), released October 19, 1998. This software
  30 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation
  31 ** published by SGI, but has not been independently verified as being
  32 ** compliant with the OpenGL(R) version 1.2.1 Specification.
  33 **
  34 */
  35 /*
  36 */
  37
  38 #include <stdlib.h>
  39 #include <stdio.h>
  40 #include <math.h>
  41 #include "glimports.h"
  42 #include "zlassert.h"
  43
  44 #include "quicksort.h"
  45 #include "directedLine.h"
  46 #include "polyDBG.h"
  47
  48 #ifdef __WATCOMC__
  49 #pragma warning 726 10
  50 #endif
  51
  52 //we must return the newLine
  53 directedLine* directedLine::deleteChain(directedLine* begin, directedLine* end)
  54 {
  55   if(begin->head()[0] ==  end->tail()[0] &&
  56      begin->head()[1] ==  end->tail()[1]
  57      )
  58     {
  59       directedLine *ret = begin->prev;
  60       begin->prev->next = end->next;
  61       end->next->prev = begin->prev;
  62       delete begin->sline;
  63       delete end->sline;
  64       delete begin;
  65       delete end;
  66
  67       return ret;
  68     }
  69
  70   directedLine* newLine;
  71   sampledLine* sline = new sampledLine(begin->head(), end->tail());
  72   newLine =  new directedLine(INCREASING, sline);
  73   directedLine *p = begin->prev;
  74   directedLine *n = end->next;
  75   p->next = newLine;
  76   n->prev = newLine;
  77   newLine->prev = p;
  78   newLine->next = n;
  79
  80   delete begin->sline;
  81   delete end->sline;
  82   delete begin;
  83   delete end;
  84   return newLine;
  85 }
  86
  87
  88 void directedLine::deleteSingleLine(directedLine* dline)
  89 {
  90   //make sure that dline->prev->tail is the same as
  91   //dline->next->head. This is for numerical erros.
  92   //for example, if we delete a line which is almost degeneate
  93   //within (epsilon), then we want to make that the polygon after deletion
  94   //is still a valid polygon
  95
  96   dline->next->head()[0] =  dline->prev->tail()[0];
  97   dline->next->head()[1] =  dline->prev->tail()[1];
  98
  99   dline->prev->next = dline->next;
 100   dline->next->prev = dline->prev;
 101
 102   delete dline;
 103
 104 }
 105
 106 static Int myequal(Real a[2], Real b[2])
 107 {
 108   /*
 109   if(a[0]==b[0] && a[1] == b[1])
 110     return 1;
 111   else
 112     return 0;
 113     */
 114
 115
 116   if(fabs(a[0]-b[0]) < 0.00001 &&
 117      fabs(a[1]-b[1]) < 0.00001)
 118     return 1;
 119   else
 120     return 0;
 121
 122 }
 123
 124 directedLine* directedLine::deleteDegenerateLines()
 125 {
 126   //if there is only one edge or two edges, don't do anything
 127   if(this->next == this)
 128     return this;
 129   if(this->next == this->prev)
 130     return this;
 131
 132   //find a nondegenerate line
 133   directedLine* temp;
 134   directedLine* first = NULL;
 135   if(! myequal(head(), tail()))
 136     /*
 137   if(head()[0] != tail()[0] ||
 138   head()[1] != tail()[1])
 139   */
 140     first = this;
 141   else
 142     {
 143       for(temp = this->next; temp != this; temp = temp->next)
 144         {
 145           /*
 146           if(temp->head()[0] != temp->tail()[0] ||
 147              temp->head()[1] != temp->tail()[1])
 148              */
 149           if(! myequal(temp->head(), temp->tail()))
 150             {
 151               first = temp;
 152               break;
 153             }
 154
 155         }
 156     }
 157
 158   //if there are no non-degenerate lines, then we simply return NULL.
 159   if(first == NULL)
 160     {
 161       deleteSinglePolygonWithSline();
 162       return NULL;
 163     }
 164
 165   directedLine* tempNext = NULL;
 166   for(temp =first->next; temp != first; temp = tempNext)
 167     {
 168       tempNext = temp->getNext();
 169 /*
 170       if(temp->head()[0] == temp->tail()[0] &&
 171          temp->head()[1] == temp->tail()[1])
 172 */
 173
 174       if(myequal(temp->head(), temp->tail()))
 175         deleteSingleLine(temp);
 176     }
 177   return first;
 178 }
 179
 180 directedLine* directedLine::deleteDegenerateLinesAllPolygons()
 181 {
 182   directedLine* temp;
 183   directedLine *tempNext = NULL;
 184   directedLine* ret= NULL;
 185   directedLine* retEnd = NULL;
 186   for(temp=this; temp != NULL; temp = tempNext)
 187     {
 188       tempNext = temp->nextPolygon;
 189       temp->nextPolygon = NULL;
 190       if(ret == NULL)
 191         {
 192           ret = retEnd = temp->deleteDegenerateLines();
 193
 194         }
 195       else
 196         {
 197           directedLine *newPolygon = temp->deleteDegenerateLines();
 198           if(newPolygon != NULL)
 199             {
 200           retEnd->nextPolygon = temp->deleteDegenerateLines();
 201           retEnd = retEnd->nextPolygon;
 202         }
 203     }
 204     }
 205   return ret;
 206 }
 207
 208 directedLine* directedLine::cutIntersectionAllPoly(int &cutOccur)
 209 {
 210   directedLine* temp;
 211   directedLine *tempNext = NULL;
 212   directedLine* ret= NULL;
 213   directedLine* retEnd = NULL;
 214   cutOccur = 0;
 215   for(temp=this; temp != NULL; temp = tempNext)
 216     {
 217       int eachCutOccur=0;
 218       tempNext = temp->nextPolygon;
 219       temp->nextPolygon = NULL;
 220       if(ret == NULL)
 221         {
 222
 223           ret = retEnd = DBG_cutIntersectionPoly(temp, eachCutOccur);
 224           if(eachCutOccur)
 225             cutOccur = 1;
 226         }
 227       else
 228         {
 229
 230           retEnd->nextPolygon = DBG_cutIntersectionPoly(temp, eachCutOccur);
 231           retEnd = retEnd->nextPolygon;
 232           if(eachCutOccur)
 233             cutOccur = 1;
 234         }
 235     }
 236   return ret;
 237 }
 238
 239
 240 void directedLine::deleteSinglePolygonWithSline()
 241 {
 242   directedLine *temp, *tempNext;
 243   prev->next = NULL;
 244   for(temp=this; temp != NULL; temp = tempNext)
 245     {
 246       tempNext = temp->next;
 247       delete temp->sline;
 248       delete temp;
 249     }
 250 }
 251
 252 void directedLine::deletePolygonListWithSline()
 253 {
 254   directedLine *temp, *tempNext;
 255   for(temp=this; temp != NULL; temp=tempNext)
 256     {
 257       tempNext = temp->nextPolygon;
 258       temp->deleteSinglePolygonWithSline();
 259     }
 260 }
 261
 262 void directedLine::deleteSinglePolygon()
 263 {
 264   directedLine *temp, *tempNext;
 265   prev->next = NULL;
 266   for(temp=this; temp != NULL; temp = tempNext)
 267     {
 268       tempNext = temp->next;
 269       delete temp;
 270     }
 271 }
 272
 273 void directedLine::deletePolygonList()
 274 {
 275   directedLine *temp, *tempNext;
 276   for(temp=this; temp != NULL; temp=tempNext)
 277     {
 278       tempNext = temp->nextPolygon;
 279       temp->deleteSinglePolygon();
 280     }
 281 }
 282
 283
 284 /*a loop by itself*/
 285 directedLine::directedLine(short dir, sampledLine* sl)
 286 {
 287   direction = dir;
 288   sline = sl;
 289   next = this;
 290   prev = this;
 291   nextPolygon = NULL;
 292 //  prevPolygon = NULL;
 293   rootBit = 0;/*important to initilzae to 0 meaning not root yet*/
 294
 295   rootLink = NULL;
 296
 297 }
 298
 299 void directedLine::init(short dir, sampledLine* sl)
 300 {
 301   direction = dir;
 302   sline = sl;
 303 }
 304
 305 directedLine::directedLine()
 306 {
 307   next = this;
 308   prev = this;
 309   nextPolygon = NULL;
 310   rootBit = 0;/*important to initilzae to 0 meaning not root yet*/
 311   rootLink = NULL;
 312   direction = INCREASING;
 313   sline = NULL;
 314 }
 315
 316 directedLine::~directedLine()
 317 {
 318 }
 319
 320 Real* directedLine::head()
 321 {
 322
 323   return (direction==INCREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1];
 324 }
 325
 326 /*inline*/ Real* directedLine::getVertex(Int i)
 327 {
 328   return (direction==INCREASING)? (sline->get_points())[i] : (sline->get_points())[sline->get_npoints() - 1 -i];
 329 }
 330
 331 Real* directedLine::tail()
 332 {
 333   return (direction==DECREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1];
 334 }
 335
 336  /*insert a new line between prev and this*/
 337 void directedLine::insert(directedLine* nl)
 338 {
 339   nl->next = this;
 340   nl->prev = prev;
 341   prev->next = nl;
 342   prev = nl;
 343   nl->rootLink = this; /*assuming that 'this' is the root!!!*/
 344 }
 345
 346 Int directedLine::numEdges()
 347 {
 348   Int ret=0;
 349   directedLine* temp;
 350   if(next == this) return 1;
 351
 352   ret = 1;
 353   for(temp = next; temp != this; temp = temp->next)
 354     ret++;
 355   return ret;
 356 }
 357
 358 Int directedLine::numEdgesAllPolygons()
 359 {
 360   Int ret=0;
 361   directedLine* temp;
 362   for(temp=this; temp!= NULL; temp=temp->nextPolygon)
 363     {
 364       ret += temp->numEdges();
 365     }
 366   return ret;
 367 }
 368
 369 /*return 1 if the double linked list forms a polygon.
 370  */
 371 short directedLine::isPolygon()
 372 {
 373   directedLine* temp;
 374
 375   /*a polygon contains at least 3 edges*/
 376   if(numEdges() <=2) return 0;
 377
 378   /*check this edge*/
 379   if(! isConnected()) return 0;
 380
 381   /*check all other edges*/
 382   for(temp=next; temp != this; temp = temp->next){
 383     if(!isConnected()) return 0;
 384   }
 385   return 1;
 386 }
 387
 388 /*check if the head of this edge is connected to
 389  *the tail of the prev
 390  */
 391 short directedLine::isConnected()
 392 {
 393   if( (head()[0] == prev->tail()[0]) && (head()[1] == prev->tail()[1]))
 394     return 1;
 395   else
 396     return 0;
 397 }
 398
 399 Int compV2InY(Real A[2], Real B[2])
 400 {
 401   if(A[1] < B[1]) return -1;
 402   if(A[1] == B[1] && A[0] < B[0]) return -1;
 403   if(A[1] == B[1] && A[0] == B[0]) return 0;
 404   return 1;
 405 }
 406
 407 Int compV2InX(Real A[2], Real B[2])
 408 {
 409   if(A[0] < B[0]) return -1;
 410   if(A[0] == B[0] && A[1] < B[1]) return -1;
 411   if(A[0] == B[0] && A[1] == B[1]) return 0;
 412   return 1;
 413 }
 414
 415 /*compare two vertices NOT lines!
 416  *A vertex is the head of a directed line.
 417  *(x_1, y_1) <= (x_2, y_2) if
 418  *either y_1 < y_2
 419  *or     y_1 == y_2 && x_1 < x_2.
 420  *return -1 if this->head() <= nl->head(),
 421  *return  1 otherwise
 422  */
 423 Int directedLine::compInY(directedLine* nl)
 424 {
 425   if(head()[1] < nl->head()[1]) return -1;
 426   if(head()[1] == nl->head()[1] && head()[0] < nl->head()[0]) return -1;
 427   return 1;
 428 }
 429
 430 /*compare two vertices NOT lines!
 431  *A vertex is the head of a directed line.
 432  *(x_1, y_1) <= (x_2, y_2) if
 433  *either x_1 < x_2
 434  *or     x_1 == x_2 && y_1 < y_2.
 435  *return -1 if this->head() <= nl->head(),
 436  *return  1 otherwise
 437  */
 438 Int directedLine::compInX(directedLine* nl)
 439 {
 440   if(head()[0] < nl->head()[0]) return -1;
 441   if(head()[0] == nl->head()[0] && head()[1] < nl->head()[1]) return -1;
 442   return 1;
 443 }
 444
 445 /*used by sort precedures
 446  */
 447 static Int compInY2(directedLine* v1, directedLine* v2)
 448 {
 449   return v1->compInY(v2);
 450 }
 451 #ifdef NOT_USED
 452 static Int compInX(directedLine* v1, directedLine* v2)
 453 {
 454   return v1->compInX(v2);
 455 }
 456 #endif
 457
 458 /*sort all the vertices NOT the lines!
 459  *a vertex is the head of a directed line
 460  */
 461 directedLine** directedLine::sortAllPolygons()
 462 {
 463   Int total_num_edges = 0;
 464   directedLine** array = toArrayAllPolygons(total_num_edges);
 465   quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void *, void *)) compInY2);
 466
 467   return array;
 468 }
 469
 470 void directedLine::printSingle()
 471 {
 472   if(direction == INCREASING)
 473     printf("direction is INCREASING\n");
 474   else
 475     printf("direction is DECREASING\n");
 476   printf("head=%f,%f)\n", head()[0], head()[1]);
 477   sline->print();
 478 }
 479
 480 /*print one polygon*/
 481 void directedLine::printList()
 482 {
 483   directedLine* temp;
 484   printSingle();
 485   for(temp = next; temp!=this; temp=temp->next)
 486     temp->printSingle();
 487 }
 488
 489 /*print all the polygons*/
 490 void directedLine::printAllPolygons()
 491 {
 492   directedLine *temp;
 493   for(temp = this; temp!=NULL; temp = temp->nextPolygon)
 494     {
 495       printf("polygon:\n");
 496       temp->printList();
 497     }
 498 }
 499
 500 /*insert this polygon into the head of the old polygon List*/
 501 directedLine* directedLine::insertPolygon(directedLine* oldList)
 502 {
 503   /*this polygon is a root*/
 504   setRootBit();
 505   if(oldList == NULL) return this;
 506   nextPolygon = oldList;
 507 /*  oldList->prevPolygon = this;*/
 508   return this;
 509 }
 510
 511 /*cutoff means delete. but we don't deallocate any space,
 512  *so we use cutoff instead of delete
 513  */
 514 directedLine* directedLine::cutoffPolygon(directedLine *p)
 515 {
 516   directedLine* temp;
 517   directedLine* prev_polygon  = NULL;
 518   if(p == NULL) return this;
 519
 520   for(temp=this; temp != p; temp = temp->nextPolygon)
 521     {
 522       if(temp == NULL)
 523         {
 524           fprintf(stderr, "in cutoffPolygon, not found\n");
 525           exit(1);
 526         }
 527       prev_polygon = temp;
 528     }
 529
 530 /*  prev_polygon = p->prevPolygon;*/
 531
 532   p->resetRootBit();
 533   if(prev_polygon == NULL) /*this is the one to cutoff*/
 534     return nextPolygon;
 535   else {
 536     prev_polygon->nextPolygon = p->nextPolygon;
 537     return this;
 538   }
 539 }
 540
 541 Int directedLine::numPolygons()
 542 {
 543   if(nextPolygon == NULL) return 1;
 544   else return 1+nextPolygon->numPolygons();
 545 }
 546
 547
 548 /*let  array[index ...] denote
 549  *all the edges in this polygon
 550  *return the next available index of array.
 551  */
 552 Int directedLine::toArraySinglePolygon(directedLine** array, Int index)
 553 {
 554   directedLine *temp;
 555   array[index++] = this;
 556   for(temp = next; temp != this; temp = temp->next)
 557     {
 558       array[index++] = temp;
 559     }
 560   return index;
 561 }
 562
 563 /*the space is allocated. The caller is responsible for
 564  *deallocate the space.
 565  *total_num_edges is set to be the total number of edges of all polygons
 566  */
 567 directedLine** directedLine::toArrayAllPolygons(Int& total_num_edges)
 568 {
 569   total_num_edges=numEdgesAllPolygons();
 570   directedLine** ret = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges);
 571   assert(ret);
 572
 573   directedLine *temp;
 574   Int index = 0;
 575   for(temp=this; temp != NULL; temp=temp->nextPolygon) {
 576     index = temp->toArraySinglePolygon(ret, index);
 577   }
 578   return ret;
 579 }
 580
 581 /*assume the polygon is a simple polygon, return
 582  *the area enclosed by it.
 583  *if thee order is counterclock wise, the area is positive.
 584  */
 585 Real directedLine::polyArea()
 586 {
 587   directedLine* temp;
 588   Real ret=0.0;
 589   Real x1,y1,x2,y2;
 590   x1 = this->head()[0];
 591   y1 = this->head()[1];
 592   x2 = this->next->head()[0];
 593   y2 = this->next->head()[1];
 594   ret = -(x2*y1-x1*y2);
 595   for(temp=this->next; temp!=this; temp = temp->next)
 596     {
 597       x1 = temp->head()[0];
 598       y1 = temp->head()[1];
 599       x2 = temp->next->head()[0];
 600       y2 = temp->next->head()[1];
 601       ret += -( x2*y1-x1*y2);
 602     }
 603   return Real(0.5)*ret;
 604 }
 605
 606 /*******************split or combine polygons begin********************/
 607 /*conect a diagonal of a single simple polygon or  two simple polygons.
 608  *If the two vertices v1 (head) and v2 (head) are in the same simple polygon,
 609  *then we actually split the simple polygon into two polygons.
 610  *If instead two vertices velong to two difference polygons,
 611  *then we combine the  two polygons into one polygon.
 612  *It is upto the caller to decide whether this is a split or a
 613  *combination.
 614  *
 615  *Case Split:
 616  *split a single simple polygon into two simple polygons by
 617  *connecting a diagonal (two vertices).
 618  *v1, v2: the two vertices are the head() of the two directedLines.
 619  *  this routine generates one new sampledLine which is returned in
 620  *generatedLine,
 621  *and it generates two directedLines returned in ret_p1 and ret_p2.
 622  *ret_p1 and ret_p2 are used as the entry to the two new polygons.
 623  *Notice the caller should not deallocate the space of v2 and v2 after
 624  *calling this function, since all of the edges are connected to
 625  *ret_p1 or ret_p2.
 626  *
 627  *combine:
 628  *combine two simpolygons into one by connecting one diagonal.
 629  *the returned polygon is returned in ret_p1.
 630  */
 631 /*ARGSUSED*/
 632 void directedLine::connectDiagonal(directedLine* v1, directedLine* v2,
 633                            directedLine** ret_p1,
 634                            directedLine** ret_p2,
 635                            sampledLine** generatedLine,
 636                            directedLine* polygonList                                                               )
 637 {
 638   sampledLine *nsline  = new sampledLine(2);
 639
 640
 641
 642   nsline->setPoint(0, v1->head());
 643   nsline->setPoint(1, v2->head());
 644
 645
 646
 647   /*the increasing line is from v1 head to v2 head*/
 648   directedLine* newLineInc = new directedLine(INCREASING, nsline);
 649
 650
 651
 652   directedLine* newLineDec = new directedLine(DECREASING, nsline);
 653
 654
 655   directedLine* v1Prev = v1->prev;
 656   directedLine* v2Prev = v2->prev;
 657
 658   v1        ->prev = newLineDec;
 659   v2Prev    ->next = newLineDec;
 660   newLineDec->next = v1;
 661   newLineDec->prev = v2Prev;
 662
 663   v2        ->prev = newLineInc;
 664   v1Prev    ->next = newLineInc;
 665   newLineInc->next = v2;
 666   newLineInc->prev = v1Prev;
 667
 668   *ret_p1 = newLineDec;
 669   *ret_p2 = newLineInc;
 670   *generatedLine = nsline;
 671 }
 672
 673 //see the function connectDiangle
 674 /*ARGSUSED*/
 675 void directedLine::connectDiagonal_2slines(directedLine* v1, directedLine* v2,
 676                            directedLine** ret_p1,
 677                            directedLine** ret_p2,
 678                            directedLine* polygonList                                                               )
 679 {
 680   sampledLine *nsline  = new sampledLine(2);
 681   sampledLine *nsline2  = new sampledLine(2);
 682
 683   nsline->setPoint(0, v1->head());
 684   nsline->setPoint(1, v2->head());
 685   nsline2->setPoint(0, v1->head());
 686   nsline2->setPoint(1, v2->head());
 687
 688   /*the increasing line is from v1 head to v2 head*/
 689   directedLine* newLineInc = new directedLine(INCREASING, nsline);
 690
 691   directedLine* newLineDec = new directedLine(DECREASING, nsline2);
 692
 693   directedLine* v1Prev = v1->prev;
 694   directedLine* v2Prev = v2->prev;
 695
 696   v1        ->prev = newLineDec;
 697   v2Prev    ->next = newLineDec;
 698   newLineDec->next = v1;
 699   newLineDec->prev = v2Prev;
 700
 701   v2        ->prev = newLineInc;
 702   v1Prev    ->next = newLineInc;
 703   newLineInc->next = v2;
 704   newLineInc->prev = v1Prev;
 705
 706   *ret_p1 = newLineDec;
 707   *ret_p2 = newLineInc;
 708
 709 }
 710
 711 Int directedLine::samePolygon(directedLine* v1, directedLine* v2)
 712 {
 713   if(v1 == v2) return 1;
 714   directedLine *temp;
 715   for(temp = v1->next; temp != v1; temp = temp->next)
 716     {
 717       if(temp == v2) return 1;
 718     }
 719   return 0;
 720 }
 721
 722 directedLine* directedLine::findRoot()
 723 {
 724   if(rootBit) return this;
 725   directedLine* temp;
 726   for(temp = next; temp != this; temp = temp->next)
 727     if(temp -> rootBit ) return temp;
 728   return NULL; /*should not happen*/
 729 }
 730
 731 directedLine* directedLine::rootLinkFindRoot()
 732 {
 733   directedLine* tempRoot;
 734   directedLine* tempLink;
 735   tempRoot = this;
 736   tempLink = rootLink;
 737   while(tempLink != NULL){
 738     tempRoot = tempLink;
 739     tempLink = tempRoot->rootLink;
 740   }
 741   return tempRoot;
 742 }
 743
 744 /*******************split or combine polygons end********************/
 745
 746 /*****************IO stuff begin*******************/
 747
 748 /*format:
 749  *#polygons
 750  * #vertices
 751  *  vertices
 752  * #vertices
 753  *  vertices
 754  *...
 755  */
 756 void directedLine::writeAllPolygons(char* filename)
 757 {
 758   FILE* fp = fopen(filename, "w");
 759   assert(fp);
 760   Int nPolygons = numPolygons();
 761   directedLine *root;
 762   fprintf(fp, "%i\n", nPolygons);
 763   for(root = this; root != NULL; root = root->nextPolygon)
 764     {
 765       directedLine *temp;
 766       Int npoints=0;
 767       npoints = root->get_npoints()-1;
 768       for(temp = root->next; temp != root; temp=temp->next)
 769         npoints += temp->get_npoints()-1;
 770       fprintf(fp, "%i\n", npoints/*root->numEdges()*/);
 771
 772
 773       for(Int i=0; i<root->get_npoints()-1; i++){
 774         fprintf(fp, "%f ", root->getVertex(i)[0]);
 775         fprintf(fp, "%f ", root->getVertex(i)[1]);
 776       }
 777
 778       for(temp=root->next; temp != root; temp = temp->next)
 779         {
 780           for(Int i=0; i<temp->get_npoints()-1; i++){
 781
 782             fprintf(fp, "%f ", temp->getVertex(i)[0]);
 783             fprintf(fp, "%f ", temp->getVertex(i)[1]);
 784           }
 785           fprintf(fp,"\n");
 786         }
 787       fprintf(fp, "\n");
 788     }
 789   fclose(fp);
 790 }
 791
 792 directedLine* readAllPolygons(char* filename)
 793 {
 794   Int i,j;
 795   FILE* fp = fopen(filename, "r");
 796   Int nPolygons;
 797   int result;
 798
 799   assert(fp);
 800   result = fscanf(fp, "%i", &nPolygons);
 801   assert(result != EOF);
 802   directedLine *ret = NULL;
 803
 804   for(i=0; i<nPolygons; i++)
 805     {
 806       Int nEdges;
 807       result = fscanf(fp, "%i", &nEdges);
 808       assert(result != EOF);
 809       Real vert[2][2] = { { 0 } };
 810       Real VV[2][2];
 811       /*the first two vertices*/
 812       result = fscanf(fp, "%f", &(vert[0][0]));
 813       assert(result != EOF);
 814       result = fscanf(fp, "%f", &(vert[0][1]));
 815       assert(result != EOF);
 816       result = fscanf(fp, "%f", &(vert[1][0]));
 817       assert(result != EOF);
 818       result = fscanf(fp, "%f", &(vert[1][1]));
 819       assert(result != EOF);
 820       VV[1][0] = vert[0][0];
 821       VV[1][1] = vert[0][1];
 822       sampledLine *sLine = new sampledLine(2, vert);
 823       directedLine *thisPoly = new directedLine(INCREASING, sLine);
 824 thisPoly->rootLinkSet(NULL);
 825
 826       directedLine *dLine;
 827       for(j=2; j<nEdges; j++)
 828         {
 829           vert[0][0]=vert[1][0];
 830           vert[0][1]=vert[1][1];
 831           result = fscanf(fp, "%f", &(vert[1][0]));
 832           assert(result != EOF);
 833           result = fscanf(fp, "%f", &(vert[1][1]));
 834           assert(result != EOF);
 835           sLine = new sampledLine(2,vert);
 836           dLine = new directedLine(INCREASING, sLine);
 837 dLine->rootLinkSet(thisPoly);
 838           thisPoly->insert(dLine);
 839         }
 840
 841       VV[0][0]=vert[1][0];
 842       VV[0][1]=vert[1][1];
 843       sLine = new sampledLine(2,VV);
 844       dLine = new directedLine(INCREASING, sLine);
 845 dLine->rootLinkSet(thisPoly);
 846       thisPoly->insert(dLine);
 847
 848       ret = thisPoly->insertPolygon(ret);
 849     }
 850   fclose(fp);
 851   return ret;
 852 }
 853
 854
 855
 856
 857
 858
 859
 860