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)
sweepRange *	sweepRangeMake (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)
directedLine *	partitionY (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

typedef struct sweepRange sweepRange

Function Documentation

cuspType()

Int cuspType

(

directedLine *

v

)

Definition at line 142 of file partitionY.cc.

{
  if(! isCusp(v)) return 0;
  else if(isReflex(v)) return 1;
  else
    return 2;
}

Referenced by MC_sweepY().

DBGfindDiagonals()

directedLine ** DBGfindDiagonals	(	directedLine *	polygons,
		Int &	num_diagonals
	)

Definition at line 426 of file partitionY.cc.

{
  Int total_num_edges = 0;
  directedLine** array = polygons->toArrayAllPolygons(total_num_edges);
  quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void*, void*)) compInY);
  sweepRange** ranges = (sweepRange**) malloc(sizeof(sweepRange*) * total_num_edges);
  assert(ranges);
 
  sweepY(total_num_edges, array, ranges);
 
 directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges);
  assert(diagonal_vertices);
  findDiagonals(total_num_edges, array, ranges, num_diagonals, diagonal_vertices);
 
  num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
  return diagonal_vertices;
 
}

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.

{
  Int i,j,k;
 
  k=0;
 
  for(i=0; i<total_num_edges; i++)
    {
      directedLine* vert =sortedVertices[i];
      directedLine* thisEdge = vert;
      directedLine* prevEdge = vert->getPrev();
/*
printf("find i=%i\n", i);            
printf("the vertex is\n");
vert->printSingle();
*/
      if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge) && compEdges(prevEdge, thisEdge)<0)
    {
      /*this is an upward interior cusp*/
      diagonal_vertices[k++] = vert;
 
      for(j=i+1; j<total_num_edges; j++)
        if(sweepRangeEqual(ranges[i], ranges[j]))
          {
        diagonal_vertices[k++] = sortedVertices[j];
        break;
          }
      assert(j<total_num_edges);
 
 
    }
      else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge) && compEdges(prevEdge, thisEdge)>0)
    {
      /*this is an downward interior cusp*/
      diagonal_vertices[k++] = vert;
      for(j=i-1; j>=0; j--)
        if(sweepRangeEqual(ranges[i], ranges[j]))
          {
        diagonal_vertices[k++] = sortedVertices[j];
        break;
          }
/*    printf("j=%i\n", j);*/
      assert(j>=0);
 
 
 
    }
    }
  num_diagonals = k/2;
}

Referenced by DBGfindDiagonals(), and partitionY().

isAbove()

Int isAbove	(	directedLine *	v,
		directedLine *	e
	)

Definition at line 89 of file partitionY.cc.

{
  Real* vert = v->head();
  if(   compVertInY(e->head(), vert) != -1 
     && compVertInY(e->tail(), vert) != -1
     )
    return 1;
  else
    return 0;
}

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.

{
  Real* vert = v->head();
  if(   compVertInY(e->head(), vert) != 1 
     && compVertInY(e->tail(), vert) != 1
     )
    return 1;
  else
    return 0;
}

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.

