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 }
 313
 314 directedLine::~directedLine()
 315 {
 316 }
 317
 318 Real* directedLine::head()
 319 {
 320
 321   return (direction==INCREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1];
 322 }
 323
 324 /*inline*/ Real* directedLine::getVertex(Int i)
 325 {
 326   return (direction==INCREASING)? (sline->get_points())[i] : (sline->get_points())[sline->get_npoints() - 1 -i];
 327 }
 328
 329 Real* directedLine::tail()
 330 {
 331   return (direction==DECREASING)? (sline->get_points())[0] : (sline->get_points())[sline->get_npoints()-1];
 332 }
 333
 334  /*insert a new line between prev and this*/
 335 void directedLine::insert(directedLine* nl)
 336 {
 337   nl->next = this;
 338   nl->prev = prev;
 339   prev->next = nl;
 340   prev = nl;
 341   nl->rootLink = this; /*assuming that 'this' is the root!!!*/
 342 }
 343
 344 Int directedLine::numEdges()
 345 {
 346   Int ret=0;
 347   directedLine* temp;
 348   if(next == this) return 1;
 349
 350   ret = 1;
 351   for(temp = next; temp != this; temp = temp->next)
 352     ret++;
 353   return ret;
 354 }
 355
 356 Int directedLine::numEdgesAllPolygons()
 357 {
 358   Int ret=0;
 359   directedLine* temp;
 360   for(temp=this; temp!= NULL; temp=temp->nextPolygon)
 361     {
 362       ret += temp->numEdges();
 363     }
 364   return ret;
 365 }
 366
 367 /*return 1 if the double linked list forms a polygon.
 368  */
 369 short directedLine::isPolygon()
 370 {
 371   directedLine* temp;
 372
 373   /*a polygon contains at least 3 edges*/
 374   if(numEdges() <=2) return 0;
 375
 376   /*check this edge*/
 377   if(! isConnected()) return 0;
 378
 379   /*check all other edges*/
 380   for(temp=next; temp != this; temp = temp->next){
 381     if(!isConnected()) return 0;
 382   }
 383   return 1;
 384 }
 385
 386 /*check if the head of this edge is connected to
 387  *the tail of the prev
 388  */
 389 short directedLine::isConnected()
 390 {
 391   if( (head()[0] == prev->tail()[0]) && (head()[1] == prev->tail()[1]))
 392     return 1;
 393   else
 394     return 0;
 395 }
 396
 397 Int compV2InY(Real A[2], Real B[2])
 398 {
 399   if(A[1] < B[1]) return -1;
 400   if(A[1] == B[1] && A[0] < B[0]) return -1;
 401   if(A[1] == B[1] && A[0] == B[0]) return 0;
 402   return 1;
 403 }
 404
 405 Int compV2InX(Real A[2], Real B[2])
 406 {
 407   if(A[0] < B[0]) return -1;
 408   if(A[0] == B[0] && A[1] < B[1]) return -1;
 409   if(A[0] == B[0] && A[1] == B[1]) return 0;
 410   return 1;
 411 }
 412
 413 /*compare two vertices NOT lines!
 414  *A vertex is the head of a directed line.
 415  *(x_1, y_1) <= (x_2, y_2) if
 416  *either y_1 < y_2
 417  *or     y_1 == y_2 && x_1 < x_2.
 418  *return -1 if this->head() <= nl->head(),
 419  *return  1 otherwise
 420  */
 421 Int directedLine::compInY(directedLine* nl)
 422 {
 423   if(head()[1] < nl->head()[1]) return -1;
 424   if(head()[1] == nl->head()[1] && head()[0] < nl->head()[0]) return -1;
 425   return 1;
 426 }
 427
 428 /*compare two vertices NOT lines!
 429  *A vertex is the head of a directed line.
 430  *(x_1, y_1) <= (x_2, y_2) if
 431  *either x_1 < x_2
 432  *or     x_1 == x_2 && y_1 < y_2.
 433  *return -1 if this->head() <= nl->head(),
 434  *return  1 otherwise
 435  */
 436 Int directedLine::compInX(directedLine* nl)
 437 {
 438   if(head()[0] < nl->head()[0]) return -1;
 439   if(head()[0] == nl->head()[0] && head()[1] < nl->head()[1]) return -1;
 440   return 1;
 441 }
 442
 443 /*used by sort precedures
 444  */
 445 static Int compInY2(directedLine* v1, directedLine* v2)
 446 {
 447   return v1->compInY(v2);
 448 }
 449 #ifdef NOT_USED
 450 static Int compInX(directedLine* v1, directedLine* v2)
 451 {
 452   return v1->compInX(v2);
 453 }
 454 #endif
 455
 456 /*sort all the vertices NOT the lines!
 457  *a vertex is the head of a directed line
 458  */
 459 directedLine** directedLine::sortAllPolygons()
 460 {
 461   Int total_num_edges = 0;
 462   directedLine** array = toArrayAllPolygons(total_num_edges);
 463   quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void *, void *)) compInY2);
 464
 465   return array;
 466 }
 467
 468 void directedLine::printSingle()
 469 {
 470   if(direction == INCREASING)
 471     printf("direction is INCREASING\n");
 472   else
 473     printf("direction is DECREASING\n");
 474   printf("head=%f,%f)\n", head()[0], head()[1]);
 475   sline->print();
 476 }
 477
 478 /*print one polygon*/
 479 void directedLine::printList()
 480 {
 481   directedLine* temp;
 482   printSingle();
 483   for(temp = next; temp!=this; temp=temp->next)
 484     temp->printSingle();
 485 }
 486
 487 /*print all the polygons*/
 488 void directedLine::printAllPolygons()
 489 {
 490   directedLine *temp;
 491   for(temp = this; temp!=NULL; temp = temp->nextPolygon)
 492     {
 493       printf("polygon:\n");
 494       temp->printList();
 495     }
 496 }
 497
 498 /*insert this polygon into the head of the old polygon List*/
 499 directedLine* directedLine::insertPolygon(directedLine* oldList)
 500 {
 501   /*this polygon is a root*/
 502   setRootBit();
 503   if(oldList == NULL) return this;
 504   nextPolygon = oldList;
 505 /*  oldList->prevPolygon = this;*/
 506   return this;
 507 }
 508
 509 /*cutoff means delete. but we don't deallocate any space,
 510  *so we use cutoff instead of delete
 511  */
 512 directedLine* directedLine::cutoffPolygon(directedLine *p)
 513 {
 514   directedLine* temp;
 515   directedLine* prev_polygon  = NULL;
 516   if(p == NULL) return this;
 517
 518   for(temp=this; temp != p; temp = temp->nextPolygon)
 519     {
 520       if(temp == NULL)
 521         {
 522           fprintf(stderr, "in cutoffPolygon, not found\n");
 523           exit(1);
 524         }
 525       prev_polygon = temp;
 526     }
 527
 528 /*  prev_polygon = p->prevPolygon;*/
 529
 530   p->resetRootBit();
 531   if(prev_polygon == NULL) /*this is the one to cutoff*/
 532     return nextPolygon;
 533   else {
 534     prev_polygon->nextPolygon = p->nextPolygon;
 535     return this;
 536   }
 537 }
 538
 539 Int directedLine::numPolygons()
 540 {
 541   if(nextPolygon == NULL) return 1;
 542   else return 1+nextPolygon->numPolygons();
 543 }
 544
 545
 546 /*let  array[index ...] denote
 547  *all the edges in this polygon
 548  *return the next available index of array.
 549  */
 550 Int directedLine::toArraySinglePolygon(directedLine** array, Int index)
 551 {
 552   directedLine *temp;
 553   array[index++] = this;
 554   for(temp = next; temp != this; temp = temp->next)
 555     {
 556       array[index++] = temp;
 557     }
 558   return index;
 559 }
 560
 561 /*the space is allocated. The caller is responsible for
 562  *deallocate the space.
 563  *total_num_edges is set to be the total number of edges of all polygons
 564  */
 565 directedLine** directedLine::toArrayAllPolygons(Int& total_num_edges)
 566 {
 567   total_num_edges=numEdgesAllPolygons();
 568   directedLine** ret = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges);
 569   assert(ret);
 570
 571   directedLine *temp;
 572   Int index = 0;
 573   for(temp=this; temp != NULL; temp=temp->nextPolygon) {
 574     index = temp->toArraySinglePolygon(ret, index);
 575   }
 576   return ret;
 577 }
 578
 579 /*assume the polygon is a simple polygon, return
 580  *the area enclosed by it.
 581  *if thee order is counterclock wise, the area is positive.
 582  */
 583 Real directedLine::polyArea()
 584 {
 585   directedLine* temp;
 586   Real ret=0.0;
 587   Real x1,y1,x2,y2;
 588   x1 = this->head()[0];
 589   y1 = this->head()[1];
 590   x2 = this->next->head()[0];
 591   y2 = this->next->head()[1];
 592   ret = -(x2*y1-x1*y2);
 593   for(temp=this->next; temp!=this; temp = temp->next)
 594     {
 595       x1 = temp->head()[0];
 596       y1 = temp->head()[1];
 597       x2 = temp->next->head()[0];
 598       y2 = temp->next->head()[1];
 599       ret += -( x2*y1-x1*y2);
 600     }
 601   return Real(0.5)*ret;
 602 }
 603
 604 /*******************split or combine polygons begin********************/
 605 /*conect a diagonal of a single simple polygon or  two simple polygons.
 606  *If the two vertices v1 (head) and v2 (head) are in the same simple polygon,
 607  *then we actually split the simple polygon into two polygons.
 608  *If instead two vertices velong to two difference polygons,
 609  *then we combine the  two polygons into one polygon.
 610  *It is upto the caller to decide whether this is a split or a
 611  *combination.
 612  *
 613  *Case Split:
 614  *split a single simple polygon into two simple polygons by
 615  *connecting a diagonal (two vertices).
 616  *v1, v2: the two vertices are the head() of the two directedLines.
 617  *  this routine generates one new sampledLine which is returned in
 618  *generatedLine,
 619  *and it generates two directedLines returned in ret_p1 and ret_p2.
 620  *ret_p1 and ret_p2 are used as the entry to the two new polygons.
 621  *Notice the caller should not deallocate the space of v2 and v2 after
 622  *calling this function, since all of the edges are connected to
 623  *ret_p1 or ret_p2.
 624  *
 625  *combine:
 626  *combine two simpolygons into one by connecting one diagonal.
 627  *the returned polygon is returned in ret_p1.
 628  */
 629 /*ARGSUSED*/
 630 void directedLine::connectDiagonal(directedLine* v1, directedLine* v2,
 631                            directedLine** ret_p1,
 632                            directedLine** ret_p2,
 633                            sampledLine** generatedLine,
 634                            directedLine* polygonList                                                               )
 635 {
 636   sampledLine *nsline  = new sampledLine(2);
 637
 638
 639
 640   nsline->setPoint(0, v1->head());
 641   nsline->setPoint(1, v2->head());
 642
 643
 644
 645   /*the increasing line is from v1 head to v2 head*/
 646   directedLine* newLineInc = new directedLine(INCREASING, nsline);
 647
 648
 649
 650   directedLine* newLineDec = new directedLine(DECREASING, nsline);
 651
 652
 653   directedLine* v1Prev = v1->prev;
 654   directedLine* v2Prev = v2->prev;
 655
 656   v1        ->prev = newLineDec;
 657   v2Prev    ->next = newLineDec;
 658   newLineDec->next = v1;
 659   newLineDec->prev = v2Prev;
 660
 661   v2        ->prev = newLineInc;
 662   v1Prev    ->next = newLineInc;
 663   newLineInc->next = v2;
 664   newLineInc->prev = v1Prev;
 665
 666   *ret_p1 = newLineDec;
 667   *ret_p2 = newLineInc;
 668   *generatedLine = nsline;
 669 }
 670
 671 //see the function connectDiangle
 672 /*ARGSUSED*/
 673 void directedLine::connectDiagonal_2slines(directedLine* v1, directedLine* v2,
 674                            directedLine** ret_p1,
 675                            directedLine** ret_p2,
 676                            directedLine* polygonList                                                               )
 677 {
 678   sampledLine *nsline  = new sampledLine(2);
 679   sampledLine *nsline2  = new sampledLine(2);
 680
 681   nsline->setPoint(0, v1->head());
 682   nsline->setPoint(1, v2->head());
 683   nsline2->setPoint(0, v1->head());
 684   nsline2->setPoint(1, v2->head());
 685
 686   /*the increasing line is from v1 head to v2 head*/
 687   directedLine* newLineInc = new directedLine(INCREASING, nsline);
 688
 689   directedLine* newLineDec = new directedLine(DECREASING, nsline2);
 690
 691   directedLine* v1Prev = v1->prev;
 692   directedLine* v2Prev = v2->prev;
 693
 694   v1        ->prev = newLineDec;
 695   v2Prev    ->next = newLineDec;
 696   newLineDec->next = v1;
 697   newLineDec->prev = v2Prev;
 698
 699   v2        ->prev = newLineInc;
 700   v1Prev    ->next = newLineInc;
 701   newLineInc->next = v2;
 702   newLineInc->prev = v1Prev;
 703
 704   *ret_p1 = newLineDec;
 705   *ret_p2 = newLineInc;
 706
 707 }
 708
 709 Int directedLine::samePolygon(directedLine* v1, directedLine* v2)
 710 {
 711   if(v1 == v2) return 1;
 712   directedLine *temp;
 713   for(temp = v1->next; temp != v1; temp = temp->next)
 714     {
 715       if(temp == v2) return 1;
 716     }
 717   return 0;
 718 }
 719
 720 directedLine* directedLine::findRoot()
 721 {
 722   if(rootBit) return this;
 723   directedLine* temp;
 724   for(temp = next; temp != this; temp = temp->next)
 725     if(temp -> rootBit ) return temp;
 726   return NULL; /*should not happen*/
 727 }
 728
 729 directedLine* directedLine::rootLinkFindRoot()
 730 {
 731   directedLine* tempRoot;
 732   directedLine* tempLink;
 733   tempRoot = this;
 734   tempLink = rootLink;
 735   while(tempLink != NULL){
 736     tempRoot = tempLink;
 737     tempLink = tempRoot->rootLink;
 738   }
 739   return tempRoot;
 740 }
 741
 742 /*******************split or combine polygons end********************/
 743
 744 /*****************IO stuff begin*******************/
 745
 746 /*format:
 747  *#polygons
 748  * #vertices
 749  *  vertices
 750  * #vertices
 751  *  vertices
 752  *...
 753  */
 754 void directedLine::writeAllPolygons(char* filename)
 755 {
 756   FILE* fp = fopen(filename, "w");
 757   assert(fp);
 758   Int nPolygons = numPolygons();
 759   directedLine *root;
 760   fprintf(fp, "%i\n", nPolygons);
 761   for(root = this; root != NULL; root = root->nextPolygon)
 762     {
 763       directedLine *temp;
 764       Int npoints=0;
 765       npoints = root->get_npoints()-1;
 766       for(temp = root->next; temp != root; temp=temp->next)
 767         npoints += temp->get_npoints()-1;
 768       fprintf(fp, "%i\n", npoints/*root->numEdges()*/);
 769
 770
 771       for(Int i=0; i<root->get_npoints()-1; i++){
 772         fprintf(fp, "%f ", root->getVertex(i)[0]);
 773         fprintf(fp, "%f ", root->getVertex(i)[1]);
 774       }
 775
 776       for(temp=root->next; temp != root; temp = temp->next)
 777         {
 778           for(Int i=0; i<temp->get_npoints()-1; i++){
 779
 780             fprintf(fp, "%f ", temp->getVertex(i)[0]);
 781             fprintf(fp, "%f ", temp->getVertex(i)[1]);
 782           }
 783           fprintf(fp,"\n");
 784         }
 785       fprintf(fp, "\n");
 786     }
 787   fclose(fp);
 788 }
 789
 790 directedLine* readAllPolygons(char* filename)
 791 {
 792   Int i,j;
 793   FILE* fp = fopen(filename, "r");
 794   assert(fp);
 795   Int nPolygons;
 796   fscanf(fp, "%i", &nPolygons);
 797   directedLine *ret = NULL;
 798
 799   for(i=0; i<nPolygons; i++)
 800     {
 801       Int nEdges;
 802       fscanf(fp, "%i", &nEdges);
 803       Real vert[2][2];
 804       Real VV[2][2];
 805       /*the first two vertices*/
 806       fscanf(fp, "%f", &(vert[0][0]));
 807       fscanf(fp, "%f", &(vert[0][1]));
 808       fscanf(fp, "%f", &(vert[1][0]));
 809       fscanf(fp, "%f", &(vert[1][1]));
 810       VV[1][0] = vert[0][0];
 811       VV[1][1] = vert[0][1];
 812       sampledLine *sLine = new sampledLine(2, vert);
 813       directedLine *thisPoly = new directedLine(INCREASING, sLine);
 814 thisPoly->rootLinkSet(NULL);
 815
 816       directedLine *dLine;
 817       for(j=2; j<nEdges; j++)
 818         {
 819           vert[0][0]=vert[1][0];
 820           vert[0][1]=vert[1][1];
 821           fscanf(fp, "%f", &(vert[1][0]));
 822           fscanf(fp, "%f", &(vert[1][1]));
 823           sLine = new sampledLine(2,vert);
 824           dLine = new directedLine(INCREASING, sLine);
 825 dLine->rootLinkSet(thisPoly);
 826           thisPoly->insert(dLine);
 827         }
 828
 829       VV[0][0]=vert[1][0];
 830       VV[0][1]=vert[1][1];
 831       sLine = new sampledLine(2,VV);
 832       dLine = new directedLine(INCREASING, sLine);
 833 dLine->rootLinkSet(thisPoly);
 834       thisPoly->insert(dLine);
 835
 836       ret = thisPoly->insertPolygon(ret);
 837     }
 838   fclose(fp);
 839   return ret;
 840 }
 841
 842
 843
 844
 845
 846
 847
 848