ReactOS 0.4.16-dev-401-g45b008d
monoChain.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 "gluos.h"
39//#include <stdlib.h>
40//#include <stdio.h>
41//#include <GL/gl.h>
42
43//#include "glimports.h"
44#include "zlassert.h"
45
46#include "monoChain.h"
47#include "quicksort.h"
48#include "searchTree.h"
49#include "polyUtil.h"
50
51#ifndef max
52#define max(a,b) ((a>b)? a:b)
53#endif
54#ifndef min
55#define min(a,b) ((a>b)? b:a)
56#endif
57
58extern Int isCusp(directedLine *v);
59extern Int deleteRepeatDiagonals(Int num_diagonals, directedLine** diagonal_vertices, directedLine** new_vertices);
60
61//for debug purpose only
62#if 0 // UNUSED
63static void drawDiagonals(Int num_diagonals, directedLine** diagonal_vertices)
64{
65 Int i;
66 for(i=0; i<num_diagonals; i++)
67 {
69 glVertex2fv(diagonal_vertices[2*i]->head());
70 glVertex2fv(diagonal_vertices[2*i+1]->head());
71 glEnd();
72 }
73}
74#endif
75
76/*given (x_1, y_1) and (x_2, y_2), and y
77 *return x such that (x,y) is on the line
78 */
80{
81 return ((y2==y1)? (x1+x2)*0.5 : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
82}
83
84//compare the heads of the two chains
85static int compChainHeadInY(monoChain* mc1, monoChain* mc2)
86{
87 return compV2InY(mc1->getHead()->head(), mc2->getHead()->head());
88}
89
91{
92 chainHead = cHead;
93 chainTail = cTail;
94 next = this;
95 prev = this;
96
98
99 //compute bounding box
101 minX = maxX = chainTail->head()[0];
102 minY = maxY = chainTail->head()[1];
103
104 for(temp=chainHead; temp!=cTail; temp = temp->getNext())
105 {
106 if(temp->head()[0] < minX)
107 minX = temp->head()[0];
108 if(temp->head()[0] > maxX)
109 maxX = temp->head()[0];
110
111 if(temp->head()[1] < minY)
112 minY = temp->head()[1];
113 if(temp->head()[1] > maxY)
114 maxY = temp->head()[1];
115 }
116
117 //check whether the chain is increasing or decreasing
119 isIncrease = 1;
120 else
121 isIncrease = 0;
122
123 //initilize currrent, this is used for accelerating search
124 if(isIncrease)
126 else
128
129 isKey = 0;
130 keyY = 0;
131}
132
133//insert a new line between prev and this
135{
136 nc->next = this;
137 nc->prev = prev;
138 prev->next = nc;
139 prev = nc;
140}
141
143{
144 monoChain *temp, *tempNext;
145 prev->next = NULL;
146 for(temp=this; temp != NULL; temp = tempNext)
147 {
148 tempNext = temp->next;
149 delete temp;
150 }
151}
152
154{
155 monoChain *temp, *tempNext;
156 for(temp=this; temp != NULL; temp = tempNext)
157 {
158 tempNext = temp->nextPolygon;
159 temp->deleteLoop();
160 }
161}
162
164{
166 array[index++] = this;
167 for(temp = next; temp != this; temp = temp->next)
168 {
169 array[index++] = temp;
170 }
171 return index;
172}
173
175{
176 num_chains = numChainsAllLoops();
177 monoChain **ret = (monoChain**) malloc(sizeof(monoChain*) * num_chains);
178 assert(ret);
180 Int index = 0;
181 for(temp = this; temp != NULL; temp=temp->nextPolygon){
182 index = temp->toArraySingleLoop(ret, index);
183 }
184 return ret;
185}
186
188{
189 Int ret=0;
191 if(next == this) return 1;
192 ret = 1;
193 for(temp=next; temp != this; temp = temp->next)
194 ret++;
195 return ret;
196}
197
199{
200 Int ret=0;
202 for(temp =this; temp != NULL; temp = temp->nextPolygon)
203 ret += temp->numChainsSingleLoop();
204 return ret;
205}
206
207//update 'current'
209{
211 if(isIncrease)
212 {
213 for(temp= current; temp != chainTail; temp = temp->getNext())
214 {
215 if(temp->head()[1] > y)
216 break;
217 }
218 current = temp->getPrev();
219 }
220 else
221 {
222 for(temp = current; temp != chainHead; temp = temp->getPrev())
223 {
224 if(temp->head()[1] > y)
225 break;
226 }
227 current = temp->getNext();
228 }
229 return intersectHoriz(current->head()[0], current->head()[1], current->tail()[0], current->tail()[1], y);
230}
231
233{
236
237 //find the first cusp
238 directedLine *prevCusp=NULL;
239 directedLine *firstCusp;
240
241 if(isCusp(loop))
242 prevCusp = loop;
243 else
244 {
245 for(temp = loop->getNext(); temp != loop; temp = temp->getNext())
246 if(isCusp(temp))
247 break;
248 prevCusp = temp;
249 }
250 firstCusp = prevCusp;
251//printf("first cusp is (%f,%f), (%f,%f), (%f,%f)\n", prevCusp->getPrev()->head()[0], prevCusp->getPrev()->head()[1], prevCusp->head()[0], prevCusp->head()[1], prevCusp->tail()[0], prevCusp->tail()[1]);
252
253 for(temp = prevCusp->getNext(); temp != loop; temp = temp->getNext())
254 {
255 if(isCusp(temp))
256 {
257//printf("the cusp is (%f,%f), (%f,%f), (%f,%f)\n", temp->getPrev()->head()[0], temp->getPrev()->head()[1], temp->head()[0], temp->head()[1], temp->tail()[0], temp->tail()[1]);
258 if(ret == NULL)
259 {
260 ret = new monoChain(prevCusp, temp);
261 }
262 else
263 ret->insert(new monoChain(prevCusp, temp));
264 prevCusp = temp;
265 }
266 }
267 assert(ret);
268 ret->insert(new monoChain(prevCusp, firstCusp));
269
270 return ret;
271}
272
274{
276 monoChain* mc;
277 monoChain* mcEnd;
279 mcEnd = mc;
280 for(temp = list->getNextPolygon(); temp != NULL; temp = temp->getNextPolygon())
281 {
283 mcEnd->setNextPolygon(newLoop);
284 mcEnd = newLoop;
285 }
286 return mc;
287}
288
289/*compare two edges of a polygon.
290 *edge A < edge B if there is a horizontal line so that the intersection
291 *with A is to the left of the intersection with B.
292 *This function is used in sweepY for the dynamic search tree insertion to
293 *order the edges.
294 * Implementation: (x_1,y_1) and (x_2, y_2)
295 */
297{
298 Real* head1 = e1->head();
299 Real* tail1 = e1->tail();
300 Real* head2 = e2->head();
301 Real* tail2 = e2->tail();
302/*
303 Real h10 = head1[0];
304 Real h11 = head1[1];
305 Real t10 = tail1[0];
306 Real t11 = tail1[1];
307 Real h20 = head2[0];
308 Real h21 = head2[1];
309 Real t20 = tail2[0];
310 Real t21 = tail2[1];
311*/
312 Real e1_Ymax, e1_Ymin, e2_Ymax, e2_Ymin;
313/*
314 if(h11>t11) {
315 e1_Ymax= h11;
316 e1_Ymin= t11;
317 }
318 else{
319 e1_Ymax = t11;
320 e1_Ymin = h11;
321 }
322
323 if(h21>t21) {
324 e2_Ymax= h21;
325 e2_Ymin= t21;
326 }
327 else{
328 e2_Ymax = t21;
329 e2_Ymin = h21;
330 }
331*/
332
333 if(head1[1]>tail1[1]) {
334 e1_Ymax= head1[1];
335 e1_Ymin= tail1[1];
336 }
337 else{
338 e1_Ymax = tail1[1];
339 e1_Ymin = head1[1];
340 }
341
342 if(head2[1]>tail2[1]) {
343 e2_Ymax= head2[1];
344 e2_Ymin= tail2[1];
345 }
346 else{
347 e2_Ymax = tail2[1];
348 e2_Ymin = head2[1];
349 }
350
351
352 /*Real e1_Ymax = max(head1[1], tail1[1]);*/ /*max(e1->head()[1], e1->tail()[1]);*/
353 /*Real e1_Ymin = min(head1[1], tail1[1]);*/ /*min(e1->head()[1], e1->tail()[1]);*/
354 /*Real e2_Ymax = max(head2[1], tail2[1]);*/ /*max(e2->head()[1], e2->tail()[1]);*/
355 /*Real e2_Ymin = min(head2[1], tail2[1]);*/ /*min(e2->head()[1], e2->tail()[1]);*/
356
357 Real Ymax = min(e1_Ymax, e2_Ymax);
358 Real Ymin = max(e1_Ymin, e2_Ymin);
359
360 Real y = 0.5*(Ymax + Ymin);
361
362/* Real x1 = intersectHoriz(e1->head()[0], e1->head()[1], e1->tail()[0], e1->tail()[1], y);
363 Real x2 = intersectHoriz(e2->head()[0], e2->head()[1], e2->tail()[0], e2->tail()[1], y);
364*/
365/*
366 Real x1 = intersectHoriz(h10, h11, t10, t11, y);
367 Real x2 = intersectHoriz(h20, h21, t20, t21, y);
368*/
369 Real x1 = intersectHoriz(head1[0], head1[1], tail1[0], tail1[1], y);
370 Real x2 = intersectHoriz(head2[0], head2[1], tail2[0], tail2[1], y);
371
372 if(x1<= x2) return -1;
373 else return 1;
374}
375
377{
378 Real y;
379 assert(mc1->isKey || mc2->isKey);
380 if(mc1->isKey)
381 y = mc1->keyY;
382 else
383 y = mc2->keyY;
384 directedLine *d1 = mc1->find(y);
385 directedLine *d2 = mc2->find(y);
386 mc2->find(y);
387// Real x1 = mc1->chainIntersectHoriz(y);
388// Real x2 = mc2->chainIntersectHoriz(y);
389 return compEdges(d1, d2);
390}
391
392//this function modifies current for efficiency
394{
397 assert(current->head()[1] <= y);
398 if(isIncrease)
399 {
400 assert(chainTail->head()[1] >=y);
401 for(temp=current; temp!=chainTail; temp = temp->getNext())
402 {
403 if(temp->head()[1] > y)
404 break;
405 }
406 current = temp->getPrev();
407 ret = current;
408 }
409 else
410 {
411 for(temp=current; temp != chainHead; temp = temp->getPrev())
412 {
413 if(temp->head()[1] > y)
414 break;
415 }
416 current = temp->getNext();
417 ret = temp;
418 }
419 return ret;
420}
421
423{
425 for(temp = chainHead; temp != chainTail; temp = temp->getNext())
426 {
427 printf("(%f,%f) ", temp->head()[0], temp->head()[1]);
428 }
429 printf("(%f,%f) \n", chainTail->head()[0], chainTail->head()[1]);
430}
431
433{
435 this->printOneChain();
436 for(temp = next; temp != this; temp = temp->next)
437 {
438 temp->printOneChain();
439 }
440 printf("\n");
441}
442
444{
446 for(temp=this; temp != NULL; temp = temp->nextPolygon)
447 temp->printChainLoop();
448}
449
450//return 1 if error occures
451Int MC_sweepY(Int nVertices, monoChain** sortedVertices, sweepRange** ret_ranges)
452{
453 Int i;
454 Real keyY;
455 Int errOccur=0;
456//printf("enter MC_sweepY\n");
457//printf("nVertices=%i\n", nVertices);
458 /*for each vertex in the sorted list, update the binary search tree.
459 *and store the range information for each vertex.
460 */
461 treeNode* searchTree = NULL;
462//printf("nVertices=%i\n", nVertices);
463 for(i=0; i<nVertices; i++)
464 {
465 monoChain* vert = sortedVertices[i];
466 keyY = vert->getHead()->head()[1]; //the sweep line
467 directedLine *dline = vert->getHead();
468 directedLine *dlinePrev = dline->getPrev();
469 if(isBelow(dline, dline) && isBelow(dline, dlinePrev))
470 {
471//printf("case 1\n");
472 //this<v and prev < v
473 //delete both edges
474 vert->isKey = 1;
475 vert->keyY = keyY;
476 treeNode* thisNode = TreeNodeFind(searchTree, vert, (Int (*) (void *, void *))compChains);
477 vert->isKey = 0;
478
479 vert->getPrev()->isKey = 1;
480 vert->getPrev()->keyY = keyY;
481 treeNode* prevNode = TreeNodeFind(searchTree, vert->getPrev(), (Int (*) (void *, void *))compChains);
482 vert->getPrev()->isKey = 0;
483
484 if(cuspType(dline) == 1)//interior cusp
485 {
486
487 treeNode* leftEdge = TreeNodePredecessor(prevNode);
488 treeNode* rightEdge = TreeNodeSuccessor(thisNode);
489 if(leftEdge == NULL || rightEdge == NULL)
490 {
491 errOccur = 1;
492 goto JUMP_HERE;
493 }
494
495 directedLine* leftEdgeDline = ((monoChain* ) leftEdge->key)->find(keyY);
496
497
498
499 directedLine* rightEdgeDline = ((monoChain* ) rightEdge->key)->find(keyY);
500
501 ret_ranges[i] = sweepRangeMake(leftEdgeDline, 1, rightEdgeDline, 1);
502 }
503 else /*exterior cusp*/
504 {
505 ret_ranges[i] = sweepRangeMake( dline, 1, dlinePrev, 1);
506 }
507
508 searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
509 searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
510
511 }
512 else if(isAbove(dline, dline) && isAbove(dline, dlinePrev))
513 {
514//printf("case 2\n");
515 //insert both edges
516 treeNode* thisNode = TreeNodeMake(vert);
517 treeNode* prevNode = TreeNodeMake(vert->getPrev());
518
519 vert->isKey = 1;
520 vert->keyY = keyY;
521 searchTree = TreeNodeInsert(searchTree, thisNode, (Int (*) (void *, void *))compChains);
522 vert->isKey = 0;
523
524 vert->getPrev()->isKey = 1;
525 vert->getPrev()->keyY = keyY;
526 searchTree = TreeNodeInsert(searchTree, prevNode, (Int (*) (void *, void *))compChains);
527 vert->getPrev()->isKey = 0;
528
529 if(cuspType(dline) == 1) //interior cusp
530 {
531//printf("cuspType is 1\n");
532 treeNode* leftEdge = TreeNodePredecessor(thisNode);
533 treeNode* rightEdge = TreeNodeSuccessor(prevNode);
534 if(leftEdge == NULL || rightEdge == NULL)
535 {
536 errOccur = 1;
537 goto JUMP_HERE;
538 }
539//printf("leftEdge is %i, rightEdge is %i\n", leftEdge, rightEdge);
540 directedLine* leftEdgeDline = ((monoChain*) leftEdge->key)->find(keyY);
541 directedLine* rightEdgeDline = ((monoChain*) rightEdge->key)->find(keyY);
542 ret_ranges[i] = sweepRangeMake( leftEdgeDline, 1, rightEdgeDline, 1);
543 }
544 else //exterior cusp
545 {
546//printf("cuspType is not 1\n");
547 ret_ranges[i] = sweepRangeMake(dlinePrev, 1, dline, 1);
548 }
549 }
550 else
551 {
552//printf("%i,%i\n", isAbove(dline, dline), isAbove(dline, dlinePrev));
553 errOccur = 1;
554 goto JUMP_HERE;
555
556 fprintf(stderr, "error in MC_sweepY\n");
557 exit(1);
558 }
559 }
560
561 JUMP_HERE:
562 //finally clean up space: delete the search tree
563 TreeNodeDeleteWholeTree(searchTree);
564 return errOccur;
565}
566
567void MC_findDiagonals(Int total_num_edges, monoChain** sortedVertices,
568 sweepRange** ranges, Int& num_diagonals,
569 directedLine** diagonal_vertices)
570{
571 Int i,j,k;
572 k=0;
573 //reset 'current' of all the monoChains
574 for(i=0; i<total_num_edges; i++)
575 sortedVertices[i]->resetCurrent();
576
577 for(i=0; i<total_num_edges; i++)
578 {
579 directedLine* vert = sortedVertices[i]->getHead();
580 directedLine* thisEdge = vert;
581 directedLine* prevEdge = vert->getPrev();
582 if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
583 {
584 //this is an upward interior cusp
585 diagonal_vertices[k++] = vert;
586
587 directedLine* leftEdge = ranges[i]->left;
588 directedLine* rightEdge = ranges[i]->right;
589
590 directedLine* leftVert = leftEdge;
591 directedLine* rightVert = rightEdge->getNext();
592 assert(leftVert->head()[1] >= vert->head()[1]);
593 assert(rightVert->head()[1] >= vert->head()[1]);
594 directedLine* minVert = (leftVert->head()[1] <= rightVert->head()[1])?leftVert:rightVert;
595 Int found = 0;
596 for(j=i+1; j<total_num_edges; j++)
597 {
598 if(sortedVertices[j]->getHead()->head()[1] > minVert->head()[1])
599 break;
600
601 if(sweepRangeEqual(ranges[i], ranges[j]))
602 {
603 found = 1;
604 break;
605 }
606 }
607
608 if(found)
609 diagonal_vertices[k++] = sortedVertices[j]->getHead();
610 else
611 diagonal_vertices[k++] = minVert;
612 }
613 else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
614 {
615 //downward interior cusp
616 diagonal_vertices[k++] = vert;
617 directedLine* leftEdge = ranges[i]->left;
618 directedLine* rightEdge = ranges[i]->right;
619 directedLine* leftVert = leftEdge->getNext();
620 directedLine* rightVert = rightEdge;
621 assert(leftVert->head()[1] <= vert->head()[1]);
622 assert(rightVert->head()[1] <= vert->head()[1]);
623 directedLine* maxVert = (leftVert->head()[1] > rightVert->head()[1])? leftVert:rightVert;
624 Int found=0;
625 for(j=i-1; j>=0; j--)
626 {
627 if(sortedVertices[j]->getHead()->head()[1] < maxVert->head()[1])
628 break;
629 if(sweepRangeEqual(ranges[i], ranges[j]))
630 {
631 found = 1;
632 break;
633 }
634 }
635 if(found)
636 diagonal_vertices[k++] = sortedVertices[j]->getHead();
637 else
638 diagonal_vertices[k++] = maxVert;
639 }
640 }
641 num_diagonals = k/2;
642}
643
644
645
646
648{
649//printf("enter mc_partitionY\n");
650 Int total_num_chains = 0;
652 monoChain** array = loopList->toArrayAllLoops(total_num_chains);
653
654 if(total_num_chains<=2) //there is just one single monotone polygon
655 {
656 loopList->deleteLoopList();
657 free(array);
658 *retSampledLines = NULL;
659 return polygons;
660 }
661
662//loopList->printAllLoops();
663//printf("total_num_chains=%i\n", total_num_chains);
664 quicksort( (void**)array, 0, total_num_chains-1, (Int (*)(void*, void*))compChainHeadInY);
665//printf("after quicksort\n");
666
667 sweepRange** ranges = (sweepRange**)malloc(sizeof(sweepRange*) * (total_num_chains));
668 assert(ranges);
669
670 if(MC_sweepY(total_num_chains, array, ranges))
671 {
672 loopList->deleteLoopList();
673 free(array);
674 *retSampledLines = NULL;
675 return NULL;
676 }
677//printf("after MC_sweepY\n");
678
679
680 Int num_diagonals;
681 /*number diagonals is < total_num_edges*total_num_edges*/
682 directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_chains*2/*total_num_edges*/);
683 assert(diagonal_vertices);
684
685//printf("before call MC_findDiagonales\n");
686
687 MC_findDiagonals(total_num_chains, array, ranges, num_diagonals, diagonal_vertices);
688//printf("after call MC_findDia, num_diagnla=%i\n", num_diagonals);
689
690 directedLine* ret_polygons = polygons;
691 sampledLine* newSampledLines = NULL;
692 Int i,k;
693
694 num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
695
696
697
698//drawDiagonals(num_diagonals, diagonal_vertices);
699//printf("diagoanls are \n");
700//for(i=0; i<num_diagonals; i++)
701// {
702// printf("(%f,%f)\n", diagonal_vertices[2*i]->head()[0], diagonal_vertices[2*i]->head()[1]);
703// printf("**(%f,%f)\n", diagonal_vertices[2*i+1]->head()[0], diagonal_vertices[2*i+1]->head()[1]);
704// }
705
706 Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals);
707 for(i=0; i<num_diagonals; i++)
708 removedDiagonals[i] = 0;
709// printf("first pass\n");
710
711
712 for(i=0,k=0; i<num_diagonals; i++,k+=2)
713 {
714
715
716 directedLine* v1=diagonal_vertices[k];
717 directedLine* v2=diagonal_vertices[k+1];
718 directedLine* ret_p1;
719 directedLine* ret_p2;
720
721 /*we ahve to determine whether v1 and v2 belong to the same polygon before
722 *their structure are modified by connectDiagonal().
723 */
724/*
725 directedLine *root1 = v1->findRoot();
726 directedLine *root2 = v2->findRoot();
727 assert(root1);
728 assert(root2);
729*/
730
733
734 if(root1 != root2)
735 {
736
737 removedDiagonals[i] = 1;
738 sampledLine* generatedLine;
739
740
741
742 v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
743
744
745
746 newSampledLines = generatedLine->insert(newSampledLines);
747/*
748 ret_polygons = ret_polygons->cutoffPolygon(root1);
749
750 ret_polygons = ret_polygons->cutoffPolygon(root2);
751 ret_polygons = ret_p1->insertPolygon(ret_polygons);
752root1->rootLinkSet(ret_p1);
753root2->rootLinkSet(ret_p1);
754ret_p1->rootLinkSet(NULL);
755ret_p2->rootLinkSet(ret_p1);
756*/
757 ret_polygons = ret_polygons->cutoffPolygon(root2);
758
759
760
761root2->rootLinkSet(root1);
762ret_p1->rootLinkSet(root1);
763ret_p2->rootLinkSet(root1);
764
765 /*now that we have connected the diagonal v1 and v2,
766 *we have to check those unprocessed diagonals which
767 *have v1 or v2 as an end point. Notice that the head of v1
768 *has the same coodinates as the head of v2->prev, and the head of
769 *v2 has the same coordinate as the head of v1->prev.
770 *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid
771 *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
772 *replaced by (v2->prev, x), that is, x is on the left of
773 * v2->prev->prev->head, v2->prev->head, v2->prev->tail.
774 */
775 Int ii, kk;
776 for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2)
777 if( removedDiagonals[ii]==0)
778 {
779 directedLine* d1=diagonal_vertices[kk];
780 directedLine* d2=diagonal_vertices[kk+1];
781 /*check d1, and replace diagonal_vertices[kk] if necessary*/
782 if(d1 == v1) {
783 /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/
784 if(! pointLeft2Lines(v1->getPrev()->head(),
785 v1->head(), v1->tail(), d2->head()))
786 {
787/*
788 assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
789 v2->getPrev()->head(),
790 v2->getPrev()->tail(), d2->head()));
791*/
792 diagonal_vertices[kk] = v2->getPrev();
793 }
794 }
795 if(d1 == v2) {
796 /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/
797 if(! pointLeft2Lines(v2->getPrev()->head(),
798 v2->head(), v2->tail(), d2->head()))
799 {
800/*
801 assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
802 v1->getPrev()->head(),
803 v1->getPrev()->tail(), d2->head()));
804*/
805 diagonal_vertices[kk] = v1->getPrev();
806 }
807 }
808 /*check d2 and replace diagonal_vertices[k+1] if necessary*/
809 if(d2 == v1) {
810 /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/
811 if(! pointLeft2Lines(v1->getPrev()->head(),
812 v1->head(), v1->tail(), d1->head()))
813 {
814/* assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
815 v2->getPrev()->head(),
816 v2->getPrev()->tail(), d1->head()));
817*/
818 diagonal_vertices[kk+1] = v2->getPrev();
819 }
820 }
821 if(d2 == v2) {
822 /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/
823 if(! pointLeft2Lines(v2->getPrev()->head(),
824 v2->head(), v2->tail(), d1->head()))
825 {
826/* assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
827 v1->getPrev()->head(),
828 v1->getPrev()->tail(), d1->head()));
829*/
830 diagonal_vertices[kk+1] = v1->getPrev();
831 }
832 }
833 }
834}/*end if (root1 not equal to root 2)*/
835}
836
837 /*second pass, now all diagoals should belong to the same polygon*/
838//printf("second pass: \n");
839
840// for(i=0; i<num_diagonals; i++)
841// printf("%i ", removedDiagonals[i]);
842
843
844 for(i=0,k=0; i<num_diagonals; i++, k += 2)
845 if(removedDiagonals[i] == 0)
846 {
847
848
849 directedLine* v1=diagonal_vertices[k];
850 directedLine* v2=diagonal_vertices[k+1];
851
852
853
854 directedLine* ret_p1;
855 directedLine* ret_p2;
856
857 /*we ahve to determine whether v1 and v2 belong to the same polygon before
858 *their structure are modified by connectDiagonal().
859 */
860 directedLine *root1 = v1->findRoot();
861/*
862 directedLine *root2 = v2->findRoot();
863
864
865
866 assert(root1);
867 assert(root2);
868 assert(root1 == root2);
869 */
870 sampledLine* generatedLine;
871
872
873
874 v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
875 newSampledLines = generatedLine->insert(newSampledLines);
876
877 ret_polygons = ret_polygons->cutoffPolygon(root1);
878
879 ret_polygons = ret_p1->insertPolygon(ret_polygons);
880
881 ret_polygons = ret_p2->insertPolygon(ret_polygons);
882
883
884
885 for(Int j=i+1; j<num_diagonals; j++)
886 {
887 if(removedDiagonals[j] ==0)
888 {
889
890 directedLine* temp1=diagonal_vertices[2*j];
891 directedLine* temp2=diagonal_vertices[2*j+1];
892 if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2)
893 if(! temp1->samePolygon(temp1, temp2))
894 {
895 /*if temp1 and temp2 are in different polygons,
896 *then one of them must be v1 or v2.
897 */
898
899
900
901 assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2);
902 if(temp1==v1)
903 {
904 diagonal_vertices[2*j] = v2->getPrev();
905 }
906 if(temp2==v1)
907 {
908 diagonal_vertices[2*j+1] = v2->getPrev();
909 }
910 if(temp1==v2)
911 {
912 diagonal_vertices[2*j] = v1->getPrev();
913 }
914 if(temp2==v2)
915 {
916 diagonal_vertices[2*j+1] = v1->getPrev();
917 }
918 }
919 }
920 }
921
922 }
923
924
925 //clean up
926 loopList->deleteLoopList();
927 free(array);
928 free(ranges);
929 free(diagonal_vertices);
930 free(removedDiagonals);
931
932 *retSampledLines = newSampledLines;
933 return ret_polygons;
934}
935
936
struct outqueuenode * head
Definition: adnsresfilter.c:66
#define index(s, c)
Definition: various.h:29
directedLine * getPrev()
Definition: directedLine.h:73
directedLine * cutoffPolygon(directedLine *p)
void rootLinkSet(directedLine *r)
Definition: directedLine.h:155
directedLine * insertPolygon(directedLine *newpolygon)
directedLine * findRoot()
directedLine * rootLinkFindRoot()
Int samePolygon(directedLine *v1, directedLine *v2)
Int compInY(directedLine *nl)
directedLine * getNext()
Definition: directedLine.h:74
Real * head()
Real * tail()
Definition: list.h:37
Real chainIntersectHoriz(Real y)
Definition: monoChain.cc:208
directedLine * getHead()
Definition: monoChain.h:66
void printAllLoops()
Definition: monoChain.cc:443
directedLine * chainTail
Definition: monoChain.h:43
monoChain * getPrev()
Definition: monoChain.h:65
directedLine * find(Real y)
Definition: monoChain.cc:393
monoChain ** toArrayAllLoops(Int &num_chains)
Definition: monoChain.cc:174
directedLine * chainHead
Definition: monoChain.h:42
monoChain * prev
Definition: monoChain.h:45
Real minX
Definition: monoChain.h:50
monoChain * next
Definition: monoChain.h:44
monoChain(directedLine *cHead, directedLine *cTail)
Definition: monoChain.cc:90
Int toArraySingleLoop(monoChain **array, Int index)
Definition: monoChain.cc:163
Int isIncrease
Definition: monoChain.h:51
void printChainLoop()
Definition: monoChain.cc:432
void insert(monoChain *nc)
Definition: monoChain.cc:134
Int numChainsAllLoops()
Definition: monoChain.cc:198
Real maxY
Definition: monoChain.h:50
Int numChainsSingleLoop()
Definition: monoChain.cc:187
Real minY
Definition: monoChain.h:50
monoChain * nextPolygon
Definition: monoChain.h:46
void setNextPolygon(monoChain *np)
Definition: monoChain.h:63
directedLine * current
Definition: monoChain.h:55
Int isKey
Definition: monoChain.h:82
Real maxX
Definition: monoChain.h:50
void deleteLoop()
Definition: monoChain.cc:142
Real keyY
Definition: monoChain.h:83
void printOneChain()
Definition: monoChain.cc:422
void deleteLoopList()
Definition: monoChain.cc:153
sampledLine * insert(sampledLine *nline)
Definition: sampledLine.cc:53
#define free
Definition: debug_ros.c:5
#define malloc
Definition: debug_ros.c:4
int Int
Definition: definitions.h:37
float Real
Definition: definitions.h:36
Int compV2InY(Real A[2], Real B[2])
#define NULL
Definition: types.h:112
#define assert(x)
Definition: debug.h:53
#define printf
Definition: freeldr.h:97
const GLdouble * v
Definition: gl.h:2040
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
GLAPI void GLAPIENTRY glBegin(GLenum mode)
#define GL_LINE
Definition: gl.h:266
GLAPI void GLAPIENTRY glEnd(void)
GLAPI void GLAPIENTRY glVertex2fv(const GLfloat *v)
GLuint index
Definition: glext.h:6031
GLfloat GLfloat v1
Definition: glext.h:6062
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
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
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
#define stderr
Definition: stdio.h:100
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
monoChain * directedLineLoopListToMonoChainLoopList(directedLine *list)
Definition: monoChain.cc:273
Int isCusp(directedLine *v)
Definition: partitionY.cc:100
Int MC_sweepY(Int nVertices, monoChain **sortedVertices, sweepRange **ret_ranges)
Definition: monoChain.cc:451
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: monoChain.cc:296
Int deleteRepeatDiagonals(Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
Definition: partitionY.cc:386
Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
Definition: monoChain.cc:79
directedLine * MC_partitionY(directedLine *polygons, sampledLine **retSampledLines)
Definition: monoChain.cc:647
void MC_findDiagonals(Int total_num_edges, monoChain **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
Definition: monoChain.cc:567
#define min(a, b)
Definition: monoChain.cc:55
monoChain * directedLineLoopToMonoChainLoop(directedLine *loop)
Definition: monoChain.cc:232
Int compChains(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:376
static int compChainHeadInY(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:85
#define max(a, b)
Definition: monoChain.cc:52
int k
Definition: mpi.c:3369
sweepRange * sweepRangeMake(directedLine *left, Int leftType, directedLine *right, Int rightType)
Definition: partitionY.cc:150
Int cuspType(directedLine *v)
Definition: partitionY.cc:142
Int isBelow(directedLine *v, directedLine *e)
Definition: partitionY.cc:73
Int sweepRangeEqual(sweepRange *src1, sweepRange *src2)
Definition: partitionY.cc:167
Int isAbove(directedLine *v, directedLine *e)
Definition: partitionY.cc:89
Int pointLeft2Lines(Real A[2], Real B[2], Real C[2], Real P[2])
Definition: polyUtil.cc:78
void quicksort(void *v[], int left, int right, int(*comp)(void *, void *))
Definition: quicksort.cc:62
static calc_node_t temp
Definition: rpn_ieee.c:38
#define exit(n)
Definition: config.h:202
void TreeNodeDeleteSingleNode(treeNode *node)
Definition: searchTree.cc:57
treeNode * TreeNodePredecessor(treeNode *node)
Definition: searchTree.cc:266
treeNode * TreeNodeFind(treeNode *tree, void *key, int(*compkey)(void *, void *))
Definition: searchTree.cc:92
treeNode * TreeNodeMake(void *key)
Definition: searchTree.cc:46
treeNode * TreeNodeSuccessor(treeNode *node)
Definition: searchTree.cc:244
treeNode * TreeNodeInsert(treeNode *root, treeNode *newnode, int(*compkey)(void *, void *))
Definition: searchTree.cc:106
void TreeNodeDeleteWholeTree(treeNode *node)
Definition: searchTree.cc:62
directedLine * right
Definition: partitionY.h:73
directedLine * left
Definition: partitionY.h:71
void * key
Definition: searchTree.h:37
int ret
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG x2
Definition: winddi.h:3710
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG y1
Definition: winddi.h:3709
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3708
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG _In_ LONG y2
Definition: winddi.h:3711