reactos/dll/glu32/libnurbs/nurbtess/partitionY.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$ $Revision: 1.1 $
  35 */
  36 /*
  37 ** $Header: /cygdrive/c/RCVS/CVS/ReactOS/reactos/lib/glu32/libnurbs/nurbtess/partitionY.cc,v 1.1 2004/02/02 16:39:13 navaraf Exp $
  38 */
  39
  40 #include <stdlib.h>
  41 #include <stdio.h>
  42 #include <time.h>
  43
  44 #include "zlassert.h"
  45 #include "partitionY.h"
  46 #include "searchTree.h"
  47 #include "quicksort.h"
  48 #include "polyUtil.h"
  49
  50
  51 #define max(a,b) ((a>b)? a:b)
  52 #define min(a,b) ((a>b)? b:a)
  53
  54
  55 /*retrurn
  56  *-1: if A < B (Ya<Yb) || (Ya==Yb)
  57  * 0: if A == B
  58  * 1: if A>B
  59  */
  60 static Int compVertInY(Real A[2], Real B[2])
  61 {
  62   if( (A[1] < B[1]) || (A[1]==B[1] && A[0]<B[0]))
  63     return -1;
  64   else if
  65     ( A[1] == B[1] && A[0] == B[0]) return 0;
  66   else
  67     return 1;
  68 }
  69
  70 /*v is a vertex: the head of en edge,
  71  *e is an edge,
  72  *return 1 if e is below v: assume v1 and v2 are the two endpoints of e:
  73  * v1<= v, v2<=v.
  74  */
  75 Int isBelow(directedLine *v, directedLine *e)
  76 {
  77   Real* vert = v->head();
  78   if(   compVertInY(e->head(), vert) != 1
  79      && compVertInY(e->tail(), vert) != 1
  80      )
  81     return 1;
  82   else
  83     return 0;
  84 }
  85
  86 /*v is a vertex: the head of en edge,
  87  *e is an edge,
  88  *return 1 if e is below v: assume v1 and v2 are the two endpoints of e:
  89  * v1>= v, v2>=v.
  90  */
  91 Int isAbove(directedLine *v, directedLine *e)
  92 {
  93   Real* vert = v->head();
  94   if(   compVertInY(e->head(), vert) != -1
  95      && compVertInY(e->tail(), vert) != -1
  96      )
  97     return 1;
  98   else
  99     return 0;
 100 }
 101
 102 Int isCusp(directedLine *v)
 103 {
 104   Real *A=v->getPrev()->head();
 105   Real *B=v->head();
 106   Real *C=v->tail();
 107   if(A[1] < B[1] && B[1] < C[1])
 108     return 0;
 109   else if(A[1] > B[1] && B[1] > C[1])
 110     return 0;
 111   else if(A[1] < B[1] && C[1] < B[1])
 112     return 1;
 113   else if(A[1] > B[1] && C[1] > B[1])
 114     return 1;
 115
 116   if(isAbove(v, v) && isAbove(v, v->getPrev()) ||
 117      isBelow(v, v) && isBelow(v, v->getPrev()))
 118     return 1;
 119   else
 120     return 0;
 121 }
 122
 123 /*crossproduct is strictly less than 0*/
 124 Int isReflex(directedLine *v)
 125 {
 126   Real* A = v->getPrev()->head();
 127   Real* B = v->head();
 128   Real* C = v->tail();
 129   Real Bx,By, Cx, Cy;
 130   Bx = B[0] - A[0];
 131   By = B[1] - A[1];
 132   Cx = C[0] - A[0];
 133   Cy = C[1] - A[1];
 134
 135   if(Bx*Cy - Cx*By < 0) return 1;
 136   else return 0;
 137 }
 138
 139  /*return
 140  *0: not-cusp
 141  *1: interior cusp
 142  *2: exterior cusp
 143  */
 144 Int cuspType(directedLine *v)
 145 {
 146   if(! isCusp(v)) return 0;
 147   else if(isReflex(v)) return 1;
 148   else
 149     return 2;
 150 }
 151
 152 sweepRange* sweepRangeMake(directedLine* left, Int leftType,
 153                            directedLine* right, Int rightType)
 154 {
 155   sweepRange* ret = (sweepRange*)malloc(sizeof(sweepRange));
 156   assert(ret);
 157   ret->left = left;
 158   ret->leftType = leftType;
 159   ret->right = right;
 160   ret->rightType = rightType;
 161   return ret;
 162 }
 163
 164 void sweepRangeDelete(sweepRange* range)
 165 {
 166   free(range);
 167 }
 168
 169 Int sweepRangeEqual(sweepRange* src1, sweepRange* src2)
 170 {
 171   Int leftEqual;
 172   Int rightEqual;
 173
 174
 175   /*The case when both are vertices should not happen*/
 176   assert(! (src1->leftType == 0 && src2->leftType == 0));
 177   if(src1->leftType == 0 && src2->leftType == 1){
 178     if(src1->left == src2->left ||
 179        src1->left->getPrev() == src2->left
 180        )
 181       leftEqual = 1;
 182     else
 183       leftEqual = 0;
 184   }
 185   else if(src1->leftType == 1 && src2->leftType == 1){
 186     if(src1->left == src2->left)
 187       leftEqual = 1;
 188     else
 189       leftEqual = 0;
 190   }
 191   else /*src1->leftType == 1 && src2->leftType == 0*/{
 192     if(src1->left == src2->left ||
 193        src1->left == src2->left->getPrev()
 194        )
 195       leftEqual = 1;
 196     else
 197       leftEqual = 0;
 198   }
 199
 200   /*the same thing for right*/
 201   /*The case when both are vertices should not happen*/
 202   assert(! (src1->rightType == 0 && src2->rightType == 0));
 203   if(src1->rightType == 0 && src2->rightType == 1){
 204     if(src1->right == src2->right ||
 205        src1->right->getPrev() == src2->right
 206        )
 207       rightEqual = 1;
 208     else
 209       rightEqual = 0;
 210   }
 211   else if(src1->rightType == 1 && src2->rightType == 1){
 212     if(src1->right == src2->right)
 213       rightEqual = 1;
 214     else
 215       rightEqual = 0;
 216   }
 217   else /*src1->rightType == 1 && src2->rightType == 0*/{
 218     if(src1->right == src2->right ||
 219        src1->right == src2->right->getPrev()
 220        )
 221       rightEqual = 1;
 222     else
 223       rightEqual = 0;
 224   }
 225
 226   return (leftEqual == 1 || rightEqual == 1);
 227 }
 228
 229 /*given (x_1, y_1) and (x_2, y_2), and y
 230  *return x such that (x,y) is on the line
 231  */
 232 inline/*static*/ Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
 233 {
 234   return ((y2==y1)? (x1+x2)*Real(0.5) : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
 235 /*
 236   if(y2 == y1) return (x1+x2)*0.5;
 237   else return x1 + ((y-y1)/(y2-y1)) * (x2-x1);
 238 */
 239 }
 240
 241 /*compare two edges of a polygon.
 242  *edge A < edge B if there is a horizontal line so that the intersection
 243  *with A is to the left of the intersection with B.
 244  *This function is used in sweepY for the dynamic search tree insertion to
 245  *order the edges.
 246  * Implementation: (x_1,y_1) and (x_2, y_2)
 247  */
 248 static Int compEdges(directedLine *e1, directedLine *e2)
 249 {
 250   Real* head1 = e1->head();
 251   Real* tail1 = e1->tail();
 252   Real* head2 = e2->head();
 253   Real* tail2 = e2->tail();
 254 /*
 255   Real h10 = head1[0];
 256   Real h11 = head1[1];
 257   Real t10 = tail1[0];
 258   Real t11 = tail1[1];
 259   Real h20 = head2[0];
 260   Real h21 = head2[1];
 261   Real t20 = tail2[0];
 262   Real t21 = tail2[1];
 263 */
 264   Real e1_Ymax, e1_Ymin, e2_Ymax, e2_Ymin;
 265 /*
 266   if(h11>t11) {
 267     e1_Ymax= h11;
 268     e1_Ymin= t11;
 269   }
 270   else{
 271     e1_Ymax = t11;
 272     e1_Ymin = h11;
 273   }
 274
 275   if(h21>t21) {
 276     e2_Ymax= h21;
 277     e2_Ymin= t21;
 278   }
 279   else{
 280     e2_Ymax = t21;
 281     e2_Ymin = h21;
 282   }
 283 */
 284
 285   if(head1[1]>tail1[1]) {
 286     e1_Ymax= head1[1];
 287     e1_Ymin= tail1[1];
 288   }
 289   else{
 290     e1_Ymax = tail1[1];
 291     e1_Ymin = head1[1];
 292   }
 293
 294   if(head2[1]>tail2[1]) {
 295     e2_Ymax= head2[1];
 296     e2_Ymin= tail2[1];
 297   }
 298   else{
 299     e2_Ymax = tail2[1];
 300     e2_Ymin = head2[1];
 301   }
 302
 303
 304   /*Real e1_Ymax = max(head1[1], tail1[1]);*/ /*max(e1->head()[1], e1->tail()[1]);*/
 305   /*Real e1_Ymin = min(head1[1], tail1[1]);*/ /*min(e1->head()[1], e1->tail()[1]);*/
 306   /*Real e2_Ymax = max(head2[1], tail2[1]);*/ /*max(e2->head()[1], e2->tail()[1]);*/
 307   /*Real e2_Ymin = min(head2[1], tail2[1]);*/ /*min(e2->head()[1], e2->tail()[1]);*/
 308
 309   Real Ymax = min(e1_Ymax, e2_Ymax);
 310   Real Ymin = max(e1_Ymin, e2_Ymin);
 311
 312   Real y = Real(0.5)*(Ymax + Ymin);
 313
 314 /*  Real x1 = intersectHoriz(e1->head()[0], e1->head()[1], e1->tail()[0], e1->tail()[1], y);
 315   Real x2 = intersectHoriz(e2->head()[0], e2->head()[1], e2->tail()[0], e2->tail()[1], y);
 316 */
 317 /*
 318   Real x1 = intersectHoriz(h10, h11, t10, t11, y);
 319   Real x2 = intersectHoriz(h20, h21, t20, t21, y);
 320 */
 321   Real x1 = intersectHoriz(head1[0], head1[1], tail1[0], tail1[1], y);
 322   Real x2 = intersectHoriz(head2[0], head2[1], tail2[0], tail2[1], y);
 323
 324   if(x1<= x2) return -1;
 325   else return 1;
 326 }
 327
 328 /*used by sort precedures
 329  */
 330 static Int compInY(directedLine* v1, directedLine* v2)
 331 {
 332   return v1->compInY(v2);
 333 }
 334
 335 void findDiagonals(Int total_num_edges, directedLine** sortedVertices, sweepRange** ranges, Int& num_diagonals, directedLine** diagonal_vertices)
 336 {
 337   Int i,j,k;
 338
 339   k=0;
 340
 341   for(i=0; i<total_num_edges; i++)
 342     {
 343       directedLine* vert =sortedVertices[i];
 344       directedLine* thisEdge = vert;
 345       directedLine* prevEdge = vert->getPrev();
 346 /*
 347 printf("find i=%i\n", i);
 348 printf("the vertex is\n");
 349 vert->printSingle();
 350 */
 351       if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
 352         {
 353           /*this is an upward interior cusp*/
 354           diagonal_vertices[k++] = vert;
 355
 356           for(j=i+1; j<total_num_edges; j++)
 357             if(sweepRangeEqual(ranges[i], ranges[j]))
 358               {
 359                 diagonal_vertices[k++] = sortedVertices[j];
 360                 break;
 361               }
 362           assert(j<total_num_edges);
 363
 364
 365         }
 366       else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
 367         {
 368           /*this is an downward interior cusp*/
 369           diagonal_vertices[k++] = vert;
 370           for(j=i-1; j>=0; j--)
 371             if(sweepRangeEqual(ranges[i], ranges[j]))
 372               {
 373                 diagonal_vertices[k++] = sortedVertices[j];
 374                 break;
 375               }
 376 /*        printf("j=%i\n", j);*/
 377           assert(j>=0);
 378
 379
 380
 381         }
 382     }
 383   num_diagonals = k/2;
 384 }
 385
 386 /*get rid of repeated diagonlas so that each diagonal appears only once in the array
 387  */
 388 Int deleteRepeatDiagonals(Int num_diagonals, directedLine** diagonal_vertices, directedLine** new_vertices)
 389 {
 390   Int i,k;
 391   Int j,l;
 392   Int index;
 393   index=0;
 394   for(i=0,k=0; i<num_diagonals; i++, k+=2)
 395     {
 396       Int isRepeated=0;
 397       /*check the diagonla (diagonal_vertice[k], diagonal_vertices[k+1])
 398        *is repeated or not
 399        */
 400       for(j=0,l=0; j<index; j++, l+=2)
 401         {
 402           if(
 403              (diagonal_vertices[k] == new_vertices[l] &&
 404               diagonal_vertices[k+1] == new_vertices[l+1]
 405               )
 406              ||
 407              (
 408               diagonal_vertices[k] == new_vertices[l+1] &&
 409               diagonal_vertices[k+1] == new_vertices[l]
 410               )
 411              )
 412             {
 413               isRepeated=1;
 414               break;
 415             }
 416         }
 417       if(! isRepeated)
 418         {
 419           new_vertices[index+index] = diagonal_vertices[k];
 420           new_vertices[index+index+1] = diagonal_vertices[k+1];
 421           index++;
 422         }
 423     }
 424   return index;
 425 }
 426
 427 /*for debug only*/
 428 directedLine** DBGfindDiagonals(directedLine *polygons, Int& num_diagonals)
 429 {
 430   Int total_num_edges = 0;
 431   directedLine** array = polygons->toArrayAllPolygons(total_num_edges);
 432   quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void*, void*)) compInY);
 433   sweepRange** ranges = (sweepRange**) malloc(sizeof(sweepRange*) * total_num_edges);
 434   assert(ranges);
 435
 436   sweepY(total_num_edges, array, ranges);
 437
 438  directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges);
 439   assert(diagonal_vertices);
 440   findDiagonals(total_num_edges, array, ranges, num_diagonals, diagonal_vertices);
 441
 442   num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
 443   return diagonal_vertices;
 444
 445 }
 446
 447
 448 /*partition into Y-monotone polygons*/
 449 directedLine* partitionY(directedLine *polygons, sampledLine **retSampledLines)
 450 {
 451   Int total_num_edges = 0;
 452   directedLine** array = polygons->toArrayAllPolygons(total_num_edges);
 453
 454   quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void*, void*)) compInY);
 455
 456   sweepRange** ranges = (sweepRange**) malloc(sizeof(sweepRange*) * (total_num_edges));
 457   assert(ranges);
 458
 459
 460
 461   sweepY(total_num_edges, array, ranges);
 462
 463
 464
 465   /*the diagonal vertices are stored as:
 466    *v0-v1: 1st diagonal
 467    *v2-v3: 2nd diagonal
 468    *v5-v5: 3rd diagonal
 469    *...
 470    */
 471
 472
 473   Int num_diagonals;
 474   /*number diagonals is < total_num_edges*total_num_edges*/
 475   directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges*2/*total_num_edges*/);
 476   assert(diagonal_vertices);
 477
 478
 479
 480   findDiagonals(total_num_edges, array, ranges, num_diagonals, diagonal_vertices);
 481
 482
 483
 484   directedLine* ret_polygons = polygons;
 485   sampledLine* newSampledLines = NULL;
 486   Int i,k;
 487
 488 num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
 489
 490
 491
 492   Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals);
 493   for(i=0; i<num_diagonals; i++)
 494     removedDiagonals[i] = 0;
 495
 496
 497
 498
 499
 500   for(i=0,k=0; i<num_diagonals; i++,k+=2)
 501     {
 502
 503
 504       directedLine* v1=diagonal_vertices[k];
 505       directedLine* v2=diagonal_vertices[k+1];
 506       directedLine* ret_p1;
 507       directedLine* ret_p2;
 508
 509       /*we ahve to determine whether v1 and v2 belong to the same polygon before
 510        *their structure are modified by connectDiagonal().
 511        */
 512 /*
 513       directedLine *root1 = v1->findRoot();
 514       directedLine *root2 = v2->findRoot();
 515       assert(root1);
 516       assert(root2);
 517 */
 518
 519 directedLine*  root1 = v1->rootLinkFindRoot();
 520 directedLine*  root2 = v2->rootLinkFindRoot();
 521
 522       if(root1 != root2)
 523         {
 524
 525           removedDiagonals[i] = 1;
 526           sampledLine* generatedLine;
 527
 528
 529
 530           v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
 531
 532
 533
 534           newSampledLines = generatedLine->insert(newSampledLines);
 535 /*
 536           ret_polygons = ret_polygons->cutoffPolygon(root1);
 537
 538           ret_polygons = ret_polygons->cutoffPolygon(root2);
 539           ret_polygons = ret_p1->insertPolygon(ret_polygons);
 540 root1->rootLinkSet(ret_p1);
 541 root2->rootLinkSet(ret_p1);
 542 ret_p1->rootLinkSet(NULL);
 543 ret_p2->rootLinkSet(ret_p1);
 544 */
 545           ret_polygons = ret_polygons->cutoffPolygon(root2);
 546
 547
 548
 549 root2->rootLinkSet(root1);
 550 ret_p1->rootLinkSet(root1);
 551 ret_p2->rootLinkSet(root1);
 552
 553        /*now that we have connected the diagonal v1 and v2,
 554         *we have to check those unprocessed diagonals which
 555         *have v1 or v2 as an end point. Notice that the head of v1
 556         *has the same coodinates as the head of v2->prev, and the head of
 557         *v2 has the same coordinate as the head of v1->prev.
 558         *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid
 559         *diagonal, then x should be on the left hand side of the directed line:        *v1->prev->head -- v1->head -- v1->tail. Otherwise, (v1,x) should be
 560         *replaced by (v2->prev, x), that is, x is on the left of
 561         * v2->prev->prev->head, v2->prev->head, v2->prev->tail.
 562         */
 563         Int ii, kk;
 564         for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2)
 565           if( removedDiagonals[ii]==0)
 566             {
 567               directedLine* d1=diagonal_vertices[kk];
 568               directedLine* d2=diagonal_vertices[kk+1];
 569               /*check d1, and replace diagonal_vertices[kk] if necessary*/
 570               if(d1 == v1) {
 571                 /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/
 572                 if(! pointLeft2Lines(v1->getPrev()->head(),
 573                                      v1->head(), v1->tail(), d2->head()))
 574                   {
 575 /*
 576                     assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
 577                                            v2->getPrev()->head(),
 578                                            v2->getPrev()->tail(), d2->head()));
 579 */
 580                     diagonal_vertices[kk] = v2->getPrev();
 581                   }
 582               }
 583               if(d1 == v2) {
 584                 /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/
 585                 if(! pointLeft2Lines(v2->getPrev()->head(),
 586                                      v2->head(), v2->tail(), d2->head()))
 587                   {
 588 /*
 589                     assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
 590                                            v1->getPrev()->head(),
 591                                            v1->getPrev()->tail(), d2->head()));
 592 */
 593                     diagonal_vertices[kk] = v1->getPrev();
 594                   }
 595               }
 596               /*check d2 and replace diagonal_vertices[k+1] if necessary*/
 597               if(d2 == v1) {
 598                 /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/
 599                 if(! pointLeft2Lines(v1->getPrev()->head(),
 600                                      v1->head(), v1->tail(), d1->head()))
 601                   {
 602 /*                  assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
 603                                            v2->getPrev()->head(),
 604                                            v2->getPrev()->tail(), d1->head()));
 605 */
 606                     diagonal_vertices[kk+1] = v2->getPrev();
 607                   }
 608               }
 609               if(d2 == v2) {
 610                 /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/
 611                 if(! pointLeft2Lines(v2->getPrev()->head(),
 612                                      v2->head(), v2->tail(), d1->head()))
 613                   {
 614 /*                  assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
 615                                            v1->getPrev()->head(),
 616                                            v1->getPrev()->tail(), d1->head()));
 617 */
 618                     diagonal_vertices[kk+1] = v1->getPrev();
 619                   }
 620               }
 621             }
 622 }/*end if (root1 not equal to root 2)*/
 623 }
 624
 625   /*second pass,  now all diagoals should belong to the same polygon*/
 626
 627
 628
 629   for(i=0,k=0; i<num_diagonals; i++, k += 2)
 630     if(removedDiagonals[i] == 0)
 631       {
 632
 633
 634         directedLine* v1=diagonal_vertices[k];
 635         directedLine* v2=diagonal_vertices[k+1];
 636
 637
 638
 639         directedLine* ret_p1;
 640         directedLine* ret_p2;
 641
 642         /*we ahve to determine whether v1 and v2 belong to the same polygon before
 643          *their structure are modified by connectDiagonal().
 644          */
 645         directedLine *root1 = v1->findRoot();
 646 /*
 647         directedLine *root2 = v2->findRoot();
 648
 649
 650
 651         assert(root1);
 652         assert(root2);
 653         assert(root1 == root2);
 654   */
 655         sampledLine* generatedLine;
 656
 657
 658
 659         v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
 660         newSampledLines = generatedLine->insert(newSampledLines);
 661
 662         ret_polygons = ret_polygons->cutoffPolygon(root1);
 663
 664         ret_polygons = ret_p1->insertPolygon(ret_polygons);
 665
 666         ret_polygons = ret_p2->insertPolygon(ret_polygons);
 667
 668
 669
 670         for(Int j=i+1; j<num_diagonals; j++)
 671           {
 672             if(removedDiagonals[j] ==0)
 673               {
 674
 675                 directedLine* temp1=diagonal_vertices[2*j];
 676                 directedLine* temp2=diagonal_vertices[2*j+1];
 677                if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2)
 678                 if(! temp1->samePolygon(temp1, temp2))
 679                   {
 680                     /*if temp1 and temp2 are in different polygons,
 681                      *then one of them must be v1 or v2.
 682                      */
 683
 684
 685
 686                     assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2);
 687                     if(temp1==v1)
 688                       {
 689                         diagonal_vertices[2*j] = v2->getPrev();
 690                       }
 691                     if(temp2==v1)
 692                       {
 693                         diagonal_vertices[2*j+1] = v2->getPrev();
 694                       }
 695                     if(temp1==v2)
 696                       {
 697                         diagonal_vertices[2*j] = v1->getPrev();
 698                       }
 699                     if(temp2==v2)
 700                       {
 701                         diagonal_vertices[2*j+1] = v1->getPrev();
 702                       }
 703                   }
 704               }
 705           }
 706
 707       }
 708
 709   /*clean up spaces*/
 710   free(array);
 711   free(ranges);
 712   free(diagonal_vertices);
 713   free(removedDiagonals);
 714
 715   *retSampledLines = newSampledLines;
 716   return ret_polygons;
 717 }
 718
 719 /*given a set of simple polygons where the interior
 720  *is decided by left-hand principle,
 721  *return a range (sight) for each vertex. This is called
 722  *Trapezoidalization.
 723  */
 724 void sweepY(Int nVertices, directedLine** sortedVertices, sweepRange** ret_ranges)
 725 {
 726   Int i;
 727   /*for each vertex in the sorted list, update the binary search tree.
 728    *and store the range information for each vertex.
 729    */
 730   treeNode* searchTree = NULL;
 731   for(i=0; i<nVertices;i++)
 732     {
 733
 734       directedLine* vert = sortedVertices[i];
 735
 736       directedLine* thisEdge = vert;
 737       directedLine* prevEdge = vert->getPrev();
 738
 739       if(isBelow(vert, thisEdge) && isAbove(vert, prevEdge))
 740         {
 741
 742           /*case 1: this < v < prev
 743            *the polygon is going down at v, the interior is to
 744            *the right hand side.
 745            * find the edge to the right of thisEdge for right range.
 746            * delete thisEdge
 747            * insert prevEdge
 748            */
 749           treeNode* thisNode = TreeNodeFind(searchTree, thisEdge, ( Int (*) (void *, void *))compEdges);
 750           assert(thisNode);
 751
 752           treeNode* succ = TreeNodeSuccessor(thisNode);
 753           assert(succ);
 754           searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
 755           searchTree = TreeNodeInsert(searchTree, TreeNodeMake(prevEdge), ( Int (*) (void *, void *))compEdges);
 756
 757
 758           ret_ranges[i] = sweepRangeMake(vert, 0, (directedLine*) (succ->key), 1);
 759
 760         }
 761       else if(isAbove(vert, thisEdge) && isBelow(vert, prevEdge))
 762         {
 763
 764           /*case 2: this > v > prev
 765            *the polygon is going up at v, the interior is to
 766            *the left hand side.
 767            * find the edge to the left of thisEdge for left range.
 768            * delete prevEdge
 769            * insert thisEdge
 770            */
 771           treeNode* prevNode = TreeNodeFind(searchTree, prevEdge, ( Int (*) (void *, void *))compEdges);
 772           assert(prevNode);
 773           treeNode* pred = TreeNodePredecessor(prevNode);
 774           searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
 775           searchTree = TreeNodeInsert(searchTree, TreeNodeMake(thisEdge), ( Int (*) (void *, void *))compEdges);
 776           ret_ranges[i] = sweepRangeMake((directedLine*)(pred->key), 1, vert, 0);
 777         }
 778       else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge))
 779         {
 780
 781           /*case 3: insert both edges*/
 782           treeNode* thisNode = TreeNodeMake(thisEdge);
 783           treeNode* prevNode = TreeNodeMake(prevEdge);
 784           searchTree = TreeNodeInsert(searchTree, thisNode, ( Int (*) (void *, void *))compEdges);
 785           searchTree = TreeNodeInsert(searchTree, prevNode, ( Int (*) (void *, void *))compEdges);
 786           if(compEdges(thisEdge, prevEdge)<0)  /*interior cusp*/
 787             {
 788
 789               treeNode* leftEdge = TreeNodePredecessor(thisNode);
 790               treeNode* rightEdge = TreeNodeSuccessor(prevNode);
 791               ret_ranges[i] = sweepRangeMake( (directedLine*) leftEdge->key, 1,
 792                                              (directedLine*) rightEdge->key, 1
 793                                              );
 794             }
 795           else /*exterior cusp*/
 796             {
 797
 798               ret_ranges[i] = sweepRangeMake( prevEdge, 1, thisEdge, 1);
 799             }
 800         }
 801       else if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge))
 802         {
 803
 804           /*case 4: delete both edges*/
 805           treeNode* thisNode = TreeNodeFind(searchTree, thisEdge, ( Int (*) (void *, void *))compEdges);
 806           treeNode* prevNode = TreeNodeFind(searchTree, prevEdge, ( Int (*) (void *, void *))compEdges);
 807           if(compEdges(thisEdge, prevEdge)>0) /*interior cusp*/
 808             {
 809               treeNode* leftEdge = TreeNodePredecessor(prevNode);
 810               treeNode* rightEdge = TreeNodeSuccessor(thisNode);
 811               ret_ranges[i] = sweepRangeMake( (directedLine*) leftEdge->key, 1,
 812                                              (directedLine*) rightEdge->key, 1
 813                                              );
 814             }
 815           else /*exterior cusp*/
 816             {
 817               ret_ranges[i] = sweepRangeMake( thisEdge, 1, prevEdge, 1);
 818             }
 819           searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
 820           searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
 821         }
 822       else
 823         {
 824           fprintf(stderr,"error in partitionY.C, invalid case\n");
 825           printf("vert is\n");
 826           vert->printSingle();
 827           printf("thisEdge is\n");
 828           thisEdge->printSingle();
 829           printf("prevEdge is\n");
 830           prevEdge->printSingle();
 831
 832           exit(1);
 833         }
 834     }
 835
 836   /*finaly clean up space: delete the search tree*/
 837   TreeNodeDeleteWholeTree(searchTree);
 838 }