{
  Int total_num_edges = 0;
  directedLine** array = polygons->toArrayAllPolygons(total_num_edges);
 
  quicksort( (void**)array, 0, total_num_edges-1, (Int (*)(void*, void*)) compInY);
 
  sweepRange** ranges = (sweepRange**) malloc(sizeof(sweepRange*) * (total_num_edges));
  assert(ranges);
 
 
 
  sweepY(total_num_edges, array, ranges);
 
 
 
  /*the diagonal vertices are stored as:
   *v0-v1: 1st diagonal
   *v2-v3: 2nd diagonal
   *v5-v5: 3rd diagonal
   *...
   */
 
 
  Int num_diagonals;
  /*number diagonals is < total_num_edges*total_num_edges*/
  directedLine** diagonal_vertices = (directedLine**) malloc(sizeof(directedLine*) * total_num_edges*2/*total_num_edges*/);
  assert(diagonal_vertices);
 
 
 
  findDiagonals(total_num_edges, array, ranges, num_diagonals, diagonal_vertices);
 
 
 
  directedLine* ret_polygons = polygons;
  sampledLine* newSampledLines = NULL;
  Int i,k;
 
num_diagonals=deleteRepeatDiagonals(num_diagonals, diagonal_vertices, diagonal_vertices);
 
 
 
  Int *removedDiagonals=(Int*)malloc(sizeof(Int) * num_diagonals);
  for(i=0; i<num_diagonals; i++)
    removedDiagonals[i] = 0;
 
 
 
 
 
  for(i=0,k=0; i<num_diagonals; i++,k+=2)
    {
 
 
      directedLine* v1=diagonal_vertices[k];
      directedLine* v2=diagonal_vertices[k+1];
      directedLine* ret_p1;
      directedLine* ret_p2;
      
      /*we ahve to determine whether v1 and v2 belong to the same polygon before
       *their structure are modified by connectDiagonal().
       */
/*
      directedLine *root1 = v1->findRoot();
      directedLine *root2 = v2->findRoot();
      assert(root1);      
      assert(root2);
*/
 
directedLine*  root1 = v1->rootLinkFindRoot();
directedLine*  root2 = v2->rootLinkFindRoot();
 
      if(root1 != root2)
    {
 
      removedDiagonals[i] = 1;
      sampledLine* generatedLine;
 
 
 
      v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
 
 
 
      newSampledLines = generatedLine->insert(newSampledLines);
/*
      ret_polygons = ret_polygons->cutoffPolygon(root1);
 
      ret_polygons = ret_polygons->cutoffPolygon(root2);
      ret_polygons = ret_p1->insertPolygon(ret_polygons);
root1->rootLinkSet(ret_p1);
root2->rootLinkSet(ret_p1);
ret_p1->rootLinkSet(NULL);
ret_p2->rootLinkSet(ret_p1);
*/
      ret_polygons = ret_polygons->cutoffPolygon(root2);
 
 
 
root2->rootLinkSet(root1);
ret_p1->rootLinkSet(root1);
ret_p2->rootLinkSet(root1);
 
       /*now that we have connected the diagonal v1 and v2, 
        *we have to check those unprocessed diagonals which 
        *have v1 or v2 as an end point. Notice that the head of v1
        *has the same coodinates as the head of v2->prev, and the head of
        *v2 has the same coordinate as the head of v1->prev. 
        *Suppose these is a diagonal (v1, x). If (v1,x) is still a valid
        *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  
        *replaced by (v2->prev, x), that is, x is on the left of 
        * v2->prev->prev->head, v2->prev->head, v2->prev->tail.
        */
        Int ii, kk;
        for(ii=0, kk=0; ii<num_diagonals; ii++, kk+=2)
      if( removedDiagonals[ii]==0)
        {
          directedLine* d1=diagonal_vertices[kk];
          directedLine* d2=diagonal_vertices[kk+1];
          /*check d1, and replace diagonal_vertices[kk] if necessary*/
          if(d1 == v1) {
        /*check if d2 is to left of v1->prev->head:v1->head:v1->tail*/
        if(! pointLeft2Lines(v1->getPrev()->head(), 
                     v1->head(), v1->tail(), d2->head()))
          {
/*
            assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
                       v2->getPrev()->head(), 
                       v2->getPrev()->tail(), d2->head()));
*/
            diagonal_vertices[kk] = v2->getPrev();
          }
          }
          if(d1 == v2) {
        /*check if d2 is to left of v2->prev->head:v2->head:v2->tail*/
        if(! pointLeft2Lines(v2->getPrev()->head(),
                     v2->head(), v2->tail(), d2->head()))
          {
/*
            assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
                       v1->getPrev()->head(),
                       v1->getPrev()->tail(), d2->head()));
*/
            diagonal_vertices[kk] = v1->getPrev();
          }
          }
          /*check d2 and replace diagonal_vertices[k+1] if necessary*/
          if(d2 == v1) {
        /*check if d1 is to left of v1->prev->head:v1->head:v1->tail*/
        if(! pointLeft2Lines(v1->getPrev()->head(), 
                     v1->head(), v1->tail(), d1->head()))
          {
/*          assert(pointLeft2Lines(v2->getPrev()->getPrev()->head(),
                       v2->getPrev()->head(), 
                       v2->getPrev()->tail(), d1->head()));
*/
            diagonal_vertices[kk+1] = v2->getPrev();
          }
          }
          if(d2 == v2) {
        /*check if d1 is to left of v2->prev->head:v2->head:v2->tail*/
        if(! pointLeft2Lines(v2->getPrev()->head(),
                     v2->head(), v2->tail(), d1->head()))
          {
/*          assert(pointLeft2Lines(v1->getPrev()->getPrev()->head(),
                       v1->getPrev()->head(),
                       v1->getPrev()->tail(), d1->head()));
*/
            diagonal_vertices[kk+1] = v1->getPrev();
          }
          }
        }                                  
}/*end if (root1 not equal to root 2)*/
}
 
  /*second pass,  now all diagoals should belong to the same polygon*/
 
 
 
  for(i=0,k=0; i<num_diagonals; i++, k += 2)
    if(removedDiagonals[i] == 0) 
      {
 
 
    directedLine* v1=diagonal_vertices[k];
    directedLine* v2=diagonal_vertices[k+1];
 
 
 
    directedLine* ret_p1;
    directedLine* ret_p2;
 
    /*we ahve to determine whether v1 and v2 belong to the same polygon before
     *their structure are modified by connectDiagonal().
     */
    directedLine *root1 = v1->findRoot();
/*
    directedLine *root2 = v2->findRoot();
 
 
 
    assert(root1);      
    assert(root2);      
    assert(root1 == root2);
  */    
    sampledLine* generatedLine;
 
 
 
    v1->connectDiagonal(v1,v2, &ret_p1, &ret_p2, &generatedLine, ret_polygons);
    newSampledLines = generatedLine->insert(newSampledLines);
 
    ret_polygons = ret_polygons->cutoffPolygon(root1);
 
    ret_polygons = ret_p1->insertPolygon(ret_polygons);
 
    ret_polygons = ret_p2->insertPolygon(ret_polygons);
 
 
 
    for(Int j=i+1; j<num_diagonals; j++) 
      {
        if(removedDiagonals[j] ==0)
          {
 
        directedLine* temp1=diagonal_vertices[2*j];
        directedLine* temp2=diagonal_vertices[2*j+1];
               if(temp1==v1 || temp1==v2 || temp2==v1 || temp2==v2)
        if(! temp1->samePolygon(temp1, temp2))
          {
            /*if temp1 and temp2 are in different polygons, 
             *then one of them must be v1 or v2.
             */
 
 
 
            assert(temp1==v1 || temp1 == v2 || temp2==v1 || temp2 ==v2);
            if(temp1==v1) 
              {
            diagonal_vertices[2*j] = v2->getPrev();
              }
            if(temp2==v1)
              {
            diagonal_vertices[2*j+1] = v2->getPrev();
              }
            if(temp1==v2)
              {
            diagonal_vertices[2*j] = v1->getPrev();           
              }
            if(temp2==v2)
              {
            diagonal_vertices[2*j+1] = v1->getPrev();
              }
          }
          }
      }      
 
      }
 
  /*clean up spaces*/
  free(array);
  free(ranges);
  free(diagonal_vertices);
  free(removedDiagonals);
 
  *retSampledLines = newSampledLines;
  return ret_polygons;
}

