tubao.rar_凸包算法

#include <stdio.h> #include <stdlib.h> #include <math.h> void Init();//数据读入 void Make();//算法函数 void QSort(int); //对顶点进行快速排序 void Swap(int, int); //交换内容 #define MAXN 10 // 顶点的个数 /* 顶点的类型定义 */ typedef struct { double x; double y; double arCos; }Point1; Point1 points[MAXN]; // 顶点数组 int stack[MAXN]; // 栈 /*主函数*/ int main() { Init(); //程序数据的读入 Make(); //程序算法过程 while(1); return 0; } /*数据读入函数*/ void Init() { points[0].x=-1; points[0].y=0; points[1].x=1; points[1].y=1; points[2].x=0; points[2].y=1; points[3].x=1; points[3].y=0; points[4].x=0.5; points[4].y=0.5; points[5].x=0.6; points[5].y=0.7; points[6].x=0.3; points[6].y=0.2; points[7].x=5; points[7].y=10; points[8].x=-2; points[8].y=8; points[9].x=10; points[9].y=20; } //int i; //for(i=0;i<MAXN;i++) //{ // printf("please enter points:"); // getchar(); // fflush(stdin); // scanf("<%.2lf, %.2lf>",&points[i].x,&points[i].y); // } // } /*算法实现函数*/ void Make() { int Multi(Point1, Point1, Point1); //计算两个向量的积 double Angle(int); //计算其余顶点与第一顶点的角度,为排序做准备 int i, j, t; double min = 32767.0; for(i=0; i<MAXN;i++)/ /找第一个顶点,做为算法的起始顶点 { if(points[i].y < min) { j = i; min = points[i].y; } } Swap(0, j); for(i=1;i<MAXN;i++) //计算除第一顶点外的其余顶点到第一点的线段与x轴的夹角 { points[i].arCos = Angle(i); } QSort(MAXN); //根据所得到的角度进行快速排序. for(i=0;i<=2;++i) stack[i] = i; //将前3个顶点压栈 t = 2; while(i < MAXN) { /*如果新的点,与最近入栈中的2点构成了一个"凹"角, 则将栈顶元素出栈. 直到把栈检查完*/ while(Multi(points[stack[t-1]], points[stack[t]], points[i]) && t >= 1) t--; t++; // 将新点压栈 stack[t] = i; i++; } /*显示结果*/ for(i=0;i<=t;i++) printf("<%.2lf, %.2lf>\n",points[stack[i]].x, points[stack[i]].y); } /*左转关系判断*/ int Multi(Point1 px, Point1 py, Point1 pz) { double k; k = (py.x-px.x)*(pz.y-py.y) - (pz.x-py.x)*(py.y-px.y); // 计算两个向量的向量积, // 判断3个点所成的角是不是一个"凹"角. if(k < 0) return 1; return 0; } /*角度计算函数*/ double Angle(int i) { double j, k, m, n; j = fabs(points[i].x - points[0].x); k = fabs(points[i].y - points[0].y); m = sqrt(j*j+k*k); //得到顶点i 到第一顶点的线段长度. n = acos(j/m); //得到该线段与x轴的角度 //强悍 return n; } /*根据角度进行排序*/ void QSort(int n) { int i,j,k,min; for(i=0;i<=n-1;i++) { k=i+1; min=i; for(j=k;j<n;j++) if(points[j].arCos<points[min].arCos) Swap(j,min); } } /*交换*/ void Swap(int px, int py) { Point1 k; k.x = points[px].x; k.y = points[px].y; k.arCos = points[px].arCos; points[px].x = points[py].x; points[px].y = points[py].y; points[px].arCos = points[py].arCos; points[py].x = k.x; points[py].y = k.y; points[py].arCos = k.arCos; }