samplemonopoly.cc

winNT技术操作系统,国外开放的原代码和LIUX一样

  rightGridChain = new gridBoundaryChain(grid, firstGridIndex, firstGridIndex-lastGridIndex+1, rightGridIndices, rightGridInnerIndices);

  free(leftGridIndices);
  free(rightGridIndices);
  free(leftGridInnerIndices);
  free(rightGridInnerIndices);
}

void findDownCorners(Real *botVertex, 
		   vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex,
		   vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex,
		   Real v,
		   Real uleft,
		   Real uright,
		   Int& ret_leftCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
		   Int& ret_leftCornerIndex, /*useful when ret_leftCornerWhere == 0 or 2*/
		   Int& ret_rightCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
		   Int& ret_rightCornerIndex /*useful when ret_leftCornerWhere == 0 or 2*/
		   )
{
#ifdef MYDEBUG
printf("*************enter find donw corner\n");
printf("finddownCorner: v=%f, uleft=%f, uright=%f\n", v, uleft, uright);
printf("(%i,%i,%i,%i)\n", leftChainStartIndex, leftChainEndIndex,rightChainStartIndex, rightChainEndIndex); 
printf("left chain is\n");
leftChain->print();
printf("right chain is\n");
rightChain->print();
#endif

  assert(v > botVertex[1]);
  Real leftGridPoint[2];
  leftGridPoint[0] = uleft;
  leftGridPoint[1] = v;
  Real rightGridPoint[2];
  rightGridPoint[0] = uright;
  rightGridPoint[1] = v;

  Int i;
  Int index1, index2;

  index1 = leftChain->findIndexBelowGen(v, leftChainStartIndex, leftChainEndIndex);
  index2 = rightChain->findIndexBelowGen(v, rightChainStartIndex, rightChainEndIndex);

  if(index2 <= rightChainEndIndex) //index2 was found above
    index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex);

  if(index1>leftChainEndIndex && index2 > rightChainEndIndex) /*no point below v on left chain or right chain*/
    {

      /*the botVertex is the only vertex below v*/
      ret_leftCornerWhere = 1;
      ret_rightCornerWhere = 1;
    }
  else if(index1>leftChainEndIndex ) /*index2 <= rightChainEndIndex*/
    {

      ret_rightCornerWhere = 2; /*on right chain*/
      ret_rightCornerIndex = index2;


      Real tempMin = rightChain->getVertex(index2)[0];
      Int tempI = index2;
      for(i=index2+1; i<= rightChainEndIndex; i++)
	if(rightChain->getVertex(i)[0] < tempMin)
	  {
	    tempI = i;
	    tempMin = rightChain->getVertex(i)[0];
	  }


      //we consider whether we can use botVertex as left corner. First check 
      //if (leftGirdPoint, botVertex) interesects right chian or not.
     if(DBG_intersectChain(rightChain, rightChainStartIndex,rightChainEndIndex,
				    leftGridPoint, botVertex))
       {
	 ret_leftCornerWhere = 2;//right
	 ret_leftCornerIndex = index2; //should use tempI???
       }
     else if(botVertex[0] < tempMin)
       ret_leftCornerWhere = 1; //bot
     else
       {
	 ret_leftCornerWhere = 2; //right
	 ret_leftCornerIndex = tempI;
       }
    }
  else if(index2> rightChainEndIndex) /*index1<=leftChainEndIndex*/
    {
      ret_leftCornerWhere = 0; /*left chain*/
      ret_leftCornerIndex = index1;
      
      /*find the vertex on the left chain with the maximum u,
       *either this vertex or the botvertex can be used as the right corner
       */

      Int tempI;
      //skip those points which are equal to v. (avoid degeneratcy)
      for(tempI = index1; tempI <= leftChainEndIndex; tempI++)
	if(leftChain->getVertex(tempI)[1] < v) 
	  break;
      if(tempI > leftChainEndIndex)
	ret_rightCornerWhere = 1;
      else
	{
	  Real tempMax = leftChain->getVertex(tempI)[0];
	  for(i=tempI; i<= leftChainEndIndex; i++)
	    if(leftChain->getVertex(i)[0] > tempMax)
	      {
		tempI = i;
		tempMax = leftChain->getVertex(i)[0];
	      }



	  //we consider whether we can use botVertex as a corner. So first we check 
	  //whether (rightGridPoint, botVertex) interescts the left chain or not.
	  if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex,
				    rightGridPoint, botVertex))
	    {
	      ret_rightCornerWhere = 0;
	      ret_rightCornerIndex = index1; //should use tempI???
	    }
	  else if(botVertex[0] > tempMax)
	    {
		      
              ret_rightCornerWhere = 1;
	    }
	  else
	    {
	      ret_rightCornerWhere = 0;
	      ret_rightCornerIndex = tempI;
	    }
	}
      
    }
  else /*index1<=leftChainEndIndex and index2 <=rightChainEndIndex*/
    {
      if(leftChain->getVertex(index1)[1] >= rightChain->getVertex(index2)[1]) /*left point above right point*/
	{
	  ret_leftCornerWhere = 0; /*on left chain*/
	  ret_leftCornerIndex = index1;

	  Real tempMax;
	  Int tempI;

	  tempI = index1;
	  tempMax = leftChain->getVertex(index1)[0];

	  /*find the maximum u for all the points on the left above the right point index2*/
	  for(i=index1+1; i<= leftChainEndIndex; i++)
	    {
	      if(leftChain->getVertex(i)[1] < rightChain->getVertex(index2)[1])
		break;

	      if(leftChain->getVertex(i)[0]>tempMax)
		{
		  tempI = i;
		  tempMax = leftChain->getVertex(i)[0];
		}
	    }
	  //we consider if we can use rightChain(index2) as right corner
	  //we check if (rightChain(index2), rightGidPoint) intersecs left chain or not.
	  if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2)))
	    {
	      ret_rightCornerWhere = 0;
	      ret_rightCornerIndex = index1; //should use tempI???
	    }
	  else if(tempMax >= rightChain->getVertex(index2)[0] ||
	     tempMax >= uright
	     )
	    {

	      ret_rightCornerWhere = 0; /*on left Chain*/
	      ret_rightCornerIndex = tempI;
	    }
	  else
	    {
	      ret_rightCornerWhere = 2; /*on right chain*/
	      ret_rightCornerIndex = index2;
	    }
	}
      else /*left below right*/
	{
	  ret_rightCornerWhere = 2; /*on the right*/
	  ret_rightCornerIndex = index2;
	  
	  Real tempMin;
	  Int tempI;
	  
	  tempI = index2;
	  tempMin = rightChain->getVertex(index2)[0];
	  
	  /*find the minimum u for all the points on the right above the left poitn index1*/
	  for(i=index2+1; i<= rightChainEndIndex; i++)
	    {
	      if( rightChain->getVertex(i)[1] < leftChain->getVertex(index1)[1])
		break;
	      if(rightChain->getVertex(i)[0] < tempMin)
		{
		  tempI = i;
		  tempMin = rightChain->getVertex(i)[0];
		}
	    }

	  //we consider if we can use leftchain(index1) as left corner. 
	  //we check if (leftChain(index1) intersects right chian or not
	  if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex, leftGridPoint, leftChain->getVertex(index1)))
	    {
	      ret_leftCornerWhere = 2;
	      ret_leftCornerIndex = index2; //should use tempI???
	      }
	  else if(tempMin <= leftChain->getVertex(index1)[0] ||
	     tempMin <= uleft)				
	    {
	      ret_leftCornerWhere = 2; /* on right chain*/
	      ret_leftCornerIndex = tempI;
	    }
	  else
	    {
	      ret_leftCornerWhere = 0; /*on left chain*/
	      ret_leftCornerIndex = index1;
	    }
	}
    }

}


