convexhull.txt

现有一硬件采集了人在一固定大小的平面上的压力中心点

 现有一硬件采集了人在一固定大小的平面上的压力中心点，采集了很多数据，现在要求用vb算出一组压力中心点的凸包，以便显示人在这一时段的活动范围   
    
    
    
    
  /*****************************************************/   
  /*                                                                                                       */   
  /*               凸包问题求解                                                                 */   
  /*               使用蛮力算法                                                                 */   
  /*               Author:lixiongwei                                                       */   
  /*               Time:06/12/11   Sun.                                                     */   
  /*               WIN   XP+(TC/Win_TC/VC++6.0)                                     */   
  /*                                                                                                       */   
  /*****************************************************/   
  #include   <stdio.h>   
  #include   <conio.h>   
  #include   <time.h>   
  #include   <stdlib.h>   
  #include   <graphics.h>   
  #define   MAX_X       630   
  #define   MAX_Y       470   
  #define   MAX_NUM     200   
  /******************函数原型以及变量类型声明***********************/   
  struct     point{   
          double   x;   /*横坐标*/   
          double   y;   /*纵坐标*/   
          int   flag;   /*标记凸点*/   
  };   
  struct   point   my_point[MAX_NUM];   /*定义凸包点的信息*/   
  void   my_graphics();   
  void   my_convex_hull();   
  /*****************************主函数******************************/   
  int   main()   
  {   
          int   i,j,k;   
          clock_t       start,end;         
          double       elapsed,temp_x,temp_y;   
    
          /*初始化随机数*/   
          srand(   (unsigned)time(   NULL   )   );   
          start=clock();   
          for(i=0;i<MAX_NUM;i++)   
          {   
              while(   (my_point[i].x   =   (rand()   %   MAX_X))<10   );/*随机产生横坐标*/   
              while(   (my_point[i].y   =   (rand()   %   MAX_Y))<10   );/*随机产生纵坐标*/   
              my_point[i].flag=0;   
          }   
          /**********************************/   
          for(i=0;i<MAX_NUM;i++)   
                  printf("my_point[%d].x=%f         my_point[%d].y=%f         my_point[%d].flag=%d\n",   
                                i,my_point[i].x,i,my_point[i].y,i,my_point[i].flag);   
    
          printf("\nNow   compute,press   any   key   to   continue...\n");   
          getch();   
          my_convex_hull();/*调用凸包计算函数*/   
          for(i=0;i<MAX_NUM;i++)   
                  printf("my_point[%d].x=%f         my_point[%d].y=%f         my_point[%d].flag=%d\n",   
                                i,my_point[i].x,       i,my_point[i].y,       i,my_point[i].flag);   
    
          printf("\nPress   any   key   to   watch   screen...\n");   
          getch();   
          my_graphics();   
          end=clock();   
          elapsed=((double)(end-start))/CLK_TCK;   
          printf("This   program   use   time:   %fs.   goodbye   everyone~!\n",elapsed);   
          getch();   
          return   0;   
  }   
    
  /******************使用蛮力算法求凸包计算函数的定义*******************/   
  void     my_convex_hull()   
  {   
          int   i,j,k,sign=0;   
          double   a=0,b=0,c=0;   
    
          for(i=0;   i<MAX_NUM;   ++i)   
                  for(j=i+1;   j<MAX_NUM;   ++j)   
                  {   
                            a   =   my_point[j].y   -   my_point[i].y;   
                            b   =   my_point[i].x   -   my_point[j].x;   
                            c   =   (   my_point[i].x   *   my_point[j].y   )-(   my_point[i].y   *   my_point[j].x   );   
    
                            sign=0;   
                            for(k=0;   k<MAX_NUM;   ++k)   
                            {   
                                    if(   (k==j)||(k==i)   )   
                                            continue;   
                                    /*   
                                    if(   (   a*my_point[k].x+b*my_point[k].y   )   ==   c)   
                                            exit(1);   
                                    */       /*如果有两个以上的点共线，不处理*/   
    
                                    if(   (   (a*(my_point[k].x)+b*(my_point[k].y))>c   )   )   
                                            ++sign;   
                                    if(   (   (a*(my_point[k].x)+b*(my_point[k].y))<c   )   )   
                                            --sign;   
    
                              }/*end   inside   for*/   
    
                              if(   (sign==(MAX_NUM-2))||((sign==(2-MAX_NUM)))   )   
                              {   
                                        printf("\n\n");   
                                        my_point[i].flag=1;   
                                        my_point[j].flag=1;   
                              }   
    
                    }/*inside   for   end   */   
    
                  printf("\n\n");   
  }   
    
  /******************屏幕输出函数的函数定义*******************/   
  void   my_graphics()   
  {   
          int   i,j,k,convex_hull,sign;   
          double   a=0,b=0,c=0;   
          struct   point   border_point[MAX_NUM];   /*记录边界凸点*/   
          int   graphdriver=VGA;   
          int   graphmode=VGAHI;   
    
          initgraph(&graphdriver,&graphmode,"");   
          cleardevice();   
          setcolor(WHITE);   
          rectangle(0,0,639,479);   
          rectangle(2,2,637,477);   
    
          for(i=0,j=0;i<MAX_NUM;i++)   
          {   
                  if(my_point[i].flag==1)   
                  {   
                          border_point[j].x   =   my_point[i].x;   
                          border_point[j].y   =   my_point[i].y;   
                          border_point[j].flag   =   1;   
                          ++j;   
                    }   
          }   
          convex_hull=j;/*记录顶点个数*/   
    
          for(i=0;i<MAX_NUM;++i)   
          {   
                  if(my_point[i].flag==1)   
                  {   
                          setcolor(YELLOW);   
                          fillellipse(my_point[i].x,   my_point[i].y,   3,3);   
                    }   
                  else   
                  {   
                          setcolor(WHITE);   
                          circle(my_point[i].x,   my_point[i].y   ,2);   
                  }   
          }   
    
    
          /***********以下连接各个凸点*************/   
          setcolor(WHITE);   
          for(i=0;   i<convex_hull;   ++i)   
                  for(j=i+1;   j<convex_hull;   ++j)   
                  {   
                            a   =   border_point[j].y   -   border_point[i].y;   
                            b   =   border_point[i].x   -   border_point[j].x;   
                            c   =   (   border_point[i].x   *   border_point[j].y   )-(   border_point[i].y   *   border_point[j].x   );   
    
                            sign=0;   
                            for(k=0;   k<convex_hull;   ++k)   
                            {   
                                    if(   (k==j)||(k==i)   )   
                                            continue;   
                                    if(   (   (a*(border_point[k].x)+b*(border_point[k].y))>c   )   )   
                                            ++sign;   
                                    if(   (   (a*(border_point[k].x)+b*(border_point[k].y))<c   )   )   
                                            --sign;   
    
                              }/*end   inside   for*/   
    
                              if(   (sign==(convex_hull-2))||((sign==(2-convex_hull)))   )   
                              {   
                                        line(border_point[i].x,border_point[i].y,border_point[j].x,border_point[j].y);   
    
                              }   
    
                    }/*inside   for   end   */   
          /**************************/   
    
          getch();   
          closegraph();   
  }