ReactOS 0.4.15-dev-6042-g2eb6700
partitionY.h File Reference
#include "directedLine.h"
Include dependency graph for partitionY.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes

struct  sweepRange
 

Typedefs

typedef struct sweepRange sweepRange
 

Functions

Int isBelow (directedLine *v, directedLine *e)
 
Int isAbove (directedLine *v, directedLine *e)
 
Int cuspType (directedLine *v)
 
sweepRangesweepRangeMake (directedLine *left, Int leftType, directedLine *right, Int rightType)
 
void sweepRangeDelete (sweepRange *range)
 
Int sweepRangeEqual (sweepRange *sr1, sweepRange *sr2)
 
void sweepY (Int nVertices, directedLine **sortedVerteces, sweepRange **ret_ranges)
 
directedLinepartitionY (directedLine *polygons, sampledLine **retSampledLines)
 
void findDiagonals (Int total_num_edges, directedLine **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
 
directedLine ** DBGfindDiagonals (directedLine *polygons, Int &num_diagonals)
 

Typedef Documentation

◆ sweepRange

Function Documentation

◆ cuspType()

Int cuspType ( directedLine v)

Definition at line 142 of file partitionY.cc.

143{
144 if(! isCusp(v)) return 0;
145 else if(isReflex(v)) return 1;
146 else
147 return 2;
148}
const GLdouble * v
Definition: gl.h:2040
Int isReflex(directedLine *v)
Definition: partitionY.cc:122
Int isCusp(directedLine *v)
Definition: partitionY.cc:100

Referenced by MC_sweepY().

◆ DBGfindDiagonals()

directedLine ** DBGfindDiagonals ( directedLine polygons,
Int num_diagonals 
)

Definition at line 426 of file partitionY.cc.

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}
directedLine ** toArrayAllPolygons(Int &total_num_edges)
#define malloc
Definition: debug_ros.c:4
int Int
Definition: definitions.h:37
#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
Int deleteRepeatDiagonals(Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
Definition: partitionY.cc:386
void sweepY(Int nVertices, directedLine **sortedVertices, sweepRange **ret_ranges)
Definition: partitionY.cc:722
static Int compInY(directedLine *v1, directedLine *v2)
Definition: partitionY.cc:328
void quicksort(void *v[], int left, int right, int(*comp)(void *, void *))
Definition: quicksort.cc:62

◆ findDiagonals()

void findDiagonals ( Int  total_num_edges,
directedLine **  sortedVertices,
sweepRange **  ranges,
Int num_diagonals,
directedLine **  diagonal_vertices 
)

Definition at line 333 of file partitionY.cc.

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/*
345printf("find i=%i\n", i);
346printf("the vertex is\n");
347vert->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}
directedLine * getPrev()
Definition: directedLine.h:73
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
int k
Definition: mpi.c:3369
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: partitionY.cc:246
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

Referenced by DBGfindDiagonals(), and partitionY().

◆ isAbove()

Int isAbove ( directedLine v,
directedLine e 
)

Definition at line 89 of file partitionY.cc.

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}
float Real
Definition: definitions.h:36
#define e
Definition: ke_i.h:82
static Int compVertInY(Real A[2], Real B[2])
Definition: partitionY.cc:58

Referenced by findDiagonals(), isCusp(), MC_findDiagonals(), MC_sweepY(), and sweepY().

◆ isBelow()

Int isBelow ( directedLine v,
directedLine e 
)

Definition at line 73 of file partitionY.cc.

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}

Referenced by findDiagonals(), isCusp(), MC_findDiagonals(), MC_sweepY(), and sweepY().

◆ partitionY()

directedLine * partitionY ( directedLine polygons,
sampledLine **  retSampledLines 
)

Definition at line 447 of file partitionY.cc.

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
486num_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
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);
538root1->rootLinkSet(ret_p1);
539root2->rootLinkSet(ret_p1);
540ret_p1->rootLinkSet(NULL);
541ret_p2->rootLinkSet(ret_p1);
542*/
543 ret_polygons = ret_polygons->cutoffPolygon(root2);
544
545
546
547root2->rootLinkSet(root1);
548ret_p1->rootLinkSet(root1);
549ret_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}
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)
Real * head()
sampledLine * insert(sampledLine *nline)
Definition: sampledLine.cc:53
#define free
Definition: debug_ros.c:5
#define NULL
Definition: types.h:112
GLfloat GLfloat v1
Definition: glext.h:6062
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
Int pointLeft2Lines(Real A[2], Real B[2], Real C[2], Real P[2])
Definition: polyUtil.cc:78

◆ sweepRangeDelete()

void sweepRangeDelete ( sweepRange range)

Definition at line 162 of file partitionY.cc.

163{
164 free(range);
165}
GLenum GLint * range
Definition: glext.h:7539

◆ sweepRangeEqual()

Int sweepRangeEqual ( sweepRange sr1,
sweepRange sr2 
)

Definition at line 167 of file partitionY.cc.

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}

Referenced by findDiagonals(), and MC_findDiagonals().

◆ sweepRangeMake()

sweepRange * sweepRangeMake ( directedLine left,
Int  leftType,
directedLine right,
Int  rightType 
)

Definition at line 150 of file partitionY.cc.

152{
154 assert(ret);
155 ret->left = left;
156 ret->leftType = leftType;
157 ret->right = right;
158 ret->rightType = rightType;
159 return ret;
160}
GLdouble GLdouble right
Definition: glext.h:10859
GLint left
Definition: glext.h:7726
int ret

Referenced by MC_sweepY(), and sweepY().

◆ sweepY()

void sweepY ( Int  nVertices,
directedLine **  sortedVerteces,
sweepRange **  ret_ranges 
)

Definition at line 722 of file partitionY.cc.

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}
void printSingle()
#define printf
Definition: freeldr.h:94
#define stderr
Definition: stdio.h:100
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
sweepRange * sweepRangeMake(directedLine *left, Int leftType, directedLine *right, Int rightType)
Definition: partitionY.cc:150
#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
void * key
Definition: searchTree.h:37

Referenced by DBGfindDiagonals(), and partitionY().