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

Go to the source code of this file.

Classes

class  monoChain
 

Functions

monoChaindirectedLineLoopToMonoChainLoop (directedLine *loop)
 
monoChaindirectedLineLoopListToMonoChainLoopList (directedLine *list)
 
Int MC_sweepY (Int nVertices, monoChain **sortedVertices, sweepRange **ret_ranges)
 
void MC_findDiagonals (Int total_num_edges, monoChain **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
 
directedLineMC_partitionY (directedLine *polygons, sampledLine **retSampledLines)
 

Function Documentation

◆ directedLineLoopListToMonoChainLoopList()

monoChain * directedLineLoopListToMonoChainLoopList ( directedLine list)

Definition at line 273 of file monoChain.cc.

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}
Definition: list.h:37
void setNextPolygon(monoChain *np)
Definition: monoChain.h:63
#define NULL
Definition: types.h:112
monoChain * directedLineLoopToMonoChainLoop(directedLine *loop)
Definition: monoChain.cc:232
static calc_node_t temp
Definition: rpn_ieee.c:38

Referenced by MC_partitionY().

◆ directedLineLoopToMonoChainLoop()

monoChain * directedLineLoopToMonoChainLoop ( directedLine loop)

Definition at line 232 of file monoChain.cc.

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}
directedLine * getNext()
Definition: directedLine.h:74
#define assert(x)
Definition: debug.h:53
Int isCusp(directedLine *v)
Definition: partitionY.cc:100
int ret

Referenced by directedLineLoopListToMonoChainLoopList().

◆ MC_findDiagonals()

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

Definition at line 567 of file monoChain.cc.

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}
directedLine * getPrev()
Definition: directedLine.h:73
Real * head()
directedLine * getHead()
Definition: monoChain.h:66
int Int
Definition: definitions.h:37
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
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: monoChain.cc:296
int k
Definition: mpi.c:3369
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
directedLine * right
Definition: partitionY.h:73
directedLine * left
Definition: partitionY.h:71

Referenced by MC_partitionY().

◆ MC_partitionY()

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

Definition at line 647 of file monoChain.cc.

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}
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)
monoChain ** toArrayAllLoops(Int &num_chains)
Definition: monoChain.cc:174
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
GLfloat GLfloat v1
Definition: glext.h:6062
GLfloat GLfloat GLfloat v2
Definition: glext.h:6063
monoChain * directedLineLoopListToMonoChainLoopList(directedLine *list)
Definition: monoChain.cc:273
Int MC_sweepY(Int nVertices, monoChain **sortedVertices, sweepRange **ret_ranges)
Definition: monoChain.cc:451
Int deleteRepeatDiagonals(Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
Definition: partitionY.cc:386
void MC_findDiagonals(Int total_num_edges, monoChain **sortedVertices, sweepRange **ranges, Int &num_diagonals, directedLine **diagonal_vertices)
Definition: monoChain.cc:567
static int compChainHeadInY(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:85
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

Referenced by Subdivider::drawSurfaces().

◆ MC_sweepY()

Int MC_sweepY ( Int  nVertices,
monoChain **  sortedVertices,
sweepRange **  ret_ranges 
)

Definition at line 451 of file monoChain.cc.

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}
monoChain * getPrev()
Definition: monoChain.h:65
Int isKey
Definition: monoChain.h:82
Real keyY
Definition: monoChain.h:83
float Real
Definition: definitions.h:36
#define stderr
Definition: stdio.h:100
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
Int compChains(monoChain *mc1, monoChain *mc2)
Definition: monoChain.cc:376
sweepRange * sweepRangeMake(directedLine *left, Int leftType, directedLine *right, Int rightType)
Definition: partitionY.cc:150
Int cuspType(directedLine *v)
Definition: partitionY.cc:142
#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 MC_partitionY().