partitiony.cc

Mesa is an open-source implementation of the OpenGL specification - a system for rendering interacti

	  index++;
	}
    }
  return index;
}

/*for debug only*/	  
directedLine** DBGfindDiagonals(directedLine *polygons, Int& num_diagonals)
{
  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;

}


/*partition into Y-monotone polygons*/
directedLine* partitionY(directedLine *polygons, sampledLine **retSampledLines)
{
  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;
}
	
/*given a set of simple polygons where the interior 
 *is decided by left-hand principle,
 *return a range (sight) for each vertex. This is called
 *Trapezoidalization.
 */ 
void sweepY(Int nVertices, directedLine** sortedVertices, sweepRange** ret_ranges)
{
  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);
}