?? 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();
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -