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