|
凸包是对平面是上的某个点集而言的，凸包是一个最小凸多边形，满足点集
中的所有点都在该凸多边形内（或在该多边形的边上）。
通常，我们采用Graham扫描法来求点集的凸包。首先，排序选出点集中最左下
角点（先取y坐标最小的点，若有多个再在其中取x坐标最小的点），设该点为p0；
然后，将其余的按以p0为中心的极角坐标逆时针排序，多于相同极角的点只保留
距离p0最远的一个，这样就可以得到一个点的序列p1,p2, p2…..,pn;接下来，
将p0, p1, p2压入栈，一次处理pi（i >= 2 && i <= n），不断让栈顶的元素出
栈，直到栈顶的下一个元素，栈顶元素，以及pi构成的折线不拐向左侧，将pi压
入栈中；最后栈中的元素即为所求的凸包的顶点序列
void swap(TPoint p[], int i, int j)
{
TPoint tmp;
tmp = p[i];
p[i] = p[j];
p[j] = tmp;
}
int stack[MaxNode];
int top;
int cmp(const void *a, const void *b)
{
TPoint *c = (TPoint *)a;
TPoint *d = (TPoint *)b;
double k = multi(*c, *d, point[0]);
if(k< 0) return 1;
else if(k == 0 && distance(*c, point[0]) < distance(*d, point[0])) return 1;
else return -1;
}
void grahamScan(TPoint p[], int n)
{
//Graham扫描求凸包
int i;
//将最左下的点调整到p[0]的位置
for(i = 1;i <= n - 1;i++){
if((p[i].y < p[0].y) || (p[i].y == p[0].y && p[i].x < p[0].x))
swap(p, 0, i);
}
//将平p[1]到p[n - 1]按按极角排序，可采用快速排序
qsort(p + 1, , n - 1, sizeof(p[0], cmp));
for(i = 0;i <= 2;i++) stack[i] = i;
top = 2;
for(i = 3;i <= n - 1;i++){
while(multi(p[i], p[stack[top]], p[stack[top - 1]]) > 0) top–;
}
top++;
stack[top] = i;
}
int main()
{
}
POJ计算几何解题报告http://old.blog.edu.cn/user3/Hailer/archives/2008/2158935.shtml | 
转播