sweepRangeDelete()

void sweepRangeDelete

(

sweepRange *

range

)

Definition at line 162 of file partitionY.cc.

{
  free(range);
}

sweepRangeEqual()

Int sweepRangeEqual	(	sweepRange *	sr1,
		sweepRange *	sr2
	)

Definition at line 167 of file partitionY.cc.

{
  Int leftEqual;
  Int rightEqual;
  
  
  /*The case when both are vertices should not happen*/
  assert(! (src1->leftType == 0 && src2->leftType == 0));    
  if(src1->leftType == 0 && src2->leftType == 1){
    if(src1->left == src2->left ||
       src1->left->getPrev() == src2->left
       )
      leftEqual = 1;
    else
      leftEqual = 0;
  }
  else if(src1->leftType == 1 && src2->leftType == 1){
    if(src1->left == src2->left)
      leftEqual = 1;
    else
      leftEqual = 0;
  }
  else /*src1->leftType == 1 && src2->leftType == 0*/{
    if(src1->left == src2->left ||
       src1->left == src2->left->getPrev()
       )
      leftEqual = 1;
    else 
      leftEqual = 0;
  }
 
  /*the same thing for right*/
  /*The case when both are vertices should not happen*/
  assert(! (src1->rightType == 0 && src2->rightType == 0));    
  if(src1->rightType == 0 && src2->rightType == 1){
    if(src1->right == src2->right ||
       src1->right->getPrev() == src2->right
       )
      rightEqual = 1;
    else
      rightEqual = 0;
  }
  else if(src1->rightType == 1 && src2->rightType == 1){
    if(src1->right == src2->right)
      rightEqual = 1;
    else
      rightEqual = 0;
  }
  else /*src1->rightType == 1 && src2->rightType == 0*/{
    if(src1->right == src2->right ||
       src1->right == src2->right->getPrev()
       )
      rightEqual = 1;
    else 
      rightEqual = 0;
  }
  
  return (leftEqual == 1 || rightEqual == 1);
}

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.

