graham_convexhull.cpp

用动态数组法实现求凸壳的程序（格雷厄姆法）

#include "stdafx.h"



#include<stdio.h>    
#include"stdlib.h"
#include "conio.h"
#include"math.h"
#define PI  3.1415926
long pNum=18;
long iConvexNum;
void creat(float(*Points)[2])
{long i=0;
  FILE *fp;
  if((fp=fopen("in_put.txt","r"))==NULL)
  { printf("can not open the file\n");
    exit(0);}
  else 
  for(i=0;i<pNum;i++)
     { 
      fscanf(fp,"%f,%f",&Points[i][0],&Points[i][1]);
	 // i=i+1;
     
   }
      
      
  }

//求最下（最右）点。

void miny(float(*Points)[2])
{
 long i;
 float m,n;
 for(i=1;i<pNum;i++)
{
 if(Points[0][1]>Points[i][1])
  {
    m=Points[0][0];
    n=Points[0][1];
    Points[0][1]=Points[i][1];
    Points[0][0]=Points[i][0];
    Points[i][0]=m;
    Points[i][1]=n;
    } 
 else if(Points[0][1]==Points[i][1]&&Points[0][0]>Points[i][0])
             {
             m=Points[0][0];
             n=Points[0][1];
             Points[0][1]=Points[i][1];
             Points[0][0]=Points[i][0];
             Points[i][0]=m;
             Points[i][1]=n;
             }
       else continue;
      }
  }
//判断倾角，并按从小到大排列。

void tank(float(*Points)[2])
  {  
      float fi,minfi,dx,dy;
	  long k;
	  float m,n;
	  float lastdis,nowdis;
      iConvexNum=pNum;
      long i,j;
   for(j=0;j<pNum;j++)
     { 
        minfi=2*PI;
   for(i=j+1;i<pNum;i++) 
    {
      dx=Points[i][0]-Points[0][0];
      dy=Points[i][1]-Points[0][1];
      nowdis=dx*dx+dy*dy;
      if(dx!=0&&dy!=0)  
      { 
       fi=atan(dy/dx);
       if(fi<0)
       fi=PI+fi;
      }
	  else if (dx<0&&dy==0) fi=PI;
	  else if (dx>0&&dy==0) fi=0;
      else fi=PI/2;
     if(minfi>fi)
     {     
         if(i!=j+1)
           { m=Points[j+1][0];
             n=Points[j+1][1];
             Points[j+1][1]=Points[i][1];
             Points[j+1][0]=Points[i][0];
             Points[i][0]=m;
             Points[i][1]=n;  }
             minfi=fi;
             lastdis=nowdis;
     }
   else if(minfi==fi&&lastdis<nowdis)
            {
             m=Points[j+1][0];
             n=Points[j+1][1];
             Points[j+1][1]=Points[i][1];
             Points[j+1][0]=Points[i][0];
             Points[i][0]=m;
             Points[i][1]=n;
            iConvexNum=iConvexNum-1;
            for(k=i;k<pNum-1;k++)
             {
              Points[k][0]=Points[k+1][0];
              Points[k][1]=Points[k+1][1];
             }
              pNum=pNum-1;
			  i=i-1;
           }
   else if(minfi==fi&&lastdis>nowdis)
      {      for(k=i;k<pNum-1;k++)
             {
              Points[k][0]=Points[k+1][0];
              Points[k][1]=Points[k+1][1];
             }
              pNum=pNum-1;
			  iConvexNum=iConvexNum-1;
			  i=i-1;
           }
else continue;
      }
   }
}
        
    

//判断是否在线段的两侧,生成凸壳。。

void ConvexHull(float(*Points)[2])
{ 
   float dx,dy,dx1,dy1,dx2,dy2;
   float same;
   long  i,k;
   for(i=0;i<pNum-3;i++)
     {
        dx=Points[i+2][0]-Points[i+1][0];
        dy=Points[i+2][1]-Points[i+1][1];
        dx1=Points[i][0]-Points[i+1][0];
        dy1=Points[i][1]-Points[i+1][1];
        dx2=Points[i+3][0]-Points[i+2][0];
        dy2=Points[i+3][1]-Points[i+2][1];
same=(dx*dy1-dy*dx1)*(dx*dy2-dy*dx2);

if(same>0&&(dx*dy1-dy*dx1)<0&&(dx*dy1-dy*dx1)<0)
           {
              for(long k=i+1;k<pNum-2;k++)
                { 
                  Points[k][0]=Points[k+2][0];
                  Points[k][1]=Points[k+2][1];
                 }
			   pNum=pNum-2;
			   iConvexNum=iConvexNum-2;
			   i=i-1;
            }
		
		else if(same<0&&(dx*dy1-dy*dx1)<0)
           {
              for(long k=i+1;k<pNum-1;k++)
                { 
                  Points[k][0]=Points[k+1][0];
                  Points[k][1]=Points[k+1][1];
                 }
			   pNum=pNum-1;
			   iConvexNum=iConvexNum-1;
			   i=i-1;
            }
       else if(same<0&&(dx*dy2-dy*dx2)<0)
           {
             for(long k=i+2;k<pNum-1;k++)
               { 
                  Points[k][0]=Points[k+1][0];
                  Points[k][1]=Points[k+1][1];
               }
			   pNum=pNum-1;
			   iConvexNum=iConvexNum-1;
			   i=i-1;
            }

       else if(same==0)
           {
              for(long k=i+2;k<pNum-1;k++)
				{ 
				   Points[k][0]=Points[k+1][0];
				   Points[k][1]=Points[k+1][1];
				}
			   i=i-1;
			   pNum=pNum-1;
			   iConvexNum=iConvexNum-1;
		   }
	   
			  else continue;
	}


}


void print(float(*Points)[2])
  {
   FILE *fp;
   

   if((fp=fopen("out_put.txt","w"))==NULL)
     { printf("can not open the file\n");
       getch();
       exit(0);}
  for(long i=0;i<iConvexNum;i++)  
     { fprintf(fp,"%f,%f",Points[i][0],Points[i][1]);
       fprintf(fp,"\n");
       }
    }

int _tmain(int argc, _TCHAR* argv[])
{   long i; 
    float(*Points)[2];
    Points=new float[pNum][2];
    creat(Points);
    miny(Points);
    tank(Points);
    ConvexHull(Points);
	print(Points);
  return(0);
}