voronoidoc.cpp

一个很不错的求Voronoi线与最小凸壳的vc++源程序

   LineStruct* Line;
   Line=new LineStruct;
   ZCX(&PointList[0],&PointList[1],Line);
   LineList[0].x1=Line->x1;
   LineList[0].y1=Line->y1;
   LineList[0].x2=Line->x2;
   LineList[0].y2=Line->y2;
   LineList[0].Point1=&PointList[0];
   LineList[0].Point2=&PointList[1];
   LineList[0].exist=TRUE;
   ZCX(&PointList[1],&PointList[2],Line);
   LineList[1].x1=Line->x1;
   LineList[1].y1=Line->y1;
   LineList[1].x2=Line->x2;
   LineList[1].y2=Line->y2;
   LineList[1].Point1=&PointList[1];
   LineList[1].Point2=&PointList[2];
   LineList[1].exist=TRUE;
   Point=intersect(&LineList[0],&LineList[1]);
   ZCX(&PointList[0],&PointList[2],Line);
   LineList[2].x1=Line->x1;
   LineList[2].y1=Line->y1;
   LineList[2].x2=Line->x2;
   LineList[2].y2=Line->y2;
   LineList[2].Point1=&PointList[0];
   LineList[2].Point2=&PointList[2];
   LineList[2].exist=TRUE;
   if(RZDJ(&PointList[0],&PointList[2],&PointList[1])==1)
   {
	   if(IntersectOrNot(Point->x,Point->y,LineList[0].x1,LineList[0].y1,
		   PointList[0].x,PointList[0].y,PointList[1].x,PointList[1].y))
	   {
		    LineList[0].x2=Point->x;
			LineList[0].y2=Point->y;
	   }
	   else
	   {
            LineList[0].x1=Point->x;
			LineList[0].y1=Point->y;
	   }
   }
   else if(RZDJ(&PointList[0],&PointList[2],&PointList[1])==2)
   {
        if(IntersectOrNot(Point->x,Point->y,LineList[0].x1,LineList[0].y1,PointList[1].x,
			PointList[1].y,PointList[2].x,PointList[2].y)||IntersectOrNot(Point->x,Point->y,
			LineList[0].x1,LineList[0].y1,PointList[0].x,PointList[0].y,PointList[2].x,PointList[2].y))
		{
             LineList[0].x1=Point->x;
			 LineList[0].y1=Point->y;
		}
	    else
		{
             LineList[0].x2=Point->x;
			 LineList[0].y2=Point->y;
	   }
   }
   else if(RZDJ(&PointList[0],&PointList[2],&PointList[1])==3)
   {
	   if(IntersectOrNot(Point->x,Point->y,LineList[0].x1,LineList[0].y1,PointList[0].x,
		   PointList[0].y,PointList[1].x,PointList[1].y))
		{
		     LineList[0].x1=Point->x;
			 LineList[0].y1=Point->y;
		}
		else
		{
             LineList[0].x2=Point->x;
			 LineList[0].y2=Point->y;
		}
   }
   if(RZDJ(&PointList[1],&PointList[0],&PointList[2])==1)
   {
	   if(IntersectOrNot(Point->x,Point->y,LineList[1].x1,LineList[1].y1,PointList[1].x,
		   PointList[1].y,PointList[2].x,PointList[2].y))
	   {
		    LineList[1].x2=Point->x;
			LineList[1].y2=Point->y;
	   }
	   else
	   {
            LineList[1].x1=Point->x;
			LineList[1].y1=Point->y;
	   }
   }
   else if(RZDJ(&PointList[1],&PointList[0],&PointList[2])==2)
   {
        if(IntersectOrNot(Point->x,Point->y,LineList[1].x1,LineList[1].y1,PointList[0].x,
			PointList[0].y,PointList[2].x,PointList[2].y)||IntersectOrNot(Point->x,Point->y,
			LineList[1].x1,LineList[1].y1,PointList[0].x,PointList[0].y,PointList[1].x,PointList[1].y))
		{
             LineList[1].x1=Point->x;
			 LineList[1].y1=Point->y;
		}
	    else
		{
             LineList[1].x2=Point->x;
			 LineList[1].y2=Point->y;
	   }
   }
   else if(RZDJ(&PointList[1],&PointList[0],&PointList[2])==3)
   {
	   if(IntersectOrNot(Point->x,Point->y,LineList[1].x1,LineList[1].y1,PointList[1].x,
		   PointList[1].y,PointList[2].x,PointList[2].y))
		{
		     LineList[1].x1=Point->x;
			 LineList[1].y1=Point->y;
		}
		else
		{
             LineList[1].x2=Point->x;
			 LineList[1].y2=Point->y;
		}
   }
   if(RZDJ(&PointList[0],&PointList[1],&PointList[2])==1)
   {
	   if(IntersectOrNot(Point->x,Point->y,LineList[2].x1,LineList[2].y1,PointList[0].x,
		   PointList[0].y,PointList[2].x,PointList[2].y))
	   {
		    LineList[2].x2=Point->x;
			LineList[2].y2=Point->y;
	   }
	   else
	   {
            LineList[2].x1=Point->x;
			LineList[2].y1=Point->y;
	   }
   }
   else if(RZDJ(&PointList[0],&PointList[1],&PointList[2])==2)
   {
        if(IntersectOrNot(Point->x,Point->y,LineList[2].x1,LineList[2].y1,PointList[0].x,
			PointList[0].y,PointList[1].x,PointList[1].y)||IntersectOrNot(Point->x,Point->y,
			LineList[2].x1,LineList[2].y1,PointList[1].x,PointList[1].y,PointList[2].x,PointList[2].y))
		{
             LineList[2].x1=Point->x;
			 LineList[2].y1=Point->y;
		}
	    else
		{
             LineList[2].x2=Point->x;
			 LineList[2].y2=Point->y;
	   }
   }
   else if(RZDJ(&PointList[0],&PointList[1],&PointList[2])==3)
   {
	   if(IntersectOrNot(Point->x,Point->y,LineList[2].x1,LineList[2].y1,PointList[0].x,
		   PointList[0].y,PointList[2].x,PointList[2].y))
		{
		     LineList[2].x1=Point->x;
			 LineList[2].y1=Point->y;
		}
		else
		{
             LineList[2].x2=Point->x;
			 LineList[2].y2=Point->y;
		}
   }
}