void findUpCorners(Real *topVertex, 
		   vertexArray *leftChain, Int leftChainStartIndex, Int leftChainEndIndex,
		   vertexArray *rightChain, Int rightChainStartIndex, Int rightChainEndIndex,
		   Real v,
		   Real uleft,
		   Real uright,
		   Int& ret_leftCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
		   Int& ret_leftCornerIndex, /*useful when ret_leftCornerWhere == 0 or 2*/
		   Int& ret_rightCornerWhere, /*0: left chain, 1: topvertex, 2: rightchain*/
		   Int& ret_rightCornerIndex /*useful when ret_leftCornerWhere == 0 or 2*/
		   )
{
#ifdef MYDEBUG
printf("***********enter findUpCorners\n");
#endif

  assert(v < topVertex[1]);
  Real leftGridPoint[2];
  leftGridPoint[0] = uleft;
  leftGridPoint[1] = v;
  Real rightGridPoint[2];
  rightGridPoint[0] = uright;
  rightGridPoint[1] = v;

  Int i;
  Int index1, index2;

  index1 = leftChain->findIndexFirstAboveEqualGen(v, leftChainStartIndex, leftChainEndIndex);


  index2 = rightChain->findIndexFirstAboveEqualGen(v, rightChainStartIndex, rightChainEndIndex);

  if(index2>= leftChainStartIndex)  //index2 was found above  
    index2 = rightChain->skipEqualityFromStart(v, index2, rightChainEndIndex);

  if(index1<leftChainStartIndex && index2 <rightChainStartIndex) /*no point above v on left chain or right chain*/
    {
      /*the topVertex is the only vertex above v*/
      ret_leftCornerWhere = 1;
      ret_rightCornerWhere = 1;
    }
  else if(index1<leftChainStartIndex ) /*index2 >= rightChainStartIndex*/
    {
      ret_rightCornerWhere = 2; /*on right chain*/
      ret_rightCornerIndex = index2;

      //find the minimum u on right top, either that, or top, or right[index2] is the left corner
      Real tempMin = rightChain->getVertex(index2)[0];
      Int tempI = index2;
      for(i=index2-1; i>=rightChainStartIndex; i--)
	if(rightChain->getVertex(i)[0] < tempMin)
	  {
	    tempMin = rightChain->getVertex(i)[0];
	    tempI = i;
	  }
      //chech whether (leftGridPoint, top) intersects rightchai,
      //if yes, use right corner as left corner
      //if not, use top or right[tempI] as left corner
      if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex,
			leftGridPoint, topVertex))
	{
	  ret_leftCornerWhere = 2; //rightChain
	  ret_leftCornerIndex = index2; 
	}
      else if(topVertex[0] < tempMin)
	ret_leftCornerWhere = 1; /*topvertex*/
      else
	{
	  ret_leftCornerWhere = 2; //right chain
	  ret_leftCornerIndex = tempI;
	}
	      
    }
  else if(index2< rightChainStartIndex) /*index1>=leftChainStartIndex*/
    {
      ret_leftCornerWhere = 0; /*left chain*/
      ret_leftCornerIndex = index1;
       
      //find the maximum u on the left top section. either that or topvertex, or left[index1]  is the right corner
      Real tempMax = leftChain->getVertex(index1)[0];
      Int tempI = index1;

      for(i=index1-1; i>=leftChainStartIndex; i--){

	if(leftChain->getVertex(i)[0] > tempMax)
	  {

	    tempMax = leftChain->getVertex(i)[0];
	    tempI = i;
	  }
      }
      //check whether (rightGridPoint, top) intersects leftChain or not
      //if yes, we use leftCorner as the right corner
      //if not, we use either top or left[tempI] as the right corner
      if(DBG_intersectChain(leftChain, leftChainStartIndex,leftChainEndIndex,
			    rightGridPoint, topVertex))
	 {
	   ret_rightCornerWhere = 0; //left chan
	   ret_rightCornerIndex = index1;
	 }
      else if(topVertex[0] > tempMax)
	ret_rightCornerWhere = 1;//topVertex
      else
	{
	  ret_rightCornerWhere = 0;//left chain
	  ret_rightCornerIndex = tempI;
	}
    }
  else /*index1>=leftChainStartIndex and index2 >=rightChainStartIndex*/
    {
      if(leftChain->getVertex(index1)[1] <= rightChain->getVertex(index2)[1]) /*left point below right point*/
	{
	  ret_leftCornerWhere = 0; /*on left chain*/
	  ret_leftCornerIndex = index1;

	  Real tempMax;
	  Int tempI;

	  tempI = index1;
	  tempMax = leftChain->getVertex(index1)[0];

	  /*find the maximum u for all the points on the left below the right point index2*/
	  for(i=index1-1; i>= leftChainStartIndex; i--)
	    {
	      if(leftChain->getVertex(i)[1] > rightChain->getVertex(index2)[1])
		break;

	      if(leftChain->getVertex(i)[0]>tempMax)
		{
		  tempI = i;
		  tempMax = leftChain->getVertex(i)[0];
		}
	    }
	  //chek whether (rightChain(index2), rightGridPoint) intersects leftchian or not
	  if(DBG_intersectChain(leftChain, leftChainStartIndex, leftChainEndIndex, rightGridPoint, rightChain->getVertex(index2)))
	     {
	       ret_rightCornerWhere = 0;
	       ret_rightCornerIndex = index1;
	     }
	  else if(tempMax >= rightChain->getVertex(index2)[0] ||
	     tempMax >= uright)
	    {
	      ret_rightCornerWhere = 0; /*on left Chain*/
	      ret_rightCornerIndex = tempI;
	    }
	  else
	    {
	      ret_rightCornerWhere = 2; /*on right chain*/
	      ret_rightCornerIndex = index2;
	    }
	}
      else /*left above right*/
	{
	  ret_rightCornerWhere = 2; /*on the right*/
	  ret_rightCornerIndex = index2;
	  
	  Real tempMin;
	  Int tempI;
	  
	  tempI = index2;
	  tempMin = rightChain->getVertex(index2)[0];
	  
	  /*find the minimum u for all the points on the right below the left poitn index1*/
	  for(i=index2-1; i>= rightChainStartIndex; i--)
	    {
	      if( rightChain->getVertex(i)[1] > leftChain->getVertex(index1)[1])
		break;
	      if(rightChain->getVertex(i)[0] < tempMin)
		{
		  tempI = i;
		  tempMin = rightChain->getVertex(i)[0];
		}
	    }
          //check whether (leftGRidPoint,left(index1)) interesect right chain 
	  if(DBG_intersectChain(rightChain, rightChainStartIndex, rightChainEndIndex,
				leftGridPoint, leftChain->getVertex(index1)))
	    {
	      ret_leftCornerWhere = 2; //right
	      ret_leftCornerIndex = index2;
	    }
	  else if(tempMin <= leftChain->getVertex(index1)[0] ||
	     tempMin <= uleft)
	    {
	      ret_leftCornerWhere = 2; /* on right chain*/
	      ret_leftCornerIndex = tempI;
	    }
	  else
	    {
	      ret_leftCornerWhere = 0; /*on left chain*/
	      ret_leftCornerIndex = index1;
	    }
	}