src/libnurbs/nurbtess/polyDBG.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 "zlassert.h"
  42 #include "polyDBG.h"
  43
  44 #ifdef __WATCOMC__
  45 #pragma warning 14  10
  46 #pragma warning 391 10
  47 #pragma warning 726 10
  48 #endif
  49
  50 static Real area(Real A[2], Real B[2], Real C[2])
  51 {
  52   Real Bx, By, Cx, Cy;
  53   Bx = B[0] - A[0];
  54   By = B[1] - A[1];
  55   Cx = C[0] - A[0];
  56   Cy = C[1] - A[1];
  57   return Bx*Cy - Cx*By;
  58 }
  59
  60 Int DBG_isConvex(directedLine *poly)
  61 {
  62   directedLine* temp;
  63   if(area(poly->head(), poly->tail(), poly->getNext()->tail()) < 0.00000)
  64     return 0;
  65   for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
  66     {
  67       if(area(temp->head(), temp->tail(), temp->getNext()->tail()) < 0.00000)
  68         return 0;
  69     }
  70   return 1;
  71 }
  72
  73 Int DBG_is_U_monotone(directedLine* poly)
  74 {
  75   Int n_changes = 0;
  76   Int prev_sign;
  77   Int cur_sign;
  78    directedLine* temp;
  79   cur_sign = compV2InX(poly->tail(), poly->head());
  80
  81   n_changes = (compV2InX(poly->getPrev()->tail(), poly->getPrev()->head())
  82                != cur_sign);
  83
  84   for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
  85     {
  86       prev_sign = cur_sign;
  87       cur_sign = compV2InX(temp->tail(), temp->head());
  88
  89       if(cur_sign != prev_sign)
  90         n_changes++;
  91     }
  92
  93   if(n_changes ==2) return 1;
  94   else return 0;
  95 }
  96
  97 /*if u-monotone, and there is a long horizontal edge*/
  98 Int DBG_is_U_direction(directedLine* poly)
  99 {
 100 /*
 101   if(! DBG_is_U_monotone(poly))
 102     return 0;
 103 */
 104   Int V_count = 0;
 105   Int U_count = 0;
 106   directedLine* temp;
 107   if( fabs(poly->head()[0] - poly->tail()[0]) <= fabs(poly->head()[1]-poly->tail()[1]))
 108     V_count += poly->get_npoints();
 109   else
 110     U_count += poly->get_npoints();
 111   /*
 112   else if(poly->head()[1] == poly->tail()[1])
 113     U_count += poly->get_npoints();
 114     */
 115   for(temp = poly->getNext(); temp != poly; temp = temp->getNext())
 116     {
 117       if( fabs(temp->head()[0] - temp->tail()[0]) <= fabs(temp->head()[1]-temp->tail()[1]))
 118         V_count += temp->get_npoints();
 119       else
 120         U_count += temp->get_npoints();
 121       /*
 122       if(temp->head()[0] == temp->tail()[0])
 123         V_count += temp->get_npoints();
 124       else if(temp->head()[1] == temp->tail()[1])
 125         U_count += temp->get_npoints();
 126         */
 127     }
 128
 129   if(U_count > V_count) return 1;
 130   else return 0;
 131 }
 132
 133 /*given two line segments, determine whether
 134  *they intersect each other or not.
 135  *return 1 if they do,
 136  *return 0 otherwise
 137  */
 138 Int DBG_edgesIntersect(directedLine* l1, directedLine* l2)
 139 {
 140   if(l1->getNext() == l2)
 141     {
 142       if(area(l1->head(), l1->tail(), l2->tail()) == 0) //colinear
 143         {
 144           if( (l1->tail()[0] - l1->head()[0])*(l2->tail()[0]-l2->head()[0]) +
 145              (l1->tail()[1] - l1->head()[1])*(l2->tail()[1]-l2->head()[1]) >=0)
 146             return 0; //not intersect
 147           else
 148             return 1;
 149         }
 150       //else we use the normal code
 151     }
 152   else if(l1->getPrev() == l2)
 153     {
 154       if(area(l2->head(), l2->tail(), l1->tail()) == 0) //colinear
 155         {
 156           if( (l2->tail()[0] - l2->head()[0])*(l1->tail()[0]-l1->head()[0]) +
 157              (l2->tail()[1] - l2->head()[1])*(l1->tail()[1]-l1->head()[1]) >=0)
 158             return 0; //not intersect
 159           else
 160             return 1;
 161         }
 162       //else we use the normal code
 163     }
 164   else //the two edges are not connected
 165     {
 166       if((l1->head()[0] == l2->head()[0] &&
 167          l1->head()[1] == l2->head()[1]) ||
 168          (l1->tail()[0] == l2->tail()[0] &&
 169          l1->tail()[1] == l2->tail()[1]))
 170         return 1;
 171
 172     }
 173
 174
 175   if(
 176      (
 177       area(l1->head(), l1->tail(), l2->head())
 178       *
 179       area(l1->head(), l1->tail(), l2->tail())
 180       < 0
 181       )
 182      &&
 183      (
 184       area(l2->head(), l2->tail(), l1->head())
 185       *area(l2->head(), l2->tail(), l1->tail())
 186       < 0
 187       )
 188      )
 189     return 1;
 190   else
 191     return 0;
 192 }
 193
 194 /*whether AB and CD intersect
 195  *return 1 if they do
 196  *retur 0 otheriwse
 197  */
 198 Int DBG_edgesIntersectGen(Real A[2], Real B[2], Real C[2], Real D[2])
 199 {
 200   if(
 201      (
 202       area(A, B, C) * area(A,B,D) <0
 203       )
 204      &&
 205      (
 206       area(C,D,A) * area(C,D,B) < 0
 207       )
 208      )
 209     return 1;
 210   else
 211     return 0;
 212 }
 213
 214 /*determien whether    (A,B) interesect chain[start] to [end]
 215  */
 216 Int DBG_intersectChain(vertexArray* chain, Int start, Int end, Real A[2], Real B[2])
 217 {
 218   Int i;
 219   for(i=start; i<=end-2; i++)
 220     if(DBG_edgesIntersectGen(chain->getVertex(i), chain->getVertex(i+1), A, B))
 221       return 1;
 222
 223   return 0;
 224 }
 225
 226 /*determine whether a polygon intersect itself or not
 227  *return 1 is it does,
 228  *       0 otherwise
 229  */
 230 Int DBG_polygonSelfIntersect(directedLine* poly)
 231 {
 232   directedLine* temp1;
 233   directedLine* temp2;
 234   temp1=poly;
 235   for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
 236     {
 237       if(DBG_edgesIntersect(temp1, temp2))
 238         {
 239           return 1;
 240         }
 241
 242     }
 243
 244   for(temp1=poly->getNext(); temp1 != poly; temp1 = temp1->getNext())
 245     for(temp2=temp1->getNext(); temp2 != temp1; temp2=temp2->getNext())
 246       {
 247         if(DBG_edgesIntersect(temp1, temp2))
 248           {
 249             return 1;
 250           }
 251       }
 252   return 0;
 253 }
 254
 255 /*check whether a line segment intersects a  polygon
 256  */
 257 Int DBG_edgeIntersectPoly(directedLine* edge, directedLine* poly)
 258 {
 259   directedLine* temp;
 260   if(DBG_edgesIntersect(edge, poly))
 261     return 1;
 262   for(temp=poly->getNext(); temp != poly; temp=temp->getNext())
 263     if(DBG_edgesIntersect(edge, temp))
 264       return 1;
 265   return 0;
 266 }
 267
 268 /*check whether two polygons intersect
 269  */
 270 Int DBG_polygonsIntersect(directedLine* p1, directedLine* p2)
 271 {
 272   directedLine* temp;
 273   if(DBG_edgeIntersectPoly(p1, p2))
 274     return 1;
 275   for(temp=p1->getNext(); temp!= p1; temp = temp->getNext())
 276     if(DBG_edgeIntersectPoly(temp, p2))
 277       return 1;
 278   return 0;
 279 }
 280
 281 /*check whether there are polygons intersecting each other in
 282  *a list of polygons
 283  */
 284 Int DBG_polygonListIntersect(directedLine* pList)
 285 {
 286   directedLine *temp;
 287   for(temp=pList; temp != NULL; temp = temp->getNextPolygon())
 288     if(DBG_polygonSelfIntersect(temp))
 289       return 1;
 290   directedLine* temp2;
 291   for(temp=pList; temp!=NULL; temp=temp->getNextPolygon())
 292     {
 293       for(temp2=temp->getNextPolygon(); temp2 != NULL; temp2=temp2->getNextPolygon())
 294         if(DBG_polygonsIntersect(temp, temp2))
 295           return 1;
 296     }
 297
 298   return 0;
 299 }
 300
 301
 302 Int DBG_isCounterclockwise(directedLine* poly)
 303 {
 304   return (poly->polyArea() > 0);
 305 }
 306
 307 /*ray: v0 with direction (dx,dy).
 308  *edge: v1-v2.
 309  * the extra point v10[2] is given for the information at
 310  *v1. Basically this edge is connectd to edge
 311  * v10-v1. If v1 is on the ray,
 312  * then we need v10  to determine whether this ray intersects
 313  * the edge or not (that is, return 1 or return 0).
 314  * If v1 is on the ray, then if v2 and v10 are on the same side of the ray,
 315  * we return 0, otherwise return 1.
 316  *For v2, if v2 is on the ray, we always return 0.
 317  *Notice that v1 and v2 are not symmetric. So the edge is directed!!!
 318  * The purpose for this convention is such that: a point is inside a polygon
 319  * if and only if it intersets with odd number of edges.
 320  */
 321 Int DBG_rayIntersectEdge(Real v0[2], Real dx, Real dy, Real v10[2], Real v1[2], Real v2[2])
 322 {
 323 /*
 324 if( (v1[1] >= v0[1] && v2[1]<= v0[1] )
 325   ||(v2[1] >= v0[1] && v1[1]<= v0[1] )
 326    )
 327   printf("rayIntersectEdge, *********\n");
 328 */
 329
 330   Real denom = (v2[0]-v1[0])*(-dy) - (v2[1]-v1[1]) * (-dx);
 331   Real nomRay = (v2[0]-v1[0]) * (v0[1] - v1[1]) - (v2[1]-v1[1])*(v0[0]-v1[0]);
 332   Real nomEdge = (v0[0]-v1[0]) * (-dy) - (v0[1]-v1[1])*(-dx);
 333
 334
 335   /*if the ray is parallel to the edge, return 0: not intersect*/
 336   if(denom == 0.0)
 337     return 0;
 338
 339   /*if v0 is on the edge, return 0: not intersect*/
 340   if(nomRay == 0.0)
 341     return 0;
 342
 343   /*if v1 is on the positive ray, and the neighbor of v1 crosses the ray
 344    *return 1: intersect
 345    */
 346   if(nomEdge == 0)
 347     { /*v1 is on the positive or negative ray*/
 348
 349 /*
 350       printf("v1 is on the ray\n");
 351 */
 352
 353       if(dx*(v1[0]-v0[0])>=0 && dy*(v1[1]-v0[1])>=0) /*v1 on positive ray*/
 354         {
 355           if(area(v0, v1, v10) * area(v0, v1, v2) >0)
 356             return 0;
 357           else
 358             return 1;
 359         }
 360       else /*v1 on negative ray*/
 361         return 0;
 362     }
 363
 364   /*if v2 is on the ray, always return 0: not intersect*/
 365   if(nomEdge == denom) {
 366 /*    printf("v2 is on the ray\n");*/
 367     return 0;
 368   }
 369
 370   /*finally */
 371   if(denom*nomRay>0 && denom*nomEdge>0 && nomEdge/denom <=1.0)
 372     return 1;
 373   return 0;
 374 }
 375
 376
 377 /*return the number of intersections*/
 378 Int DBG_rayIntersectPoly(Real v0[2], Real dx, Real dy, directedLine* poly)
 379 {
 380   directedLine* temp;
 381   Int count=0;
 382   if(DBG_rayIntersectEdge(v0, dx, dy, poly->getPrev()->head(), poly->head(), poly->tail()))
 383     count++;
 384
 385   for(temp=poly->getNext(); temp != poly; temp = temp->getNext())
 386     if(DBG_rayIntersectEdge(v0, dx, dy, temp->getPrev()->head(), temp->head(), temp->tail()))
 387       count++;
 388 /*printf("ray intersect poly: count=%i\n", count);*/
 389   return count;
 390 }
 391
 392 Int DBG_pointInsidePoly(Real v[2], directedLine* poly)
 393 {
 394 /*
 395 printf("enter pointInsidePoly , v=(%f,%f)\n", v[0], v[1]);
 396 printf("the polygon is\n");
 397 poly->printList();
 398 */
 399   /*for debug purpose*/
 400   assert( (DBG_rayIntersectPoly(v,1,0,poly) % 2 )
 401          == (DBG_rayIntersectPoly(v,1,Real(0.1234), poly) % 2 )
 402          );
 403   if(DBG_rayIntersectPoly(v, 1, 0, poly) % 2 == 1)
 404     return 1;
 405   else
 406     return 0;
 407 }
 408
 409 /*return the number of polygons which contain thie polygon
 410  * as a subset
 411  */
 412 Int DBG_enclosingPolygons(directedLine* poly, directedLine* list)
 413 {
 414   directedLine* temp;
 415   Int count=0;
 416 /*
 417 printf("%i\n", DBG_pointInsidePoly(poly->head(),
 418                                    list->getNextPolygon()
 419                                    ->getNextPolygon()
 420                                    ->getNextPolygon()
 421                                    ->getNextPolygon()
 422 ));
 423 */
 424
 425   for(temp = list; temp != NULL; temp = temp->getNextPolygon())
 426     {
 427       if(poly != temp)
 428         if(DBG_pointInsidePoly(poly->head(), temp))
 429           count++;
 430 /*      printf("count=%i\n", count);*/
 431     }
 432   return count;
 433 }
 434
 435 void  DBG_reverse(directedLine* poly)
 436 {
 437   if(poly->getDirection() == INCREASING)
 438     poly->putDirection(DECREASING);
 439   else
 440     poly->putDirection(INCREASING);
 441
 442   directedLine* oldNext = poly->getNext();
 443   poly->putNext(poly->getPrev());
 444   poly->putPrev(oldNext);
 445
 446   directedLine* temp;
 447   for(temp=oldNext; temp!=poly; temp = oldNext)
 448     {
 449       if(temp->getDirection() == INCREASING)
 450         temp->putDirection(DECREASING);
 451       else
 452         temp->putDirection(INCREASING);
 453
 454       oldNext = temp->getNext();
 455       temp->putNext(temp->getPrev());
 456       temp->putPrev(oldNext);
 457     }
 458   printf("reverse done\n");
 459 }
 460
 461 Int DBG_checkConnectivity(directedLine *polygon)
 462 {
 463   if(polygon == NULL) return 1;
 464   directedLine* temp;
 465   if(polygon->head()[0] != polygon->getPrev()->tail()[0] ||
 466      polygon->head()[1] != polygon->getPrev()->tail()[1])
 467     return 0;
 468   for(temp=polygon->getNext(); temp != polygon; temp=temp->getNext())
 469     {
 470       if(temp->head()[0] != temp->getPrev()->tail()[0] ||
 471          temp->head()[1] != temp->getPrev()->tail()[1])
 472         return 0;
 473     }
 474   return 1;
 475 }
 476
 477 /*print out error message.
 478  *If it cannot modify the polygon list to make it satify the
 479  *requirements, return 1.
 480  *otherwise modify the polygon list, and return 0
 481  */
 482 Int DBG_check(directedLine *polyList)
 483 {
 484   directedLine* temp;
 485   if(polyList == NULL) return 0;
 486
 487   /*if there are intersections, print out error message
 488    */
 489   if(DBG_polygonListIntersect(polyList))
 490     {
 491       fprintf(stderr, "DBG_check: there are self intersections, don't know to modify the polygons\n");
 492     return 1;
 493     }
 494
 495   /*check the connectivity of each polygon*/
 496   for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
 497     {
 498       if(! DBG_checkConnectivity(temp))
 499         {
 500           fprintf(stderr, "DBG_check, polygon not connected\n");
 501           return 1;
 502         }
 503     }
 504
 505   /*check the orientation of each polygon*/
 506   for(temp = polyList; temp!= NULL; temp = temp ->getNextPolygon())
 507     {
 508
 509
 510       Int correctDir;
 511
 512       if( DBG_enclosingPolygons(temp, polyList) % 2 == 0)
 513         correctDir = 1; /*counterclockwise*/
 514       else
 515         correctDir = 0; /*clockwise*/
 516
 517       Int actualDir = DBG_isCounterclockwise(temp);
 518
 519       if(correctDir != actualDir)
 520         {
 521           fprintf(stderr, "DBG_check: polygon with incorrect orientations. reversed\n");
 522
 523           DBG_reverse(temp);
 524         }
 525
 526     }
 527   return 0;
 528 }
 529
 530 /**************handle self intersections*****************/
 531 //determine whether e interects [begin, end] or not
 532 static directedLine* DBG_edgeIntersectChainD(directedLine *e,
 533                                directedLine *begin, directedLine *end)
 534 {
 535   directedLine *temp;
 536   for(temp=begin; temp != end; temp = temp->getNext())
 537     {
 538       if(DBG_edgesIntersect(e, temp))
 539          return temp;
 540     }
 541   if(DBG_edgesIntersect(e, end))
 542     return end;
 543   return NULL;
 544 }
 545
 546 //given a polygon, cut the edges off and finally obtain a
 547 //a polygon without intersections. The cut-off edges are
 548 //dealloated. The new polygon is returned.
 549 directedLine* DBG_cutIntersectionPoly(directedLine *polygon, int& cutOccur)
 550 {
 551   directedLine *begin, *end, *next;
 552   begin = polygon;
 553   end = polygon;
 554   cutOccur = 0;
 555   while( (next = end->getNext()) != begin)
 556     {
 557       directedLine *interc = NULL;
 558       if( (interc = DBG_edgeIntersectChainD(next, begin, end)))
 559         {
 560           int fixed = 0;
 561           if(DBG_edgesIntersect(next, interc->getNext()))
 562              {
 563                //trying to fix it
 564                Real buf[2];
 565                int i;
 566                Int n=5;
 567                buf[0] = interc->tail()[0];
 568                buf[1] = interc->tail()[1];
 569
 570                for(i=1; i<n; i++)
 571                  {
 572                    Real r = ((Real)i) / ((Real) n);
 573                    Real u = (1-r) * interc->head()[0] + r * interc->tail()[0];
 574                    Real v = (1-r) * interc->head()[1] + r * interc->tail()[1];
 575                    interc->tail()[0] = interc->getNext()->head()[0] = u;
 576                    interc->tail()[1] = interc->getNext()->head()[1] = v;
 577                    if( (! DBG_edgesIntersect(next, interc)) &&
 578                       (! DBG_edgesIntersect(next, interc->getNext())))
 579                      break; //we fixed it
 580                  }
 581                if(i==n) // we didn't fix it
 582                  {
 583                    fixed = 0;
 584                    //back to original
 585                    interc->tail()[0] = interc->getNext()->head()[0] = buf[0];
 586                    interc->tail()[1] = interc->getNext()->head()[1] = buf[1];
 587                  }
 588                else
 589                  {
 590                    fixed = 1;
 591                  }
 592              }
 593           if(fixed == 0)
 594             {
 595               cutOccur = 1;
 596               begin->deleteSingleLine(next);
 597
 598               if(begin != end)
 599                 {
 600                   if(DBG_polygonSelfIntersect(begin))
 601                     {
 602                       directedLine* newEnd = end->getPrev();
 603                       begin->deleteSingleLine(end);
 604                       end = newEnd;
 605                     }
 606                 }
 607             }
 608           else
 609             {
 610               end = end->getNext();
 611             }
 612         }
 613       else
 614         {
 615           end = end->getNext();
 616         }
 617     }
 618   return begin;
 619 }
 620
 621 //given a polygon, cut the edges off and finally obtain a
 622 //a polygon without intersections. The cut-off edges are
 623 //dealloated. The new polygon is returned.
 624 #if 0 // UNUSED
 625 static directedLine* DBG_cutIntersectionPoly_notwork(directedLine *polygon)
 626 {
 627   directedLine *crt;//current polygon
 628   directedLine *begin;
 629   directedLine *end;
 630   directedLine *temp;
 631   crt = polygon;
 632   int find=0;
 633   while(1)
 634     {
 635 //printf("loop\n");
 636       //if there are less than 3 edges, we should stop
 637       if(crt->getPrev()->getPrev() == crt)
 638         return NULL;
 639
 640       if(DBG_edgesIntersect(crt, crt->getNext()) ||
 641         (crt->head()[0] == crt->getNext()->tail()[0] &&
 642         crt->head()[1] == crt->getNext()->tail()[1])
 643          )
 644         {
 645           find = 1;
 646           crt=crt->deleteChain(crt, crt->getNext());
 647         }
 648       else
 649         {
 650           //now we know crt and crt->getNext do not intersect
 651           begin = crt;
 652           end = crt->getNext();
 653 //printf("begin=(%f,%f)\n", begin->head()[0], begin->head()[1]);
 654 //printf("end=(%f,%f)\n", end->head()[0], end->head()[1]);
 655           for(temp=end->getNext(); temp!=begin; temp= temp->getNext())
 656             {
 657 //printf("temp=(%f,%f)\n", temp->head()[0], temp->head()[1]);
 658                directedLine *intersect = DBG_edgeIntersectChainD(temp, begin, end);
 659                if(intersect != NULL)
 660                 {
 661                   crt = crt->deleteChain(intersect, temp);
 662                   find=1;
 663                   break; //the for loop
 664                 }
 665               else
 666                 {
 667                   end = temp;
 668                 }
 669             }
 670         }
 671       if(find == 0)
 672         return crt;
 673       else
 674         find = 0;    //go to next loop
 675 }
 676 }
 677 #endif
 678
 679 directedLine* DBG_cutIntersectionAllPoly(directedLine* list)
 680 {
 681   directedLine* temp;
 682   directedLine* tempNext=NULL;
 683   directedLine* ret = NULL;
 684   int cutOccur=0;
 685   for(temp=list; temp != NULL; temp = tempNext)
 686     {
 687       directedLine *left;
 688       tempNext = temp->getNextPolygon();
 689
 690       left = DBG_cutIntersectionPoly(temp, cutOccur);
 691       if(left != NULL)
 692         ret=left->insertPolygon(ret);
 693     }
 694   return ret;
 695 }
 696
 697 sampledLine*  DBG_collectSampledLinesAllPoly(directedLine *polygonList)
 698 {
 699   directedLine *temp;
 700   sampledLine* tempHead = NULL;
 701   sampledLine* tempTail = NULL;
 702   sampledLine* cHead = NULL;
 703   sampledLine* cTail = NULL;
 704
 705   if(polygonList == NULL)
 706     return NULL;
 707
 708   DBG_collectSampledLinesPoly(polygonList, cHead, cTail);
 709
 710   assert(cHead);
 711   assert(cTail);
 712   for(temp = polygonList->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
 713     {
 714       DBG_collectSampledLinesPoly(temp, tempHead, tempTail);
 715       cTail->insert(tempHead);
 716       cTail = tempTail;
 717     }
 718   return cHead;
 719 }
 720
 721 void  DBG_collectSampledLinesPoly(directedLine *polygon, sampledLine*& retHead, sampledLine*& retTail)
 722 {
 723   directedLine *temp;
 724   retHead = NULL;
 725   retTail = NULL;
 726   if(polygon == NULL)
 727     return;
 728
 729   retHead = retTail = polygon->getSampledLine();
 730   for(temp = polygon->getNext(); temp != polygon; temp=temp->getNext())
 731     {
 732       retHead = temp->getSampledLine()->insert(retHead);
 733     }
 734 }