int CVoronoiDoc::FourPointVoronoi(PointStruct *PointList1,LineStruct* LineList)
{
   int i,j=3,id=0,in[2];
   double x,y;
   PointStruct* JPoint;
   static PointStruct* PointList;
   PointStruct JPoint1;
   PointStruct* Point;
   LineStruct* Line;
   LineStruct* Line1;
   PointList=new PointStruct[4];
   Line=new LineStruct;
   Line1=new LineStruct;
   for(i=0;i<4;i++)
   {
	   PointList[i].x=PointList1[i].x;
	   PointList[i].y=PointList1[i].y;
   }
   do
   {
	   ZCX(&PointList[0],&PointList[1],Line);
       ZCX(&PointList[1],&PointList[2],Line1);
	   Point=intersect(Line,Line1);
	   if(distance(PointList[3].x,PointList[3].y,Point->x,Point->y)<=distance(PointList[0].x,
		  PointList[0].y,Point->x,Point->y))
	   {
		   x=PointList[0].x;
		   y=PointList[0].y;
		   for(i=0;i<3;i++)
		   {
			   PointList[i].x=PointList[i+1].x;
			   PointList[i].y=PointList[i+1].y;
		   }
		   PointList[3].x=x;
		   PointList[3].y=y;
	   }
	   else
		   break;
   }while(1);
   TriangularVoronoi(PointList,LineList);
   Point->x=((PointList[0].x+PointList[1].x)/2+PointList[2].x)/2;
   Point->y=((PointList[0].y+PointList[1].y)/2+PointList[2].y)/2;
   for(i=0;i<3;i++)
   {
	  if(!same(Point->x,Point->y,PointList[3].x,PointList[3].y,PointList[i].x,PointList[i].y,
      PointList[(i+1)%3].x,PointList[(i+1)%3].y))
	     in[id++]=i;
   }
   if(id==2&&in[0]==0&&in[1]==2)
   {
      in[0]=2;
	  in[1]=0;
   }
   i=in[0];
   ZCX(&PointList[i],&PointList[3],Line);
   JPoint=intersect(Line,&LineList[i]);
   LineList[3].x1=Line->x1;
   LineList[3].y1=Line->y1;
   LineList[3].x2=Line->x2;
   LineList[3].y2=Line->y2;
   LineList[3].Point1=&PointList[i];
   LineList[3].Point2=&PointList[3];
   LineList[3].exist=TRUE;
   if(LineList[i].x1==-(1e+5)||LineList[i].x1==1e+5||LineList[i].y1==-(1e+5)||LineList[i].y1==1e+5)
   {
      LineList[i].x1=JPoint->x;
      LineList[i].y1=JPoint->y;
   }
   if(LineList[i].x2==-(1e+5)||LineList[i].x2==1e+5||LineList[i].y2==-(1e+5)||LineList[i].y2==1e+5)
   {
      LineList[i].x2=JPoint->x;
      LineList[i].y2=JPoint->y;
   }
   if(distance(PointList[i].x,PointList[i].y,LineList[3].x1,LineList[3].y1)<distance(PointList[(i+1)%3].x,
	  PointList[(i+1)%3].y,LineList[3].x1,LineList[3].y1)&&distance(PointList[i].x,PointList[i].y,
	  LineList[3].x1,LineList[3].y1)<distance(PointList[(i+2)%3].x,PointList[(i+2)%3].y,LineList[3].x1,
	  LineList[3].y1))
   {
	  LineList[3].x2=JPoint->x;
      LineList[3].y2=JPoint->y;
   }
   else
   {
      LineList[3].x1=JPoint->x;
      LineList[3].y1=JPoint->y;
   }
   if(id==1)
   { 
      ZCX(&PointList[(i+1)%3],&PointList[3],Line);
	  LineList[4].x1=Line->x1;
      LineList[4].y1=Line->y1;
      LineList[4].x2=Line->x2;
      LineList[4].y2=Line->y2;
      LineList[4].Point1=&PointList[(i+1)%3];
	  LineList[4].Point2=&PointList[3];
      LineList[4].exist=TRUE;
	  if(distance(PointList[(i+1)%3].x,PointList[(i+1)%3].y,LineList[4].x1,LineList[4].y1)
		 <distance(PointList[(i+2)%3].x,PointList[(i+2)%3].y,LineList[4].x1,LineList[4].y1)&&
		 distance(PointList[(i+1)%3].x,PointList[(i+1)%3].y,LineList[4].x1,LineList[4].y1)<
		 distance(PointList[i].x,PointList[i].y,LineList[4].x1,LineList[4].y1))
	  {
	     LineList[4].x2=JPoint->x;
         LineList[4].y2=JPoint->y;
	  }
      else
      {
         LineList[4].x1=JPoint->x;
         LineList[4].y1=JPoint->y;
	  }
	  return 5;
	}
   else
   {
      JPoint1.x=JPoint->x;
	  JPoint1.y=JPoint->y;
	  ZCX(&PointList[(i+2)%3],&PointList[3],Line);
	  i=in[1];
      JPoint=intersect(Line,&LineList[i]);
	  if(LineList[i].x1==-(1e+5)||LineList[i].x1==1e+5||LineList[i].y1==-(1e+5)||LineList[i].y1==1e+5)
	  {
         LineList[i].x1=JPoint->x;
         LineList[i].y1=JPoint->y;
	  }
      if(LineList[i].x2==-(1e+5)||LineList[i].x2==1e+5||LineList[i].y2==-(1e+5)||LineList[i].y2==1e+5)
	  {
         LineList[i].x2=JPoint->x;
         LineList[i].y2=JPoint->y;
	  }
      LineList[4].x1=Line->x1;
      LineList[4].y1=Line->y1;
      LineList[4].x2=Line->x2;
      LineList[4].y2=Line->y2;
	  LineList[4].Point1=&PointList[(i+1)%3];
	  LineList[4].Point2=&PointList[3];
      LineList[4].exist=TRUE;
	  if(distance(PointList[(i+1)%3].x,PointList[(i+1)%3].y,LineList[4].x1,LineList[4].y1)
		 <distance(PointList[(i+2)%3].x,PointList[(i+2)%3].y,LineList[4].x1,LineList[4].y1)&&
		 distance(PointList[(i+1)%3].x,PointList[(i+1)%3].y,LineList[4].x1,LineList[4].y1)<
		 distance(PointList[i].x,PointList[i].y,LineList[4].x1,LineList[4].y1))
	  {
	     LineList[4].x2=JPoint->x;
         LineList[4].y2=JPoint->y;
	  }
      else
      {
         LineList[4].x1=JPoint->x;
         LineList[4].y1=JPoint->y;
	  }
	  LineList[5].x1=JPoint1.x;
	  LineList[5].y1=JPoint1.y;
	  LineList[5].x2=JPoint->x;
	  LineList[5].y2=JPoint->y;
      LineList[5].Point1=&PointList[i];
	  LineList[5].Point2=&PointList[3];
      LineList[5].exist=TRUE;
      return 6;
   }
}
double CVoronoiDoc::distance(double x1, double y1, double x2, double y2)
{
    double s;
	s=(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
	return s;
}
int CVoronoiDoc::ZX(int n, int j, int k, LineStruct *LineList,PointStruct* PointList)
{
    int i,num1,num2,m,s=0,ida1=0,idb1=0,idak=0,idbk=0;
	double t;
	PointStruct* PointList1;
	PointStruct* PointList2;
	PointStruct* Point;
	PointStruct* Point1;
	PointStruct* Point2;
	LineStruct* Line;
	Line=new LineStruct;
    PointList1=ConstructProtrude(PointList,n/2)->GetPointList();
    num1=ConstructProtrude(PointList,n/2)->GetPointNumber();
	for(i=1;i<num1;i++)
	{
		if(PointList1[ida1].y<PointList1[i].y)
		   ida1=i;
        if(PointList1[idak].y>PointList1[i].y)
		   idak=i;
	}
	PointList2=ConstructProtrude(PointList+n/2,n-n/2)->GetPointList();
    num2=ConstructProtrude(PointList+n/2,n-n/2)->GetPointNumber();
    for(i=1;i<num2;i++)
	{
        if(PointList2[idb1].y<PointList2[i].y)
		   idb1=i;
        if(PointList2[idbk].y>PointList2[i].y)
		   idbk=i;
	}
	Point1=&PointList1[ida1];
	Point2=&PointList2[idb1];
	while(!((Point1->x==PointList1[idak].x&&Point1->y==PointList1[idak].y&&Point2->x==PointList2[idbk].x
		   &&Point2->y==PointList2[idbk].y)||(Point1->x==PointList2[idbk].x&&Point1->y==PointList2[idbk].y
		   &&Point2->x==PointList1[idak].x&&Point2->y==PointList1[idak].y)))
	{
		ZCX(Point1,Point2,Line);
		t=0;
		if(s==0)
		{
			if(Line->y2>Line->y1)
			{
		        LineList[j+k].x1=Line->x2;
		        LineList[j+k].y1=Line->y2;
			}
	        else
			{
		        LineList[j+k].x1=Line->x1;
		        LineList[j+k].y1=Line->y1;
			}
			LineList[j+k+s].Point1=&PointList1[ida1];
            LineList[j+k+s].Point2=&PointList2[idb1];
		}
	    for(i=0;i<j+k;i++)
		{
			if(LineList[i].exist==TRUE&&((LineList[i].Point1->x==Point1->x&&LineList[i].Point1->y
				==Point1->y)||(LineList[i].Point1->x==Point2->x&&LineList[i].Point1->y==Point2->y)
				||(LineList[i].Point2->x==Point1->x&&LineList[i].Point2->y==Point1->y)||
				(LineList[i].Point2->x==Point2->x&&LineList[i].Point2->y==Point2->y))&&
				(IntersectOrNot(Line->x1,Line->y1,Line->x2,Line->y2,LineList[i].x1,LineList[i].y1,
				 LineList[i].x2,LineList[i].y2)))
			{
			    if((int)(intersect(Line,&LineList[i])->y)<(int)(LineList[j+k+s].y1)&&intersect(Line,&LineList[i])->y>t)
				{
				     Point=intersect(Line,&LineList[i]);
		             t=Point->y;
				     m=i;
				}
			}
		}
	    LineList[j+k+s].x2=Point->x;
	    LineList[j+k+s].y2=Point->y;
	    LineList[j+k+s].exist=TRUE;
		LineList[j+k+s+1].x1=Point->x;
	    LineList[j+k+s+1].y1=Point->y;
        if(LineList[m].Point1->x==Point1->x||LineList[m].Point2->x==Point1->x)
		{
			if(!same(Point1->x,Point1->y,LineList[m].x1,LineList[m].y1,Line->x1,Line->y1,Line->x2,Line->y2))
			{
			    LineList[m].x1=Point->x;
		        LineList[m].y1=Point->y;
			}
			else
			{
                LineList[m].x2=Point->x;
		        LineList[m].y2=Point->y;
			}
			if(LineList[m].Point1->x==Point1->x)
			{
        		Point1=LineList[m].Point2;
				LineList[j+k+s+1].Point1=LineList[m].Point2;
				LineList[j+k+s+1].Point2=LineList[j+k+s].Point2;
			}
			else
			{
				Point1=LineList[m].Point1;
				LineList[j+k+s+1].Point1=LineList[m].Point1;
				LineList[j+k+s+1].Point2=LineList[j+k+s].Point2;
			}
		}
        else 
		{
            if(!same(Point2->x,Point2->y,LineList[m].x1,LineList[m].y1,Line->x1,Line->y1,Line->x2,Line->y2))
			{
			    LineList[m].x1=Point->x;
		        LineList[m].y1=Point->y;
			}
			else
			{
                LineList[m].x2=Point->x;
		        LineList[m].y2=Point->y;
			}
            if(LineList[m].Point1->x==Point2->x)
			{
                Point2=LineList[m].Point2;
				LineList[j+k+s+1].Point2=LineList[m].Point2;
				LineList[j+k+s+1].Point1=LineList[j+k+s].Point1;
			}
		    else
			{
                Point2=LineList[m].Point1;
				LineList[j+k+s+1].Point2=LineList[m].Point1;
				LineList[j+k+s+1].Point1=LineList[j+k+s].Point1;
			}
		}
        s++;
	}
	ZCX(Point1,Point2,Line);
	if(Line->y2>Line->y1)
	{
		LineList[j+k+s].x2=Line->x1;
		LineList[j+k+s].y2=Line->y1;
	}
	else
	{
		LineList[j+k+s].x2=Line->x2;
		LineList[j+k+s].y2=Line->y2;
	}
	LineList[j+k+s].exist=TRUE;
    for(i=0;i<j;i++)
	{
		if(LineList[i].x1>700||LineList[i].x2>700)
		{
			LineList[i].exist=FALSE;
		}
	}
	for(i=j;i<j+k;i++)
	{
		if(LineList[i].x1<0||LineList[i].x2<0)
		{
            LineList[i].exist=FALSE;
		}
	}
	return  s+1;
}