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