凸包问题

凸包问题

摘要：凸包问题是计算机几何中的一个经典问题，它要求将平面内的点集用最少的凸点将所有的顶点封闭。凸包问题的应用十分广泛，很多最优化问题经过抽象后可以发现它最终是凸包问题模型；它还可以用于人际关系网络的最小化搜索， 通过人际关系，可以合理推断出某人的身份，职位等个人特征。目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris 步进法。其中穷举法与蛮力法都是建立在穷举的算法思想上，它们的时间复杂度比较大，格雷厄姆扫描法采用几何方面的知识，降低了求解过程的时间复杂度。 关键词： 凸包问题 ；计算机几何 ；格雷厄姆扫描法

一、引言

凸包问题的完整描述：令S 是平面上的一个点集，封闭S 中所有顶点的最小凸多边形，称为S 的凸包，表示为CH（S）。如下图一所示，由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。

图一

凸包问题是计算机几何的一个经典问题，它可以解决很多优化模型，目前目前求取凸包的常用算法有：穷举法，格雷厄姆扫描法（Graham），分治法，蛮力法和Jarris 步进法。本文主要讨论穷举法，蛮力法，以及格雷厄姆扫描法，通过算法思想的描述，计算出相应的时间复杂度，比较这几种算法的优劣。

二、穷举法

穷举法的思想很简单直接，它利用凸包性质—如果点集中的两个点的连线属于凸多边形的边，当且仅当点集中其余的点都在这两个点连线的同一侧。

n(n?1)假设点集合S中有n个顶点，则这n个顶点共可以构成2条边，对于任何

一条边来讲，检查其余的n-2 个点的相对于该直线段的正负性。如果它们有相同的正负性，说明该边是凸多边形的边，反之就不属于凸多边形，继续检查。算法流程图如下：

开始

不相同 判断其余的n-2 个点的相对于该直线段的正负性 相同 从点集S中取出两个顶 点u，v 把u，v加入凸包 判断执行次数是否 n(n?1)大于

2 N Y

结束 图二：算法流程图

上述算法（穷举法）需要执行n(n-1)/2 次，再次检查n-2 个点的正负性，故算法

n2(n?1)时间复杂性为?=o(n3)。显然这并非一个高效的算法凸包问题有许多更

2加有效的算法可以达到nlogn的渐近时间复杂度。 三、蛮力法

蛮力法求解凸包问题的基本思想：对于一个由n 个点构成的集合S 中的两个点Pi 和Pj，当且当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况），他们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。

检验其余顶点是否同一边时，在平面上，穿过两个点(x1,y1)和(x2,y2)的直线是由下面的方程定义的：

ax + by = c (其中a=y2-y1,b=x2-x1,c=x1y2-x2y1)

这样一条直线把平面分成两个半平面：其中一个半平面中的点都满足ax + by＞c，另一个半平面中的点都满足ax + by＜c，因此，为了检验这些点是否位于这条直线的同一边， 可以简单地把每个点代入方程ax + by = c，检验这些表达式的符号是否相同。此算法的时间复杂度同于穷举法，此算法的巧妙之处在于它对于判断剩余顶点是否在同一边的处理。由所有不同的点共组成了n(n-1)/2边，要对每条边都要对其他n-2个顶点求出在直线方程ax + by = c中的符号，所以，其时间复杂性是O(n3)。代码见附录一 四：格雷厄姆扫描算法

格雷厄姆扫描法是利用平面上任意3 点所构成的回路是左转还是右转的判别法来求平面点集的凸包。

三角区符号的计算：主要用于判断线段相对于基准线来讲，是位于基准线的左方还是右方。比如说平面上有3个点p1(x1,y1),p2(x2,y2),p3(x3,y3),让我们判????????????断p1p3是位于p1p2的左方还是右方。判断方法,用叉积：

D?x3?x1,y3?y1x2?x1,y2?y1?(x3?x1)*(y2?y1)?(x2?x1)*(y3?y1)

????????????若D>0,则p1p3在p1p2右侧，即在顺时针方向； ????????????若D<0, 则p1p3在p1p2左侧，即在逆时针方向； ????????????若D=0，则p1p3与p1p2在同一条直线上。

算法

第一步：幅角排序。首先在点集中选取其中y坐标最小的那个点记为p0，连接p0到每个剩余点的线段，将这些线段按逆时针方向进行排序，第一条线段对应的另一顶点标为p1，后续的线段依次这样标记过程如下图：

图三

第二步：幅角扫描。堆栈初始化为CH（S）={pn-1,p0}，其中p1 为栈顶元素。按极坐标的幅角，从p0 开始，到pn-1 为止进行扫描。假定在某一时刻，堆栈内容为：CH（S）={pn-1,p0,…, pi,pj,pk}其中，pk为栈顶元素，则栈中元素按顺序构

成一个半封闭的凸多边形。假设pl是正在扫描的点，如果pjpkpl构成的路径是

