文档介绍：第九章凸包问题
令S是平面上的一个点集,封闭S中所有顶点的最小凸多边形,称为S的凸包,表示为CH(S)。如下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。
求取凸包的常用算法有:穷举法,格雷厄姆扫描法(Graham),分治法,蛮力法和Jarris步进法。
一、穷举法
1、凸包性质:如果点集中的两个点的连线属于凸多边形的边,当且仅当点集中其余的点都在这两个点连线的同一侧。
2、算法描述:
第一步:把点集(不妨设点集大小为n)中的点两两配对,得到条直线段。
第二步:对于每一条直线段检查其余的个点的相对于该直线段的正负性。如果它们有相同的正负性。那么直线段属于凸多边形的边,反之就不属于凸多边形,继续检查。
存在不同
算法流程图
上述算法(穷举法)需要执行n(n-1)/2次,再次检查n-2个点的正负性,故算法时间复杂性为
然这并非一个高效的算法。凸包问题有许多更加有效的算法可以达到⊙的渐近时间复杂度。
二、凸包问题的格雷厄姆(Graham)扫描法
格雷厄姆扫描法是利用平面上任意3点所构成的回路是左转还是右转的判别法来求平面点集的凸包。
1、三角区符号的计算
点,,是平面上的任意三点,
当D为正时,构成一个反时针方向的回路,即,是左转的;当D为负时,构成一个顺时针方向的回路,即是右转的;当D为零时,此三点共线。
2、算法思想:
第一部分:幅角排序。首先,在平面上集S中寻找y坐标最小的点。如果有两个以上的点,其y坐标都是最小的,就选择最右边的一点,把它称为。以后以为源点,对所有点的坐标进行变换。对变换后的所有点,以为源点,
图1
计算它们的极坐标幅角。以幅角的非降顺序来排序的点,如果有两个以上的点,其幅角大小相同,以最接近的点优先。令排序过的点为,其中和分别与构成最小与最大的幅角。
第二部分:幅角扫描。堆栈初始化为,其中为栈顶元素。按极坐标的幅角,从开始,到为止进行扫描。假定在某一时刻,堆栈内容为:
图2
其中,为栈顶元素,则栈中元素按顺序构成一个半封闭的凸多边形。(见图3a)令是正在扫描的点,如果构成的路径是左转的(见图3b),则由形成的边将是凸边,可以把作为半封闭的凸多边形中的一条边加入进来,因此把压入栈顶,把扫描线移到下一点;如果构成的路径是右转的(见图3c),则不可能是凸包的极点,将弹出栈顶,而扫描线仍然停留在
上。这样,在下一轮处理中,将由进行判断和作出处理。
图 3
3、算法步骤:
(1)求平面点集S中Y坐标最小的点。
(2)以为源点,变换中所有点的坐标
(3)以为源点,计算中所有点的幅角。
(4)以幅角的非降排序中所有的点,令事件调度点是排序过的数组。
(5)初始化堆栈:令,;令堆栈指针,事件调度点数组T的下标k=0。
(6)如果k<n-1,转步骤(7);否则,算法结束。
(7)计算,,所构成的三角区符号D,若,
,,,转步骤(6);否则,;转步骤(6)。
4、算法实现
输入:平面点集S[ ],顶点个数n
输出:构成凸包的极点CHS[ ],极点个数sp
Void convex_hull(POINT S[],POINT CHS[],int n,int &sp
{
int i,k;
float D;
SPOINT T[n];
for (i=1;i<n;i++) /* s中Y坐标最小的点于S[0]*/
if ((S[i].y<S[0].y)||((S[i].y=S[0].y)&&S[i].x<S[0].x))
swap(S[i],S[0]);
for (i=1;i<n;i++) { /*以S[0]为源点,变换S[i]的坐标于T[i-1]*/
T[i-1].x=S[i].x-S[0].x;T[i-1].y=S[i].y-S[0].y;
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<n-1) { /*求栈顶两点及扫描线上一点构成的三角符号*/
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-