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