ReactOS 0.4.16-dev-401-g45b008d
monoChain.cc File Reference
#include "gluos.h"
#include "zlassert.h"
#include "monoChain.h"
#include "quicksort.h"
#include "searchTree.h"
#include "polyUtil.h"
Include dependency graph for monoChain.cc:

Go to the source code of this file.

Macros

#define max(a, b)   ((a>b)? a:b)
 
#define min(a, b)   ((a>b)? b:a)
 

Functions

Int isCusp (directedLine *v)
 
Int deleteRepeatDiagonals (Int num_diagonals, directedLine **diagonal_vertices, directedLine **new_vertices)
 
Real intersectHoriz (Real x1, Real y1, Real x2, Real y2, Real y)
 
static int compChainHeadInY (monoChain *mc1, monoChain *mc2)
 
monoChaindirectedLineLoopToMonoChainLoop (directedLine *loop)
 
monoChaindirectedLineLoopListToMonoChainLoopList (directedLine *list)
 
static Int compEdges (directedLine *e1, directedLine *e2)
 
Int compChains (monoChain *mc1, monoChain *mc2)
 
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)
 

Macro Definition Documentation

◆ max

#define max (   a,
  b 
)    ((a>b)? a:b)

Definition at line 52 of file monoChain.cc.

◆ min

#define min (   a,
  b 
)    ((a>b)? b:a)

Function Documentation

◆ compChainHeadInY()

static int compChainHeadInY ( monoChain mc1,
monoChain mc2 
)
static

Definition at line 85 of file monoChain.cc.

86{
87 return compV2InY(mc1->getHead()->head(), mc2->getHead()->head());
88}
Real * head()
directedLine * getHead()
Definition: monoChain.h:66
Int compV2InY(Real A[2], Real B[2])

Referenced by MC_partitionY().

◆ compChains()

Int compChains ( monoChain mc1,
monoChain mc2 
)

Definition at line 376 of file monoChain.cc.

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}
directedLine * find(Real y)
Definition: monoChain.cc:393
Int isKey
Definition: monoChain.h:82
Real keyY
Definition: monoChain.h:83
float Real
Definition: definitions.h:36
#define assert(x)
Definition: debug.h:53
GLint GLint GLint GLint GLint GLint y
Definition: gl.h:1548
static Int compEdges(directedLine *e1, directedLine *e2)
Definition: monoChain.cc:296

Referenced by MC_sweepY().

◆ compEdges()

static Int compEdges ( directedLine e1,
directedLine e2 
)
static

Definition at line 296 of file monoChain.cc.

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}
Real * tail()
Real intersectHoriz(Real x1, Real y1, Real x2, Real y2, Real y)
Definition: monoChain.cc:79
#define min(a, b)
Definition: monoChain.cc:55
#define max(a, b)
Definition: monoChain.cc:52
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG x2
Definition: winddi.h:3710
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG x1
Definition: winddi.h:3708

Referenced by compChains(), and MC_findDiagonals().

◆ deleteRepeatDiagonals()

Int deleteRepeatDiagonals ( Int  num_diagonals,
directedLine **  diagonal_vertices,
directedLine **  new_vertices 
)

Definition at line 386 of file partitionY.cc.

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}
#define index(s, c)
Definition: various.h:29
r l[0]
Definition: byte_order.h:168
int Int
Definition: definitions.h:37
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 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

Referenced by DBGfindDiagonals(), MC_partitionY(), and partitionY().

◆ 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
Int isCusp(directedLine *v)
Definition: partitionY.cc:100
int ret

Referenced by directedLineLoopListToMonoChainLoopList().

◆ intersectHoriz()

Real intersectHoriz ( Real  x1,
Real  y1,
Real  x2,
Real  y2,
Real  y 
)
inline

Definition at line 79 of file monoChain.cc.

80{
81 return ((y2==y1)? (x1+x2)*0.5 : x1 + ((y-y1)/(y2-y1)) * (x2-x1));
82}
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG y1
Definition: winddi.h:3709
_In_ CLIPOBJ _In_ BRUSHOBJ _In_ LONG _In_ LONG _In_ LONG _In_ LONG y2
Definition: winddi.h:3711

Referenced by monoChain::chainIntersectHoriz(), and compEdges().

◆ isCusp()

Int isCusp ( directedLine v)

Definition at line 100 of file partitionY.cc.

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}
Definition: ehthrow.cxx:93
Definition: ehthrow.cxx:54
Definition: terminate.cpp:24
const GLdouble * v
Definition: gl.h:2040
Int isBelow(directedLine *v, directedLine *e)
Definition: partitionY.cc:73
Int isAbove(directedLine *v, directedLine *e)
Definition: partitionY.cc:89

Referenced by cuspType(), and directedLineLoopToMonoChainLoop().

◆ 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
Int sweepRangeEqual(sweepRange *src1, sweepRange *src2)
Definition: partitionY.cc:167
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
#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().