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