左转的，如下图三b所示，则由pkpl形成的边将是凸边，可以把作为半封闭的凸多边形中的一条边加入进来，因此把pl压入栈顶，把扫描线移到下一点；如果

pjpkpl构成的路径是右转的，则pk不可是凸包的极点，将弹出栈顶，而扫描线

仍然停留在pl上。如果构成的路径是右转的这样，在下一轮处理中，将由piplpj进行判断和作出处理。

图四

3．算法步骤：

（1）求平面点集S 中Y 坐标最小的点p0。

（2）以p0 为源点，变换S-{p0}中所有点的坐标 （3）以p0 为源点，计算S-{p0}中所有点的幅角。

（4）以幅角的非降排序S-{p0}中所有的点，令事件调度点T={p1,p2,…, pn-1}是排序过的数组。

（5）初始化堆栈：令CHS[0]=pn-1，CHS[1]=p0；令堆栈指针sp=1，事件调度点数组T 的下标k＝0。

（6）如果k

代码实现见附录二

p0，T[K]所构成的三角区符号D，若D ?0,则

sp++， CHS[sp]=T[k]，k++，转步骤（6）；否则，sp--转步骤（6）

四、算法比较

蛮力法和穷举法都是基于穷举思想的算法，它们的时间复杂度是解决凸包问题算法中最复杂的o(n3)，它们易于理解，适用于解决规模较小的问题。而格雷厄

姆扫描算法的时间复杂度为o(nlogn)，它是解决此类问题的一个比较高效的一个算法。

五、学习心得和体会

通过此次对凸包问题的研究与学习，我了解到了数学思维对于算法设计的重要性，同时也认识到计算机几何对于问题处理的简化。用几何知识来解决一些较难的题目，有时会起到意想不到的效果。用数学方法解决问题永远要比计算机高效，有很多比较难的ACM竞赛题，它考的更多的是数学方法与计算机技术相结合的综合能力，在学好算法的同时，我们更应当学会用数学思维出看待和处理问题。

参考文献：

杭电ACM课件-计算机几何讲解 刘东英 附录：

附录一:蛮力法代码

Void convex_hull() {

int I,j,k,sign=0; double a=0,b=0,c=0; for(i=0;i

a = my_point[j].y – my_point[i].y; b = my_point[j].x – my_point[i].x;

c = (my_point[i].x * my_point[j].y) – (my_point[i].y * my_point[j].x) sign=0;

for(k=0;k

if((k==j)||(k==i)) continue;

if ((a * my_point[k].x + b*mypoint[k].y)==c) exit(1);

if ((a * my_point[k].x + b*mypoint[k].y)>c) ++sign;

if ((a * my_point[k].x + b*mypoint[k].y)

if (((sign==(MAX_NUM-2))||((sign==(2- MAX_NUM))) {

printf(\my_point[i].flag=1; my_point[j].flag=1; } }

printf(\

}

附录二：

Void convex_hull(POINT S[],POINT CHS[],int n,int &sp {

int i,k; float D; SPOINT T[n];

for (i=1;i

if ((S[i].y

for (i=1;i

T[i-1].ang=atan(T[i-1].y,T[i-1].x); /*求T[i]的幅角*/ }

Sort(T,n-1); /*按T[i]幅角的非降顺序排序T[i]*/ CHS[0].x=T[n-2].x;CHS[0].y=T[n-2].y; CHS[1].x=0;CHS[1].y=0;sp=1;k=0;

While (k

D=CHS[sp-1].x*CHS[sp].y+CHS[sp].x*T[k].y+T[k].x*CHS[sp-1].y-CHS[sp-1].y *CHS[sp].x-CHS[sp].y*T[k].x-T[k].y*CHS[sp-1].x; if (D>=0)

CHS[++sp]=T[k+1]; /* 若 ,T[k]压入栈顶，扫描线前移一点*/ else sp--; /* 否则，弹出栈顶元素*/ } }

}

附录二：

Void convex_hull(POINT S[],POINT CHS[],int n,int &sp {

int i,k; float D; SPOINT T[n];

for (i=1;i

if ((S[i].y

for (i=1;i

T[i-1].ang=atan(T[i-1].y,T[i-1].x); /*求T[i]的幅角*/ }

Sort(T,n-1); /*按T[i]幅角的非降顺序排序T[i]*/ CHS[0].x=T[n-2].x;CHS[0].y=T[n-2].y; CHS[1].x=0;CHS[1].y=0;sp=1;k=0;

While (k

D=CHS[sp-1].x*CHS[sp].y+CHS[sp].x*T[k].y+T[k].x*CHS[sp-1].y-CHS[sp-1].y *CHS[sp].x-CHS[sp].y*T[k].x-T[k].y*CHS[sp-1].x; if (D>=0)

CHS[++sp]=T[k+1]; /* 若 ,T[k]压入栈顶，扫描线前移一点*/ else sp--; /* 否则，弹出栈顶元素*/ } }

本文来源：https://www.bwwdw.com/article/44h7.html