{
  sweepRange* ret = (sweepRange*)malloc(sizeof(sweepRange));
  assert(ret);
  ret->left = left;
  ret->leftType = leftType;
  ret->right = right;
  ret->rightType = rightType;
  return 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.

{
  Int i;
  /*for each vertex in the sorted list, update the binary search tree.
   *and store the range information for each vertex.
   */
  treeNode* searchTree = NULL;
  for(i=0; i<nVertices;i++)
    {
 
      directedLine* vert = sortedVertices[i];
 
      directedLine* thisEdge = vert;
      directedLine* prevEdge = vert->getPrev();
      
      if(isBelow(vert, thisEdge) && isAbove(vert, prevEdge))
    {
 
      /*case 1: this < v < prev
       *the polygon is going down at v, the interior is to 
       *the right hand side.
       * find the edge to the right of thisEdge for right range.
           * delete thisEdge
           * insert prevEdge
       */
      treeNode* thisNode = TreeNodeFind(searchTree, thisEdge, ( Int (*) (void *, void *))compEdges);
      assert(thisNode);
 
      treeNode* succ = TreeNodeSuccessor(thisNode);
      assert(succ);
      searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
      searchTree = TreeNodeInsert(searchTree, TreeNodeMake(prevEdge), ( Int (*) (void *, void *))compEdges);
 
 
      ret_ranges[i] = sweepRangeMake(vert, 0, (directedLine*) (succ->key), 1);
 
    }
      else if(isAbove(vert, thisEdge) && isBelow(vert, prevEdge))
    {
 
      /*case 2: this > v > prev
       *the polygon is going up at v, the interior is to 
       *the left hand side.
       * find the edge to the left of thisEdge for left range.
           * delete prevEdge
           * insert thisEdge
       */     
      treeNode* prevNode = TreeNodeFind(searchTree, prevEdge, ( Int (*) (void *, void *))compEdges);
      assert(prevNode);
      treeNode* pred = TreeNodePredecessor(prevNode);
      searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
      searchTree = TreeNodeInsert(searchTree, TreeNodeMake(thisEdge), ( Int (*) (void *, void *))compEdges);
      ret_ranges[i] = sweepRangeMake((directedLine*)(pred->key), 1, vert, 0);
    }
      else if(isAbove(vert, thisEdge) && isAbove(vert, prevEdge))
    {
 
      /*case 3: insert both edges*/
      treeNode* thisNode = TreeNodeMake(thisEdge);
      treeNode* prevNode = TreeNodeMake(prevEdge);    
      searchTree = TreeNodeInsert(searchTree, thisNode, ( Int (*) (void *, void *))compEdges);
      searchTree = TreeNodeInsert(searchTree, prevNode, ( Int (*) (void *, void *))compEdges);    
      if(compEdges(thisEdge, prevEdge)<0)  /*interior cusp*/
        {
 
          treeNode* leftEdge = TreeNodePredecessor(thisNode);
          treeNode* rightEdge = TreeNodeSuccessor(prevNode);
          ret_ranges[i] = sweepRangeMake( (directedLine*) leftEdge->key, 1, 
                         (directedLine*) rightEdge->key, 1
                         );
        }
      else /*exterior cusp*/
        {
 
          ret_ranges[i] = sweepRangeMake( prevEdge, 1, thisEdge, 1);
        }
    }
      else if(isBelow(vert, thisEdge) && isBelow(vert, prevEdge))
    {
 
      /*case 4: delete both edges*/
      treeNode* thisNode = TreeNodeFind(searchTree, thisEdge, ( Int (*) (void *, void *))compEdges);
      treeNode* prevNode = TreeNodeFind(searchTree, prevEdge, ( Int (*) (void *, void *))compEdges);
      if(compEdges(thisEdge, prevEdge)>0) /*interior cusp*/
        {
          treeNode* leftEdge = TreeNodePredecessor(prevNode);
          treeNode* rightEdge = TreeNodeSuccessor(thisNode);
          ret_ranges[i] = sweepRangeMake( (directedLine*) leftEdge->key, 1, 
                         (directedLine*) rightEdge->key, 1
                         );
        }
      else /*exterior cusp*/
        {
          ret_ranges[i] = sweepRangeMake( thisEdge, 1, prevEdge, 1);
        }
      searchTree = TreeNodeDeleteSingleNode(searchTree, thisNode);
      searchTree = TreeNodeDeleteSingleNode(searchTree, prevNode);
    }
      else
    {
      fprintf(stderr,"error in partitionY.C, invalid case\n");
      printf("vert is\n");
      vert->printSingle();
      printf("thisEdge is\n");
      thisEdge->printSingle();
      printf("prevEdge is\n");
      prevEdge->printSingle();
      
      exit(1);
    }
    }
 
  /*finaly clean up space: delete the search tree*/
  TreeNodeDeleteWholeTree(searchTree);
}

Referenced by DBGfindDiagonals(), and partitionY().